Road2Geeks

Introduction The House Robber problem is a classic Dynamic Programming question that frequently appears in coding interviews and online platforms like LeetCode. At first glance, the problem looks simple, but many intuitive approaches fail once edge cases are introduced. In this article, we’ll explore: Why a simple greedy or pattern-based solution does not work The correct Dynamic Programming (DP) approach A space-optimized solution Problem Statement (LeetCode 198) You are given an integer array nums where each element represents the amount of money in a house. You cannot rob two adjacent houses. Your task is to return the maximum amount of money you can rob without alerting the police. Initial Intuition (Why It Fails) A common first thought is to sum all houses at even indices and compare it with the sum of houses at odd indices. While this may work for some cases, it fails because the optimal solution is not restricted to fixed index parity. For examp...

Problem Overview LeetCode 70, Climbing Stairs , is a classic dynamic programming problem. You are given an integer n representing the number of steps to reach the top. At each step, you can either climb 1 step or 2 steps . The task is to find the total number of distinct ways to reach the top. Key Observation To reach step n , you can come from: Step n - 1 (taking 1 step) Step n - 2 (taking 2 steps) This leads to the recurrence relation: ways(n) = ways(n-1) + ways(n-2) This is exactly the same pattern as the Fibonacci sequence . Base Cases n = 1 → 1 way n = 2 → 2 ways For values greater than 2, we compute the answer iteratively. Optimized Approach (O(1) Space) Instead of storing all previous results in an array, we only keep track of the last two values. This reduces space complexity while keeping the logic efficient. Python Code class Solution: def climbStairs(self, n: int) -> int: if n < 3: return ...

📌 Problem Overview LeetCode 295, Find Median from Data Stream , asks us to design a data structure that efficiently supports: addNum(num) – add a number from the data stream findMedian() – return the median of all elements so far The challenge is not correctness, but performance . The operations may be called up to 10⁵ times , so naive approaches often lead to Time Limit Exceeded (TLE) . ❌ Why a Sorted Linked List Causes TLE A common first attempt is to maintain a sorted doubly linked list : Traverse the list to find the correct position Insert the number while keeping the list sorted Walk from both ends to compute the median ⏱ Time Complexity Operation Time Complexity addNum() O(n) findMedian() O(n) With up to 100,000 operations, this approach degrades to O(n²) overall, which is why it results in TLE on LeetCode. ✅ Optimal Approach: Two Heaps The correct and accepted solution uses two heaps ...

LeetCode 973 — K Closest Points to Origin Below are two Python implementations from my GitHub repository showing different approaches: Version 1 (Sort-based) This solution sorts all points by distance from the origin and returns the first k : # LC973_V1.py # https://github.com/RohitSingh-04/Python-Solutions/blob/main/LC973_V1.py class Solution: def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]: buffer = [(point[0]**2 + point[1]**2, index) for index, point in enumerate(points)] buffer.sort(key=lambda x: x[0]) answer = [points[buffer[i][1]] for i in range(k)] return answer 👉 View full file on GitHub: LC973_V1.py Version 2 (Heap-based) This version uses a heap to maintain the k closest points efficiently: # LC973_V2.py # https://github.com/RohitSingh-04/Python-Solutions...

Problem Overview The task is to find the kth largest element in an unsorted array. Although sorting the array would work, it requires O(n log n) time, which is inefficient for this problem. Heap-based solutions allow us to optimize this process by partially ordering elements instead of fully sorting the array. Approach 1: Min-Heap of Size k This approach maintains a min-heap that stores only the k largest elements seen so far. Key Idea Use a min-heap Keep heap size limited to k The smallest element in the heap is the kth largest overall Algorithm Steps Initialize an empty min-heap Traverse the array If heap size is less than k , push the element Otherwise, push the new element and remove the smallest one After traversal, the heap root is the answer Python Code import heapq class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: min_heap = [] for num in nums: if len(min_heap) < k:...

Clone Graph Problem – DFS Based Solution in Python The Clone Graph problem is a classic graph traversal question where the goal is to create a deep copy of a connected undirected graph. Each node contains a value and a list of its neighboring nodes. The challenge lies in correctly handling cycles and repeated references without creating duplicate nodes or falling into infinite recursion. Problem Overview You are given a reference to a node in a connected undirected graph. Each node has: An integer value val A list of neighboring nodes neighbors Your task is to return a deep copy of the entire graph. Key Insight Graphs can contain cycles, meaning a node can be revisited during traversal. To avoid cloning the same node multiple times, we use a hash map to keep track of already cloned nodes. This solution uses Depth First Search (DFS) with a dictionary called visited : Key → Original node Value → Cloned node DFS-Based Cloning Strate...

Rotting Oranges in Python: DFS vs BFS Explained The Rotting Oranges problem (LeetCode 994) is a classic grid traversal challenge. The task is to determine how many minutes it takes to rot all fresh oranges in a grid given that rotten oranges rot their neighbors in 4 directions every minute. In this article, we will walk through two different approaches to solve this problem in Python: A recursive DFS approach that tracks minimum rot times An optimized and efficient BFS approach using a queue 1. DFS Approach The DFS solution recursively spreads the “rot” from every rotten orange and uses a matrix to keep track of the minimum time taken for each orange to rot. This avoids revisiting oranges unnecessarily and ensures that only the shortest path is used. You can find the complete code here: DFS Solution (LC994_V1.py) class Solution: def rotOranges(self, i, j, itr): if i = self.m or j >= self.n or self.grid[i][j] == 0 or itr > self.answer[i]...

How to Solve “Number of Islands” Using Flood Fill and Graph Traversal When solving grid-based problems, it often feels confusing when explanations suddenly label the problem as a “graph problem” even though no graph is visible. This article explains the Number of Islands problem by connecting it to a much more intuitive idea — the 4-connected flood fill algorithm commonly taught in computer graphics. Problem Overview You are given a 2D grid containing "1" (land) and "0" (water). An island is formed when land cells are connected horizontally or vertically. The task is to count how many such islands exist in the grid. Input: [ ["1","1","0","0"], ["1","0","0","1"], ["0","0","1","1"], ["0","1","0","0"] ] Output: 3 Thinking in Terms of Flood Fill If you have previously implemented floo...

🔍 Problem Overview The task is to find the k-th smallest element in a Binary Search Tree (BST). At first glance, this problem may look like a simple tree traversal problem, but the key insight lies in understanding the special property of a BST. In a BST, an inorder traversal (Left → Root → Right) always visits nodes in sorted order . This property allows us to avoid unnecessary sorting and directly access the k-th smallest element during traversal. 💡 Initial Thought Process My first approach was straightforward: Traverse the entire tree Store all values in a list Sort the list Return the k-th smallest element While this works for any binary tree, it is inefficient for a BST. Once I realized the tree is a BST, I shifted my approach to use inorder traversal, which naturally gives sorted values. 🌳 Recursive Inorder Traversal Approach The idea is to perform an inorder traversal and count nodes as they are visited. Once the count reaches k , we store ...

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?

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