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