Road2Geeks

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

Capacity To Ship Packages Within D Days – Binary Search on Answer This problem is a classic example of the Binary Search on Answer pattern. Instead of searching within the array, we search over the range of possible ship capacities and determine the minimum capacity required to ship all packages within the given number of days. Problem Intuition We are given a list of package weights that must be shipped in the same order within a fixed number of days. Each day, the ship has a fixed capacity and we load packages sequentially until the capacity is exceeded, after which shipping continues the next day. The key observation is that: If a certain ship capacity works, then any larger capacity will also work. If a capacity does not work, then any smaller capacity will also fail. This monotonic behavior allows us to apply binary search efficiently. Search ...

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 Rotated Sorted Array (LeetCode 33) Binary Search in a Rotated Sorted Array is a classic interview problem that tests your understanding of binary search beyond the basics. In this article, we’ll break down the logic, intuition, and implementation of an efficient O(log n) solution using Python. 🔍 Problem Overview You are given a rotated sorted array of distinct integers and a target value. Your task is to return the index of the target if it exists, otherwise return -1 . Example: Input: nums = [4,5,6,7,0,1,2], target = 0 Output: 4 The challenge arises because the array is sorted but rotated at an unknown pivot, which means traditional binary search cannot be applied directly. 🧠 Key Insight At any point in a rotated sorted array, at least one half is always sorted . We use this fact to decide which side of the array to discard during binary search. Identify whether the left or right half is sorted Check if the target lies within the so...

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

Happy Number – HashSet vs Floyd’s Cycle Detection The Happy Number problem looks simple at first, but it hides an important algorithmic concept: cycle detection . In this post, we’ll explore two valid approaches to solve the problem and understand why the optimized solution works. 📌 Complete Python solution code: View on GitHub Problem Overview A number is called happy if repeatedly replacing it with the sum of the squares of its digits eventually leads to 1 . If the process enters a cycle that does not include 1, the number is not happy. Example: 19 → 1² + 9² = 82 82 → 8² + 2² = 68 68 → 6² + 8² = 100 100 → 1² + 0² + 0² = 1 ✅ Approach 1: Using a HashSet The most commonly taught approach uses a HashSet to track numbers we have already seen. If a number repeats, we know we are stuck in a cycle. Idea Store every generated number in a set If the number becomes 1 → happy If the number repeats → cycle detected Code class Solution...

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