Road2Geeks

Binary Tree Level Order Traversal — Python Solution Level Order Traversal is one of the fundamental tree traversal techniques where we visit every node of a binary tree level by level, starting from the root and moving left-to-right within each level. It’s widely used in breadth-first search (BFS) patterns and is a staple in algorithm interviews. :contentReference[oaicite:0]{index=0} 💡 What is Level Order Traversal? Given the root of a binary tree, the goal is to return a nested list where each sublist represents all node values at that specific level of the tree. For example, for the binary tree: Input: root = [3,9,20,null,null,15,7] 3 / \ 9 20 / \ 15 7 The expected traversal output is: [ [3], [9,20], [15,7] ] 📌 Idea Behind the App...

Invert Binary Tree (LeetCode 226) Invert Binary Tree is one of the most popular beginner-friendly problems when starting with tree recursion. The task is simple: for every node in the binary tree, swap its left and right children. However, many beginners struggle not with swapping — but with writing the correct base case . This post walks through an initial incorrect approach, explains why it fails, and then breaks down the correct recursive solution. ❌ First Attempt (Incorrect Base Case) Here was my first approach when solving this problem: class Solution: def invertTree(self, root): if not root.left or not root.right: return root self.invertTree(root.left) self.invertTree(root.right) root.left, root.right = root.right, root.left return root Why this fails The condition below causes the function to return too early: if not root.left or not root.right: return root This stops recursion whenever a n...

Maximum Depth of Binary Tree (LeetCode 104) When I started solving tree problems, I had absolutely no idea how to approach them. This was my first tree problem, so I initially watched a YouTube video to understand the intuition. After that, I explored three different ways to solve the problem. In this post, I’ll explain all three approaches in a simple and beginner-friendly manner. 📌 Problem Statement Given the root of a binary tree, return its maximum depth. Maximum Depth is the number of nodes along the longest path from the root node down to the farthest leaf node. 🧠 Approach 1: Recursive Depth-First Search (DFS) This is the most natural way to solve tree problems because trees are recursive by nature. For every node, we calculate the depth of its left and right subtrees and take the maximum. class Solution: def maxDepth(self, root): if not root: return 0 return 1 + max(self.maxDepth(root.left), self.maxD...

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

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

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

Problem Background While solving the Continuous Subarray Sum problem on LeetCode, I initially felt confident because the word subarray immediately triggered my sliding window intuition. I had been practicing two pointers and sliding window patterns consistently, so my brain naturally tried to force that approach here. Why Sliding Window Failed for Me I tried hard to find a condition to either expand or shrink the window. But no matter how I looked at it, something felt off. The sum does not behave monotonically There is no clear rule to shrink the window Checking divisibility by k gives no directional hint That’s when I realized this problem does not belong to the sliding window family. The confusion I was facing was actually a signal that I was applying the wrong pattern. The YouTube Insight That Changed Everything After watching a YouTube tutorial focused only on intuition, one key idea finally clicked: If the same remainder appears again while taking pre...

Problem Overview The problem Subarray Sum Equals K asks us to find the total number of continuous subarrays whose sum is equal to a given value k . At first glance, this looks like a simple array problem, but it becomes tricky because: Subarrays must be continuous Elements can be negative A brute force approach would be too slow Brute Force Thinking The most straightforward approach is to try all possible subarrays and check their sums. However, this takes O(n²) time, which leads to a Time Limit Exceeded (TLE) for large inputs. This forced me to look for an optimized approach that avoids recomputing sums again and again. Key Insight: Prefix Sum Instead of recalculating subarray sums, we can store cumulative sums. Let prefixSum[i] represent the sum of elements from index 0 to i . If the sum of a subarray from index j+1 to i is equal to k , then: prefixSum[i] − prefixSum[j] = k Rearranging this gives: prefixSum[j] = prefixSum[i] − k T...