Road2Geeks

Greedy Pattern: Erase Overlapping Intervals (LeetCode 435) Some problems quietly test whether you recognize a classic greedy pattern . Erase Overlapping Intervals is one of them. At first glance, it feels like an interval-merging problem. But once you pause and think — the real objective becomes clear: Remove the minimum number of intervals so that the remaining intervals do not overlap. Problem Restatement Given an array of intervals where intervals[i] = [start, end] , return the minimum number of intervals you need to remove to make the rest non-overlapping. Key Insight (Pattern Recognition) Instead of asking: Which intervals should I remove?

Insert Interval (LeetCode 57) The Insert Interval problem looks simple at first glance, but it tests how well you understand interval overlapping and edge cases. The goal is to insert a new interval into a list of already sorted, non-overlapping intervals and merge where necessary — all while maintaining the sorted order. 🧠 Key Observations The intervals are already sorted by start time. There are only three possible cases while traversing intervals. We can process everything in a single pass. 📌 Three Possible Cases Current interval is completely after newInterval → Insert newInterval and append the rest. Current interval is completely before newInterval → Just add it to the result. Overlapping intervals → Merge by expanding newInterval . 🧪 Example Intervals = [[1,3],[6,9]] New Interval = [2,5] Output = [[1,5],[6,9]] 💡 Python Implementation class Solution: def insert(self, intervals, ne...

Merge Intervals – Problem Overview The Merge Intervals problem is a classic greedy + sorting problem that frequently appears in coding interviews. Given a list of intervals, the task is to merge all overlapping intervals and return the non-overlapping result. Key Intuition The core idea is simple but powerful: First, sort all intervals by their start time Then, merge intervals only when they overlap with the previous one Once the intervals are sorted, any overlapping interval must be adjacent. This allows us to solve the problem in a single linear scan after sorting. Step-by-Step Approach Sort the intervals based on the starting value Initialize the result list with the first interval Iterate through the remaining intervals If the current interval overlaps with the last merged interval, update the end boundary If it does not overlap, start a new interval Python Implementation class Solution: def merge(self, intervals: List...

Problem Overview The Largest Rectangle in Histogram problem is one of those classic questions that looks simple but exposes gaps in pattern recognition very quickly. You are given an array where each element represents the height of a bar in a histogram, and your task is to find the area of the largest rectangle that can be formed. Initially, I had no intuition for this problem. I could brute-force it mentally, but nothing scalable came to mind. Only after revisiting monotonic stacks again did the solution start making sense. Key Insight Instead of trying to form rectangles explicitly, flip the thinking: Assume each bar is the shortest bar in the rectangle. Once you do that, the only thing you need to know is: The nearest smaller bar on the left The nearest smaller bar on the right Between these two boundaries, the current bar can safely extend and form a rectangle. This transforms the problem into finding previous smaller and next smaller elements — a ...

LeetCode 739 – Daily Temperatures is a classic problem that tests your understanding of monotonic stacks and future-dependent traversal. While attempting this problem, I experienced an interesting shift in intuition — instead of following a tutorial step by step, I paused after reading the problem statement and tried solving it independently. Without consciously realizing it, I started iterating from the end of the array . At first, it felt random, but later it became clear that this was the key insight needed to build an optimal solution. Problem Understanding The problem asks: for each day, how many days must you wait until a warmer temperature? This means the result at any index depends entirely on future values , not past ones. When a problem depends on future elements, traversing from right to left often simplifies the logic. Key Insight: Reverse Traversal + Monotonic Stack By iterating from the back...

Understanding Next Permutation (LeetCode 31) While following a structured DSA roadmap, most of us get comfortable with patterns like Binary Search, Sliding Window, or Greedy. Then suddenly, a problem like Next Permutation appears — and it feels like it breaks that pattern-based thinking. This is normal. Next Permutation is not a typical pattern problem. It is a rule-based, observation-driven algorithm that relies on understanding lexicographical order rather than deriving a formula or recurrence. Problem Statement Given an array of integers, rearrange it into the next lexicographically greater permutation. If such an arrangement is not possible, rearrange it as the lowest possible order (sorted ascending). The modification must be done in-place using only constant extra space. Key Observations If the array is fully decreasing, it is already the largest permutation. The next permutation is formed by making the smallest possible increase. This increas...

Next Greater Element – Monotonic Stack Approach (LeetCode 496) The Next Greater Element problem is a classic application of the monotonic stack pattern. The goal is to find, for each element in nums1 , the first greater element to its right in nums2 . If no such element exists, we return -1 . Key Observations The relative order of elements in nums2 matters. Brute force would lead to an O(n²) solution. A monotonic decreasing stack allows us to solve this in linear time. Core Idea (Monotonic Stack) We traverse nums2 from right to left and maintain a stack such that: The stack always contains elements in decreasing order. Elements smaller than or equal to the current value are popped. The top of the stack (if it exists) is the next greater element. We store the result in a hashmap so that we can answer queries for nums1 in constant time. Python Implementation class Solution: def nextGreaterElement(self, nums1, nums2): nge =...