Upsolving a Hard Problem: Divisors, Permutations, and Smart Observation

Day 73 on LeetCode Find First and Last Position of Element in Sorted Array 🎯🔍✅ Today’s problem focused on a classic and very important Binary Search variation. 🔹 Approach Used in My Solution The goal was to find the first and last occurrence of a target in a sorted array. Key idea in the solution: • Use two separate binary searches 🔸 Find First Occurrence: • When nums[mid] >= target, move left • If nums[mid] == target, store index and continue searching left 🔸 Find Last Occurrence: • When nums[mid] <= target, move right • If nums[mid] == target, store index and continue searching right • Combine both results to get final answer This ensures we don’t just find a match, but the complete range of the target. ⚡ Complexity: • Time Complexity: O(log n) • Space Complexity: O(1) 💡 Key Takeaways: • Learned how to modify binary search to find boundaries instead of single elements • Strengthened understanding of first/last occurrence patterns • Realized how small logic changes turn binary search into powerful variants 🔥 This pattern is extremely common in interview problems! #LeetCode #DSA #Algorithms #DataStructures #BinarySearch #Arrays #ProblemSolving #Coding #Programming #Cpp #STL #SoftwareEngineering #ComputerScience #CodingPractice #DeveloperLife #TechJourney #CodingDaily #100DaysOfCode #BuildInPublic #AlgorithmPractice #CodingSkills #Developers #TechCommunity #SoftwareDeveloper #EngineeringJourney

🧱 𝗜 𝗦𝗼𝗹𝘃𝗲𝗱 𝗮 “𝗩𝗶𝘀𝘂𝗮𝗹” 𝗣𝗿𝗼𝗯𝗹𝗲𝗺 𝗨𝘀𝗶𝗻𝗴 𝗢𝗻𝗹𝘆 𝗮 𝗦𝘁𝗮𝗰𝗸 — 𝗡𝗼 𝗚𝗲𝗼𝗺𝗲𝘁𝗿𝘆 𝗡𝗲𝗲𝗱𝗲𝗱 Today’s problem looked visual and innocent: 𝗚𝗶𝘃𝗲𝗻 𝗯𝗮𝗿 𝗵𝗲𝗶𝗴𝗵𝘁𝘀 𝗼𝗳 𝗮 𝗵𝗶𝘀𝘁𝗼𝗴𝗿𝗮𝗺 (𝘄𝗶𝗱𝘁𝗵 = 𝟭), 𝗳𝗶𝗻𝗱 𝘁𝗵𝗲 𝗹𝗮𝗿𝗴𝗲𝘀𝘁 𝗿𝗲𝗰𝘁𝗮𝗻𝗴𝗹𝗲 𝗮𝗿𝗲𝗮. This is the classic problem from 𝗟𝗲𝗲𝘁𝗖𝗼𝗱𝗲 — and it’s a beautiful lesson in how 𝗺𝗼𝗻𝗼𝘁𝗼𝗻𝗶𝗰 𝘀𝘁𝗮𝗰𝗸𝘀 𝗰𝗼𝗻𝘃𝗲𝗿𝘁 𝗴𝗲𝗼𝗺𝗲𝘁𝗿𝘆 𝗶𝗻𝘁𝗼 𝗶𝗻𝗱𝗶𝗰𝗲𝘀. 🧠 𝗧𝗵𝗲 𝗡𝗮𝗶𝘃𝗲 𝗧𝗵𝗼𝘂𝗴𝗵𝘁 (𝗮𝗻𝗱 𝘄𝗵𝘆 𝗶𝘁 𝗳𝗮𝗶𝗹𝘀) For every bar i, try expanding left and right until you hit a smaller bar. That’s O(n) per index -> O(n²). Too slow for n=10^5. So the real question becomes: For each bar, how far can it extend without hitting a smaller height? That is the entire problem. 💡 𝗞𝗲𝘆 𝗜𝗱𝗲𝗮 — 𝗡𝗲𝗮𝗿𝗲𝘀𝘁 𝗦𝗺𝗮𝗹𝗹𝗲𝗿 𝗘𝗹𝗲𝗺𝗲𝗻𝘁𝘀 For every index i: 1. Find the first smaller bar on the left 2. Find the first smaller bar on the right A monotonic increasing stack gives both in linear time. ▶️ 𝗟𝗲𝗳𝘁 𝗦𝗰𝗮𝗻 (𝗟 -> 𝗥) Pop until the top is strictly smaller. That index defines the left boundary. ◀️ 𝗥𝗶𝗴𝗵𝘁 𝗦𝗰𝗮𝗻 (𝗥 -> 𝗟) Same logic to get the right boundary. Now each bar knows the exact range where it is the minimum. ⏱️ 𝗖𝗼𝗺𝗽𝗹𝗲𝘅𝗶𝘁𝘆 Each index pushed/popped once → O(n) Space → O(n) ✨ 𝗟𝗲𝗮𝗿𝗻𝗶𝗻𝗴𝘀 1. “Nearest smaller element” is a powerful pattern 2. Monotonic stacks turn nested loops into linear scans 3. Think: If this bar is the minimum, how wide can the rectangle be? A visual problem, solved with clean stack discipline. #DataStructures #Algorithms #MonotonicStack #Java #ProblemSolving #CodingInterview #Stack #DSA #LeetCode #Coding #Programmer #SoftwareEngineer #InterviewPrep #CompetitiveProgramming #100DaysOfCode #Tech #Learning #ProblemSolvingSkills

Most developers approach range update problems with brute force and hit performance limits. The Difference Array Technique is a powerful optimization that reduces time complexity from O(n × q) to O(n + q) by shifting how updates are applied. Instead of updating every element in a range, you mark changes and resolve them later using prefix sums. Efficient thinking > brute force execution. If you’re preparing for coding interviews or improving problem-solving skills, this is a must-know pattern. #codefri #datastructures #algorithms #dsa #softwareengineering #codinginterview #programming #developers #codingcommunity #learncoding

🧩 𝗦𝘁𝗼𝗽 𝗦𝗲𝗮𝗿𝗰𝗵𝗶𝗻𝗴 𝗥𝗲𝗰𝘁𝗮𝗻𝗴𝗹𝗲𝘀: 𝗧𝗵𝗲 𝗛𝗶𝘀𝘁𝗼𝗴𝗿𝗮𝗺 𝗠𝗶𝗻𝗱𝘀𝗲𝘁 𝗧𝗵𝗮𝘁 𝗦𝗼𝗹𝘃𝗲𝘀 𝗧𝗵𝗶𝘀 𝗠𝗮𝘁𝗿𝗶𝘅 𝗜𝗻𝘁𝗲𝗿𝘃𝗶𝗲𝘄 𝗣𝗿𝗼𝗯𝗹𝗲𝗺 Solved an interesting problem today on 𝗟𝗲𝗲𝘁𝗖𝗼𝗱𝗲: 𝗙𝗶𝗻𝗱 𝘁𝗵𝗲 𝗮𝗿𝗲𝗮 𝗼𝗳 𝘁𝗵𝗲 𝗹𝗮𝗿𝗴𝗲𝘀𝘁 𝗿𝗲𝗰𝘁𝗮𝗻𝗴𝗹𝗲 𝗰𝗼𝗻𝘁𝗮𝗶𝗻𝗶𝗻𝗴 𝗼𝗻𝗹𝘆 𝟭’𝘀 𝗶𝗻 𝗮 𝗯𝗶𝗻𝗮𝗿𝘆 𝗺𝗮𝘁𝗿𝗶𝘅. At first glance, this looks like a classic 𝟮𝗗 𝗿𝗲𝗰𝘁𝗮𝗻𝗴𝗹𝗲 𝘀𝗲𝗮𝗿𝗰𝗵. But the elegant solution doesn’t search rectangles at all. It 𝗯𝘂𝗶𝗹𝗱𝘀 𝘁𝗵𝗲𝗺 𝘃𝗲𝗿𝘁𝗶𝗰𝗮𝗹𝗹𝘆. 🔄 𝗥𝗼𝘄 𝗯𝘆 𝗥𝗼𝘄 𝗧𝗿𝗮𝗻𝘀𝗳𝗼𝗿𝗺𝗮𝘁𝗶𝗼𝗻 For each row, treat the matrix like this: 1. ‘1’ → increase the column height 2. ‘0’ → reset the column height to 0 After processing a row, you don’t see a matrix anymore. You see a histogram. And now the question becomes: What’s the largest rectangle in this histogram? 🧠 𝗧𝗵𝗲 𝗖𝗹𝗲𝘃𝗲𝗿 𝗧𝘄𝗶𝘀𝘁 Instead of the usual stack approach, maintain three arrays: heights[] → current bar heights leftBoundaries[] → how far left this bar can extend rightBoundaries[] → how far right this bar can extend Two linear scans per row set these boundaries precisely. 📐 𝗔𝗿𝗲𝗮 𝗖𝗼𝗺𝗽𝘂𝘁𝗮𝘁𝗶𝗼𝗻 For every column: width = rightBoundaries[j] - leftBoundaries[j] area = heights[j] * width Update the maximum. Move to the next row. Repeat. 💡 𝗪𝗵𝘆 𝘁𝗵𝗶𝘀 𝘄𝗼𝗿𝗸𝘀 𝗯𝗲𝗮𝘂𝘁𝗶𝗳𝘂𝗹𝗹𝘆 Because for every row, we already know: 1. Continuous height of 1’s above 2. Maximum width possible at that height So we compute the best rectangle in constant time per column. ⚙️ 𝗖𝗼𝗺𝗽𝗹𝗲𝘅𝗶𝘁𝘆 Time: O(rows × cols) Space: O(cols) Optimal. Clean. Elegant. ✨ 𝗧𝗮𝗸𝗲𝗮𝘄𝗮𝘆 Sometimes the best way to solve a 2D problem is to 𝘀𝘁𝗼𝗽 𝘁𝗵𝗶𝗻𝗸𝗶𝗻𝗴 𝗶𝗻 𝟮𝗗. #Algorithms #DataStructures #LeetCode #Java #CodingInterview #InterviewPrep #DSA #ProblemSolving #CodingLife #Developers #SoftwareEngineer #TechInterview #Programming #LearnToCode #CodeNewbie #CompetitiveProgramming #100DaysOfCode #Debugging #Optimization #LogicBuilding #STEM

𝗧𝗵𝗶𝘀 𝗧𝗿𝗲𝗲 𝗣𝗿𝗼𝗯𝗹𝗲𝗺 𝗟𝗼𝗼𝗸𝘀 𝗟𝗶𝗸𝗲 𝗗𝗙𝗦… 𝗨𝗻𝘁𝗶𝗹 𝗡𝘂𝗺𝗯𝗲𝗿 𝗧𝗵𝗲𝗼𝗿𝘆 𝗕𝗿𝗲𝗮𝗸𝘀 𝗜𝘁 𝗢𝗽𝗲𝗻 🌳 Today’s problem looked like a simple tree traversal - until a quiet condition appeared: Count ancestors where nums[i] * nums[ancestor] is 𝗮 𝗽𝗲𝗿𝗳𝗲𝗰𝘁 𝘀𝗾𝘂𝗮𝗿𝗲. Brute force (walking up ancestors for every node) is too slow. The real win comes from 𝗰𝗵𝗮𝗻𝗴𝗶𝗻𝗴 𝘁𝗵𝗲 𝗽𝗲𝗿𝘀𝗽𝗲𝗰𝘁𝗶𝘃𝗲. 💡 𝗧𝗵𝗲 𝗞𝗲𝘆 𝗜𝗻𝘀𝗶𝗴𝗵𝘁 A product is a perfect square iff every prime factor appears an even number of times. So reduce every number to its square-free form: keep only primes with odd exponent. Examples: 12 = 2^2 × 3 -> 3 18 = 2 × 3^2 -> 2 Now the condition becomes: Two numbers form a perfect square product iff their square-free forms are equal. 🚀 𝗪𝗵𝗮𝘁 𝘁𝗵𝗲 𝗽𝗿𝗼𝗯𝗹𝗲𝗺 𝗯𝗲𝗰𝗼𝗺𝗲𝘀 For each node, count how many ancestors have the same square-free value. That’s just DFS + frequency map on the path. 🛠️ 𝗔𝗽𝗽𝗿𝗼𝗮𝗰𝗵 1. Build adjacency list 2. Precompute square-free value for each node 3. DFS from root while maintaining a hashmap of frequencies 4. At each node, add map.get(k[node]) to answer 5. Backtrack (remove from map) No ancestor traversal. No pair checks. ✨ 𝗞𝗲𝘆 𝗟𝗲𝗮𝗿𝗻𝗶𝗻𝗴𝘀 1. Perfect square checks → parity of prime exponents 2. Convert math conditions into hashable signatures 3. DFS + hashmap is powerful for ancestor path problems 4. Optimize by transforming the condition, not the traversal A beautiful mix of Trees + Number Theory + Hashing. #algorithms #datastructures #dfs #numbertheory #trees #hashmap #graph #primefactorization #coding #programming #leetcode #codinginterview #interviewprep #problemSolving #competitiveprogramming #developer #devlife #engineering #tech #learning #growth #100DaysOfCode #career #faangprep

Day 72 on LeetCode Search a 2D Matrix 🔍📊✅ Today’s problem was a great application of Binary Search in 2D, breaking it down into two efficient steps. 🔹 Approach Used in My Solution The goal was to determine whether a target exists in a sorted 2D matrix. Key idea in the solution: • First, apply binary search on rows to find the potential row where the target could exist   – Check if target lies between matrix[mid][0] and matrix[mid][cols-1] • Once the correct row is found, apply binary search within that row • Return true if found, otherwise false This avoids scanning the entire matrix and ensures efficiency. 🔹 Why This Works Because: • Each row is sorted • The first element of each row is greater than the last of the previous row So we can treat it like a two-level binary search problem. ⚡ Complexity: • Time Complexity: O(log m + log n) • Space Complexity: O(1) 💡 Key Takeaways: • Learned how to extend binary search to 2D structures • Practiced breaking problems into smaller searchable spaces • Reinforced thinking in terms of hierarchical searching 🔥 Another solid step in mastering binary search patterns! #LeetCode #DSA #Algorithms #DataStructures #BinarySearch #Matrix #2DArray #ProblemSolving #Coding #Programming #Cpp #STL #SoftwareEngineering #ComputerScience #CodingPractice #DeveloperLife #TechJourney #CodingDaily #100DaysOfCode #BuildInPublic #AlgorithmPractice #CodingSkills #Developers #TechCommunity #SoftwareDeveloper #EngineeringJourney

🔥 𝗪𝗵𝘆 𝗧𝗵𝗶𝘀 “𝗖𝘆𝗰𝗹𝗲” 𝗣𝗿𝗼𝗯𝗹𝗲𝗺 𝗜𝘀 𝗔𝗰𝘁𝘂𝗮𝗹𝗹𝘆 𝗮 𝗖𝗼𝗹𝗼𝗿𝗶𝗻𝗴 𝗣𝗿𝗼𝗯𝗹𝗲𝗺 At first, this problem looks like a 𝗰𝘆𝗰𝗹𝗲 𝘃𝗮𝗹𝗶𝗱𝗮𝘁𝗶𝗼𝗻 problem. We add edges one by one, and after each addition we must ensure that every cycle has an even total weight. The natural thought is to recheck the graph each time, but that quickly becomes too slow. So the key was to rethink the problem in a simpler form. 🔍 𝗦𝘁𝗲𝗽 𝟭 - 𝗧𝗵𝗶𝗻𝗸 𝗢𝗻𝗹𝘆 𝗔𝗯𝗼𝘂𝘁 𝗪𝗲𝗶𝗴𝗵𝘁 = 𝟭 𝗘𝗱𝗴𝗲𝘀 1. Assume all edges have weight 1. 2. Now the condition becomes: every cycle must have an even number of edges. 3. This is exactly the property of a bipartite graph. 4. So, the task reduces to: keep adding edges while maintaining bipartiteness. ⚙️ 𝗦𝘁𝗲𝗽 𝟮 - 𝗨𝘀𝗲 𝗗𝗦𝗨 𝘄𝗶𝘁𝗵 𝗖𝗼𝗹𝗼𝗿𝗶𝗻𝗴 (𝗣𝗮𝗿𝗶𝘁𝘆) Instead of checking bipartiteness repeatedly, maintain it dynamically. Use DSU for components and a color[] array for 2-coloring. For a weight 1 edge (u, v): 1. u and v must have different colors. 2. Same component & same color -> reject 3. Different components & colors clash -> flip one component, then union 4. Otherwise -> union 🔁 𝗦𝘁𝗲𝗽 𝟯 - 𝗛𝗮𝗻𝗱𝗹𝗲 𝗪𝗲𝗶𝗴𝗵𝘁 = 𝟬 𝗘𝗱𝗴𝗲𝘀 (𝗥𝗲𝘃𝗲𝗿𝘀𝗲𝗱 𝗥𝘂𝗹𝗲) A weight 0 edge must not change parity. For a weight 0 edge (u, v): 1. u and v must have the same color. 2. Same component & different color -> reject 3. Different components & colors differ -> flip one component, then union 4. Otherwise -> union ✅ 𝗙𝗶𝗻𝗮𝗹 𝗜𝗱𝗲𝗮 The problem is no longer about checking cycles. It becomes about maintaining a 𝘃𝗮𝗹𝗶𝗱 𝗰𝗼𝗹𝗼𝗿𝗶𝗻𝗴 across DSU components while adding edges, and counting how many edges can be safely added. #DSU #GraphTheory #BipartiteGraph #Parity #UnionFind #DisjointSet #Algorithms #DataStructures #CodingInterview #InterviewPrep #CompetitiveProgramming #LeetCode #ProblemSolving #Programming #TechCareers #SoftwareEngineering #ComputerScience #Dsa #CodingLife #DeveloperJourney #LearnToCode #TechLearning #EdgeCases #Optimization #TimeComplexity

🚀 Day 109 DSA Problem Solving 📌 Problem Solved: Maximum Distance Between a Pair of Values 💡 Level: Medium 🧠 Problem Idea Given two non-increasing arrays, find the maximum distance (j - i) such that: i ≤ j nums1[i] ≤ nums2[j] 🔍 Key Learning Today reinforced a powerful pattern: 👉 When arrays are sorted, always think about Two Pointers before brute force. ⚙️ Approach Used Used Two Pointers (i, j) If condition satisfies → expand j to maximize distance Else → move i to find a smaller value ⏱ Time Complexity O(n + m) ✅ (No nested loops, super efficient) 💭 Real Journey Behind the Solution Initially, I thought about checking all pairs (brute force), but that would lead to TLE. Then I noticed both arrays are non-increasing, which unlocked the two-pointer optimization. This is a reminder that: 👉 Observing constraints carefully can completely change the approach. 📈 Concepts Practiced Two Pointers Greedy Thinking Array Traversal Optimization 🔥 Takeaway Not every problem needs complex logic—sometimes the smartest solution is just about moving pointers wisely. #Day109 #DSAJourney #LeetCode #Coding #Java #ProblemSolving

🚀 Master Time Complexity Like a Pro! Understanding time complexity is not just for interviews — it’s the foundation of writing efficient and scalable code. Here’s a quick cheat sheet of common patterns every developer should know: ✔ Single loop → O(n) ✔ Nested loops → O(n²) ✔ Halving input → O(log n) ✔ Divide & Conquer → O(n log n) 💡 If you can identify patterns, you can solve problems faster — both in coding rounds and real-world systems. 📌 Bookmark this for your coding journey! #programming #dotnet #coding #algorithms #datastructures #softwareengineering #developer #dsa #dotnetfullstackdeveloper #dotnet #interviewprep #developers

Day 68 on LeetCode Guess Number Higher or Lower 🎯✅ Today’s problem reinforced the power of Binary Search on an answer space. 🔹 Approach Used in My Solution The goal was to identify a hidden number using the provided guess() API. Key idea in the solution: • Apply binary search between 1 and n • Pick mid and call guess(mid) • Based on the response:   – 0 → correct number found   – -1 → guessed number is too high → move left   – 1 → guessed number is too low → move right • Continue narrowing the search space until the number is found This is a perfect example of searching efficiently using feedback. ⚡ Complexity: • Time Complexity: O(log n) • Space Complexity: O(1) 💡 Key Takeaways: • Strengthened understanding of binary search with external APIs • Learned how to adjust search space based on feedback • Reinforced the concept of searching on answer space 🔥 Another solid step in mastering binary search patterns! #LeetCode #DSA #Algorithms #DataStructures #BinarySearch #DivideAndConquer #ProblemSolving #Coding #Programming #Cpp #STL #SoftwareEngineering #ComputerScience #CodingPractice #DeveloperLife #TechJourney #CodingDaily #100DaysOfCode #BuildInPublic #AlgorithmPractice #CodingSkills #Developers #TechCommunity #SoftwareDeveloper #EngineeringJourney