Road2Geeks

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...

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 =...

Binary Search on Answer – LeetCode 1552 Explained LeetCode 1552 ( Magnetic Force Between Two Balls ) is a classic problem that teaches the Binary Search on Answer pattern. This problem may not look like a binary search problem at first glance, but once the intuition clicks, the solution becomes very elegant. 🔍 Problem Summary You are given an array position representing positions on a line. You must place m balls such that the minimum distance between any two balls is as large as possible. 🧠 Key Insight Instead of placing balls directly, we ask a better question: Can we place m balls if the minimum distance between each ball is at least d ? This question has a monotonic behavior : If distance d is possible, then any smaller distance is also possible. If distance d is not possible, then any larger distance is impossible. This monotonic nature allows us to apply binary se...

How I Finally Understood the “Binary Search on Answer” Pattern (Split Array Largest Sum) While solving LeetCode 410 – Split Array Largest Sum , I realized something important: even when a solution looks easy to code, the intuition behind it doesn’t always come immediately. And that’s completely normal. Initially, my mind went toward a DFS / backtracking approach. The problem talks about splitting an array in multiple ways, so exploring combinations felt like the right direction. But since I haven’t solved DFS problems yet, I couldn’t even visualize what that solution would look like. The Key Shift in Thinking After watching a few videos (there aren’t many good ones for this problem), I realized something subtle but powerful: We don’t need to generate all possible splits. We only need to check whether a split is possible under a given constraint. This single realization completely changes the approa...

LeetCode 1760: Minimum Limit of Balls in a Bag (Binary Search on Answer) LeetCode 1760 is a classic example of the Binary Search on Answer pattern. While many tutorials explain the binary search part, they often skip the most important piece — how the feasibility (possible) function actually works . In this article, we will focus on building the intuition behind the solution, especially the logic used to count operations inside the possible() function. 🔹 Problem Overview You are given an array nums where each element represents the number of balls in a bag. You are allowed to perform at most maxOperations operations. In one operation, you can split a bag into two bags with any positive number of balls. Your goal is to minimize the maximum number of balls in any bag . 🔹 Why Binary Search Works Here We are not searching inside the array. Instead, we are searching for the minimum possibl...

Minimum Number of Days to Make m Bouquets (LeetCode 1482) This problem is a classic example of the Binary Search on Answer pattern. Instead of searching within an array, we search for the minimum day on which it becomes possible to make the required bouquets. Initially, the problem may look confusing because it combines conditions like adjacency , grouping , and minimum constraints . But once the problem is reframed correctly, the solution becomes systematic. 🔍 Problem Understanding You are given an array bloomDay where each value represents the day a flower blooms. To make m bouquets: Each bouquet needs exactly k adjacent flowers A flower can be used only once You must minimize the number of days If it is impossible to make m bouquets, return -1 . 💡 Key Insight Instead of asking "How many bouquets can I make?" , the real question is: By day X...

Binary Search on Answer – Smallest Divisor Given a Threshold Binary Search on Answer is a powerful problem-solving pattern where instead of searching within an array, we perform binary search over the range of possible answers . LeetCode problem 1283 – Smallest Divisor Given a Threshold is a classic example of this pattern. 🔍 Problem Intuition We are given an array of positive integers and a threshold. For any chosen divisor d , we divide each element by d , round it up using ceil , and sum the results. Our goal is to find the smallest possible divisor such that this sum does not exceed the given threshold. 💡 Key Observation If the divisor is small → the sum becomes large If the divisor is large → the sum becomes small This creates a monotonic condition , making it a perfect candidate for binary search on the answer. ⚠️ Important Edge Case The divisor can never be 0 . S...

Binary Search on Answer Pattern (Complete Practice Guide) Binary Search on Answer is a powerful problem-solving pattern frequently used in coding interviews and competitive programming. Instead of searching inside an array, we perform binary search on the range of possible answers . Minimum or maximum value is asked Answer lies within a numeric range A feasibility function exists Feasibility is monotonic 📌 LeetCode Problems Using Binary Search on Answer Problem Difficulty Core Idea 1283 – Find the Smallest Divisor Given a Threshold Easy Binary search on divisor value 1011 – Capacity To Ship Packages Within D Days ...

LeetCode 875: Koko Eating Bananas – Binary Search on Answer Explained LeetCode 875, Koko Eating Bananas , is a classic problem that looks simple at first glance but introduces a powerful and reusable concept: Binary Search on the Answer . In this article, we’ll break down the intuition, approach, and final Python solution step by step. 👉 Full source code is available here: GitHub – LeetCode 875 Solution 🧠 Problem Overview Koko loves bananas and has h hours to eat all the bananas from multiple piles. She can choose a speed k (bananas per hour) and eats from only one pile per hour. The goal is to find the minimum eating speed that allows her to finish within h hours. ❌ Why Brute Force Fails A naive approach would be to try every possible eating speed from 1 to max(piles) and check if Koko can finish on time. However, this leads to an ine...

Find Minimum in Rotated Sorted Array – Binary Search (LeetCode 153) In this problem, we are given a rotated sorted array with unique elements. The goal is to find the minimum element in O(log n) time, which naturally points to a binary search based solution. Key Observations A rotated sorted array always has one sorted half. If the array is not rotated, the first element is the minimum. The minimum element always lies in the unsorted half. Approach We use two pointers ( s and e ) and compare the middle element with the right boundary. Based on this comparison, we eliminate the sorted half and narrow the search space until both pointers converge. Python Code class Solution: def findMin(self, nums: List[int]) -> int: s, e = 0, len(nums) - 1 while s nums[e]: s = mid + 1 else: e = mid...

Binary Search in Python – Simple and Efficient Approach (LeetCode 704) Today I solved LeetCode 704: Binary Search , and the problem felt quite straightforward since I was already familiar with the binary search concept. This problem is a classic example of how knowing the fundamentals can make problem-solving much easier. The task is simple: given a sorted array of integers and a target value, return the index of the target if it exists. Otherwise, return -1 . Since the array is already sorted, binary search is the most optimal approach. Why Binary Search? Binary search works by repeatedly dividing the search space in half. Instead of checking every element one by one, we compare the middle element with the target and eliminate half of the array in each step. This drastically improves performance compared to a linear search. Approach Explained Initialize tw...

Problem Overview The problem Find the Duplicate Number gives an array of size n + 1 where each number lies in the range 1 to n . There is only one repeated number, but it may appear more than once. The main challenge is to find the duplicate without modifying the array and using constant extra space . My First Approach: Using a HashSet The most straightforward solution that came to my mind was using a HashSet. The idea is simple: keep inserting elements into a set, and if an element already exists, return it as the duplicate. class Solution: def findDuplicate(self, nums: List[int]) -> int: h_set = set() for i in nums: if i in h_set: return i h_set.add(i) This solution works perfectly and runs in O(n) time, but it uses O(n) extra space, which violates the problem constraint. Key Insight from the Tutorial: Think of It as a Linked List After watching a YouTube tutorial, I learned a crucial observation...

Middle of the Linked List – Optimal Two Pointer Approach Finding the middle of a singly linked list efficiently is a common interview problem. In this solution, we use the slow and fast pointer technique to determine the middle node in a single traversal. Intuition Behind the Approach We maintain two pointers: Slow Pointer (p1) → moves one step at a time Fast Pointer (p2) → moves two steps at a time When the fast pointer reaches the end of the list, the slow pointer will be positioned at the middle of the linked list. Visual Representation Python Implementation class Solution: def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]: p1 = p2 = head while p2 and p2.next: p1 = p1.next p2 = p2.next.next return p1 Why This Works Since the fast pointer moves twice as fast as the slow pointer, by the time it reache...

Linked List Cycle Detection using Floyd’s Algorithm (LeetCode 141) Detecting a cycle in a singly linked list is a classic problem that can be solved efficiently using Floyd’s Tortoise and Hare algorithm. Optimal Approach: Two Pointers (Cleaner Loop) This is the most readable and interview-preferred implementation. It uses two pointers moving at different speeds. class Solution: def hasCycle(self, head: Optional[ListNode]) -> bool: slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: return True return False Alternate Implementation (Non-Cleaner Loop) Below is a logically correct version that performs additional checks inside the loop to avoid null pointer access. class Solution: def hasCycle(self, head: Optional[ListNode]) -> bool: slow_pointer = fast_pointer = head ...

Longest Conseive Sequence – From TLE to Optimal O(n) The Longest Consecutive Sequence problem looks simple at first, but it easily leads to a Time Limit Exceeded (TLE) error if we are not careful with repeated work. In this post, I’ll explain where the TLE comes from and how a small optimization makes the solution run in linear time. Problem Overview Given an unsorted array of integers, we need to find the length of the longest sequence of consecutive numbers. The solution must run in O(n) time. Initial Thought Process (Why TLE Happens) A common approach is to check for every number and keep extending the sequence forward ( x, x+1, x+2... ). While lookup using a hash structure is O(1), the same sequence gets counted multiple times, leading to unnecessary repeated work. In the worst case (like a fully consecutive array), this turns into O(n²) , which causes TLE. Key Optimization The fix is surprisingly small but powerful: Only start counting when the current nu...

Group Anagrams in Python – Optimal Hashing Approach (LeetCode 49) The Group Anagrams problem is a classic hashing question frequently asked in coding interviews. The goal is to group strings that are anagrams of each other, meaning they contain the same characters with the same frequencies but possibly in a different order. In this post, I’ll explain an optimal Python solution using character frequency counting, which avoids sorting and achieves better performance. 🔍 Problem Overview You are given an array of strings. Your task is to group all strings that are anagrams of each other and return them as a list of groups. Two strings are anagrams if: They contain the same characters Each character appears the same number of times 💡 Key Intuition Instead of sorting every string (which costs O(k log k) time), we represent each word using a fixed-size frequency array of 26 characters. Since the English alphabet has only 26 lowercase letters, the freq...

Problem Overview An anagram is formed when two strings contain the same characters with the same frequency, but possibly in a different order. The task is to determine whether two given strings are valid anagrams of each other. Key Observation Since character order does not matter in an anagram, comparing strings position by position is ineffective. What actually matters is the frequency of each character in both strings. Optimal Approach Using HashMaps We use two hashmaps (dictionaries) to count the frequency of characters in both strings. If both maps are identical, the strings are anagrams. Traverse the first string and count character frequencies Traverse the second string and count character frequencies Compare both frequency maps Python Code Implementation class Solution: def isAnagram(self, s: str, t: str) -> bool: s_map = {} t_map = {} for ch in s: s_map[ch] = s_map.get(ch, 0) + 1 for ch in t: ...

Two Sum Problem – From Confusion to Clear Intuition The Two Sum problem is one of those classic interview questions that looks simple, but can easily trap you into an inefficient approach if you don’t recognize the pattern early. Initially, I also thought about checking every possible pair, but that quickly leads to a slow solution. Problem Statement (In Simple Words) You are given an array of integers and a target value. Your task is to return the indices of the two numbers such that they add up to the target. Each input has exactly one solution, and you cannot use the same element twice. Brute Force Thought Process The first idea that naturally comes to mind is: for every number, check all other numbers to see if their sum equals the target. While this works logically, it results in O(n²) time complexity, which is not optimal. Key Insight That Changes Everything Instead of asking: “Which two numbers add up to the target?” I reframed the question as: “For the current...