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