Road2Geeks

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