Road2Geeks

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