dsa2 min read
Word Search [Medium] — DFS Backtracking on Grid
Search for a word in a 2D grid using DFS backtracking with in-place visited marking.
Read →
Dfs
95 articles
dsa1 min read
Array Nesting [Medium] — Cycle Length Tracking
Find the longest nested set S(k) in a permutation array by tracing cycles with visited marking in O(n) time.
Read →
dsa6 min read
BFS & DFS on Graphs and Grids — Complete Guide
Master BFS and DFS on graphs and grids: islands, flood fill, shortest paths, connected components, and multi-source BFS with 5-language implementations.
Read →
dsa2 min read
Number of Islands — DFS/BFS Flood Fill
Count connected land components in a binary grid using DFS flood fill or BFS. Classic easy problem, foundation for all island variants.
Read →
dsa2 min read
Flood Fill — DFS Color Replace
Implement the flood fill algorithm (like paint bucket tool): replace all cells of the same color reachable from a starting cell.
Read →
dsa2 min read
Island Perimeter — Grid Edge Counting
Calculate the perimeter of an island in a binary grid. Each land cell contributes 4 edges minus 2 for each land neighbour.
Read →
dsa2 min read
Max Area of Island — DFS with Area Count
Find the maximum area of any island in a binary grid. DFS returns the area of each island, track the maximum.
Read →
dsa2 min read
Surrounded Regions — Boundary DFS
Capture all 'O' regions not connected to the border. Classic boundary DFS: mark safe cells from edges, then flip remaining O to X.
Read →
dsa2 min read
Rotting Oranges — Multi-Source BFS
Find minimum minutes until all oranges rot. Multi-source BFS: push all initially-rotten oranges into queue simultaneously, BFS layer by layer.
Read →
dsa1 min read
01 Matrix — Distance to Nearest 0 (Multi-Source BFS)
For each cell find distance to nearest 0. Multi-source BFS from all 0s simultaneously gives optimal O(m*n) solution.
Read →
dsa1 min read
Walls and Gates — Multi-Source BFS from Gates
Fill each empty room with distance to nearest gate. Multi-source BFS from all gates (0) simultaneously, walls (-1) are barriers.
Read →
dsa1 min read
Number of Enclaves — Boundary DFS Count
Count land cells that cannot reach the border. Boundary DFS marks all reachable land from borders, then count remaining land cells.
Read →
dsa2 min read
Count Sub Islands — DFS Subset Check
Count islands in grid2 that are subsets of islands in grid1. DFS the island in grid2 and verify every cell is also land in grid1.
Read →
dsa1 min read
Making a Large Island — DFS Color Map + Merge
Find the largest island after flipping exactly one 0 to 1. Color each island with DFS, store sizes, then check each 0 cell's unique neighbour islands.
Read →
dsa1 min read
Pacific Atlantic Water Flow — Two-Source DFS
Find cells that can flow to both Pacific and Atlantic oceans. Run DFS backwards from each ocean border, find intersection.
Read →
dsa1 min read
Shortest Path in Binary Matrix — BFS 8-Directional
Find shortest clear path from top-left to bottom-right in binary matrix using 8-directional BFS. Return path length or -1.
Read →
dsa1 min read
As Far from Land as Possible — Multi-Source BFS
Find the water cell farthest from any land. Multi-source BFS from all land cells gives each water cell its min distance to land.
Read →
dsa2 min read
Word Search — DFS with Backtracking
Search for a word in a grid by moving to adjacent cells without reuse. DFS with backtracking: mark visited, recurse, unmark.
Read →
dsa1 min read
Number of Distinct Islands — DFS Shape Hashing
Count islands with distinct shapes. Encode each island's DFS traversal path as a string to capture shape, store in a set.
Read →
dsa1 min read
Number of Closed Islands — Boundary DFS + Count
Count islands fully surrounded by water (no border touch). Flood-fill border land first, then count remaining connected land components.
Read →
dsa1 min read
Shortest Bridge — DFS Find + BFS Expand
Find minimum flips to connect two islands. DFS to find and color first island, then BFS outward until reaching second island.
Read →
dsa2 min read
Minimum Effort Path — Dijkstra / Binary Search + BFS
Find path from top-left to bottom-right minimizing maximum absolute difference between consecutive cells. Use Dijkstra or binary search + BFS.
Read →
dsa2 min read
Number of Islands II — Union-Find Online Queries
Count islands after each addLand operation. Online version requires Union-Find: add each land cell and union with adjacent land cells.
Read →
dsa2 min read
Clone Graph — BFS/DFS with HashMap
Deep copy an undirected graph. BFS/DFS with a HashMap from original node to cloned node prevents revisiting and handles cycles.
Read →
dsa1 min read
Number of Provinces — DFS on Adjacency Matrix
Count connected components in an undirected graph given as adjacency matrix. DFS or Union-Find both work.
Read →
dsa1 min read
Keys and Rooms — DFS/BFS Graph Reachability
Determine if all rooms are reachable. Start from room 0, DFS using keys found in each room to unlock new rooms.
Read →
dsa1 min read
Find if Path Exists in Graph — BFS/Union-Find
Check if a path exists between source and destination in an undirected graph. BFS from source or Union-Find both work in O(V+E).
Read →
dsa1 min read
Nearest Exit from Entrance in Maze — BFS
BFS from entrance in a maze to find nearest exit (border empty cell). Classic BFS shortest path with exit condition.
Read →
dsa1 min read
Snakes and Ladders — BFS on Board State
Minimum dice rolls to reach square n^2. Convert board position to 2D coordinates (Boustrophedon order), BFS on board states.
Read →
dsa1 min read
Open the Lock — BFS State Space
Minimum turns to reach target combination avoiding deadends. BFS over all 4-digit wheel states with bidirectional BFS optimization.
Read →
dsa1 min read
Jump Game III — BFS/DFS Reachability
Check if you can reach a 0 in the array by jumping arr[i] steps left or right. BFS/DFS from start index.
Read →
dsa2 min read
Course Schedule — Cycle Detection BFS/DFS
Determine if you can finish all courses given prerequisites. Equivalent to detecting a cycle in a directed graph using BFS (Kahn) or DFS coloring.
Read →
dsa1 min read
Course Schedule II — Topological Order
Return a valid course order given prerequisites. Kahn's BFS topological sort outputs nodes in processing order — that is the valid schedule.
Read →
dsa1 min read
Graph Valid Tree — Cycle + Connected Check
Check if n nodes and edges form a valid tree: must be connected and acyclic. Exactly n-1 edges, all connected via BFS/DFS or Union-Find.
Read →
dsa1 min read
Connected Components — Union-Find / BFS
Count connected components in an undirected graph. Union-Find or BFS both give O(V+E) solution.
Read →
dsa1 min read
Redundant Connection — Union-Find Cycle Detection
Find the edge that creates a cycle in an undirected graph that started as a tree. Process edges with Union-Find; the first edge whose endpoints share a root is redundant.
Read →
dsa1 min read
All Paths Source to Target — DFS Backtracking
Find all paths from node 0 to node n-1 in a DAG. DFS with backtracking: explore each path, add to results when destination reached.
Read →
dsa1 min read
Network Delay Time — Dijkstra Shortest Paths
Find time for signal to reach all nodes. Single-source shortest path (Dijkstra) from node k; answer is max of all shortest distances.
Read →
dsa1 min read
Cheapest Flights Within K Stops — Bellman-Ford / BFS
Find cheapest flight from src to dst with at most k stops. Bellman-Ford with k+1 iterations or BFS level-by-level.
Read →
dsa2 min read
Word Ladder — BFS Shortest Transformation
Find minimum transformations from beginWord to endWord changing one letter at a time (each intermediate must be in wordList). Classic BFS on word states.
Read →
dsa1 min read
Word Ladder II — BFS Shortest Paths + DFS Reconstruct
Find ALL shortest transformation sequences. BFS builds layer map, DFS reconstructs all paths backwards from endWord to beginWord.
Read →
dsa1 min read
Bus Routes — BFS on Route Graph
Find minimum buses to get from source to target stop. BFS where nodes are routes (buses), not stops. Jump to all stops of a route, then to all routes passing through each stop.
Read →
dsa1 min read
Possible Bipartition — Bipartite Check BFS/DFS
Check if people can be split into two groups with no dislikes within a group. Equivalent to bipartite check on dislikes graph.
Read →
dsa1 min read
Is Graph Bipartite — BFS 2-Coloring
Check if a graph can be 2-colored such that no adjacent nodes share a color. BFS/DFS 2-coloring on all connected components.
Read →
dsa1 min read
Minimum Jumps to Reach Home — BFS with State
BFS with (position, last_jumped_back) state to find min jumps home avoiding forbidden positions. State space BFS avoids revisiting same position+direction.
Read →
dsa1 min read
Evaluate Division — Weighted Graph BFS/DFS
Evaluate queries like A/C = A/B * B/C. Build weighted directed graph from equations, BFS/DFS to multiply edge weights along paths.
Read →
dsa1 min read
Reachable Nodes in Subdivided Graph — Dijkstra
Count total reachable nodes in a subdivided graph within M moves. Dijkstra from node 0 gives max remaining moves at each node; use those to count subdivisions.
Read →
dsa3 min read
BFS & DFS Graphs — Master Recap & Cheatsheet
Complete cheatsheet for BFS and DFS on graphs and grids: 7 patterns, complexity table, common pitfalls, and problem index.
Read →
dsa2 min read
Two Sum IV - BST — Hash Set + In-Order Traversal
Find if a BST contains two nodes summing to target using a hash set during DFS traversal.
Read →
dsa2 min read
Flatten Multilevel Doubly Linked List — DFS Stack
Flatten a multilevel doubly linked list by inserting child sub-lists inline using DFS or an explicit stack.
Read →
dsa1 min read
Number of Islands — BFS or DFS Flood Fill
Count islands in a 2D grid using BFS or DFS to flood-fill connected land cells, marking them visited.
Read →
dsa1 min read
Maximum Depth of Binary Tree — DFS and BFS Approaches
Find the maximum depth of a binary tree using recursive DFS (one line) or iterative BFS level counting.
Read →
dsa1 min read
Invert Binary Tree — Recursive Swap
Invert a binary tree by recursively swapping left and right children at every node.
Read →
dsa1 min read
Symmetric Tree — Mirror Recursion
Check if a binary tree is symmetric by comparing mirror subtrees with a two-pointer recursive approach.
Read →
dsa1 min read
Path Sum — Root-to-Leaf DFS with Running Remainder
Determine if a root-to-leaf path exists with a given sum using DFS that subtracts each node value from the target.
Read →
dsa1 min read
Same Tree — Structural and Value Comparison
Check if two binary trees are identical by recursively comparing structure and node values.
Read →
dsa1 min read
Balanced Binary Tree — Height DFS with Early Exit
Check if a binary tree is height-balanced by computing subtree heights and returning -1 early on imbalance.
Read →
dsa1 min read
Merge Two Binary Trees — Recursive Overlay
Merge two binary trees by adding overlapping node values recursively, using existing nodes where possible.
Read →
dsa1 min read
Range Sum of BST — BST Property Pruning DFS
Sum all BST values in [low, high] using BST property to prune entire subtrees outside the range.
Read →
dsa1 min read
Path Sum II — DFS Backtracking All Paths
Collect all root-to-leaf paths with a given sum using DFS backtracking, appending and removing the current node.
Read →
dsa1 min read
Diameter of Binary Tree — Tree DP Height Trick
Find the diameter (longest path between any two nodes) using a depth function that tracks the maximum path through each node.
Read →
dsa1 min read
Validate Binary Search Tree — Min/Max Bounds DFS
Validate a BST by passing down min and max bounds through DFS, ensuring every node falls strictly within its valid range.
Read →
dsa1 min read
Lowest Common Ancestor of Binary Tree — Post-Order DFS
Find the LCA of two nodes using post-order DFS: return root when found, propagate upward and split at the ancestor.
Read →
dsa1 min read
Path Sum III — Prefix Sum HashMap on Tree
Count paths in a binary tree summing to target (not necessarily root-to-leaf) using a prefix sum frequency map.
Read →
dsa2 min read
Flatten Binary Tree to Linked List
Flatten a binary tree to a linked list in-place using pre-order traversal order.
Read →
dsa3 min read
All Nodes Distance K in Binary Tree
Find all nodes at distance K from a target node by building parent pointers then doing BFS.
Read →
dsa2 min read
Sum Root to Leaf Numbers
Compute the total sum of all root-to-leaf numbers formed by concatenating digits along each path.
Read →
dsa2 min read
Count Good Nodes in Binary Tree
Count nodes where no node on the root-to-node path has a value greater than the node itself.
Read →
dsa2 min read
Convert BST to Greater Tree
Replace each node value with the sum of all values greater than or equal to it using reverse in-order traversal.
Read →
dsa2 min read
Find Duplicate Subtrees
Find all duplicate subtrees by serializing each subtree and using a hash map to detect duplicates.
Read →
dsa3 min read
Step-By-Step Directions From a Binary Tree Node to Another
Find path directions between two tree nodes by finding LCA then building paths from LCA to each target.
Read →
dsa2 min read
Distribute Coins in Binary Tree
Count minimum moves to distribute coins evenly by tracking excess/deficit coins flowing through each edge.
Read →
dsa2 min read
Binary Tree Maximum Path Sum
Find the maximum path sum in a binary tree where the path can start and end at any node.
Read →
dsa2 min read
Serialize and Deserialize Binary Tree
Serialize a binary tree to string and back using BFS level-order or DFS preorder with null markers.
Read →
dsa2 min read
Find Leaves of Binary Tree
Collect leaves by height (distance from leaf) repeatedly, returning all leaves at each height level.
Read →
dsa2 min read
Minimum Time to Collect All Apples in a Tree
Find minimum seconds to collect all apples in a tree by DFS: include a subtree path only if it contains apples.
Read →
dsa2 min read
Maximum Difference Between Node and Ancestor
Find the maximum |a - b| for any ancestor-descendant pair by tracking min and max values along each root-to-leaf path.
Read →
dsa2 min read
Longest ZigZag Path in Binary Tree
Find the longest zigzag path in a binary tree where you alternate left-right directions at each step.
Read →
dsa3 min read
Sum of Distances in Tree
Compute sum of distances from every node to all others in O(n) using two DFS passes with rerooting technique.
Read →
dsa1 min read
Binary Tree Pruning
Remove all subtrees that do not contain a 1 by recursively returning null for subtrees with only zeros.
Read →
dsa2 min read
Smallest String Starting From Leaf
Find lexicographically smallest string from any leaf to root by collecting and comparing reversed paths.
Read →
dsa2 min read
Path Sum IV
Sum all root-to-leaf path sums in a tree encoded as 3-digit integers using a hashmap to decode tree structure.
Read →
dsa2 min read
Binary Tree Upside Down
Transform a binary tree so every right child becomes a sibling and left child becomes parent using iterative rotation.
Read →
dsa2 min read
Second Minimum Node In a Binary Tree
Find second minimum value in a special binary tree where root is min and each node equals min of its children.
Read →
dsa1 min read
Construct String from Binary Tree
Build a preorder string representation of a binary tree using parentheses to show tree structure.
Read →
dsa2 min read
N-ary Tree Preorder and Postorder Traversal
Traverse an N-ary tree in preorder and postorder using DFS with a stack or recursion.
Read →
dsa1 min read
Count Nodes Equal to Average of Subtree
Count nodes where node value equals the average of all values in its subtree using post-order DFS returning sum and count.
Read →
dsa1 min read
Design Add and Search Words — Trie with Wildcard DFS
Trie that supports wildcard '.' matching any character. DFS through trie when '.' encountered, trying all children.
Read →
dsa2 min read
Word Search II — Trie + Grid DFS Pruning
Find all words from a list in a grid. Build trie from words, DFS on grid while traversing trie simultaneously to prune early.
Read →
dsa2 min read
Tarjan's Algorithm — Strongly Connected Components
Find all strongly connected components in a directed graph using Tarjan's single-pass DFS algorithm with discovery time, low-link values, and a stack.
Read →
dsa2 min read
Bridges and Articulation Points — Graph Vulnerability Detection
Find all bridge edges and articulation point vertices in an undirected graph using a single DFS pass with discovery time and low-link tracking.
Read →
dsa2 min read
Reconstruct Itinerary — Hierholzer's Eulerian Path
Find the itinerary using all flight tickets exactly once (Eulerian path). Uses Hierholzer's algorithm: DFS with post-order insertion into result — the only graph algorithm that uses post-order for path construction.
Read →
dsa2 min read
Longest Path in DAG — Graph DP with Memoisation
Find the longest path in a directed acyclic graph using DFS with memoisation. Since cycles are absent, DFS never revisits nodes, making top-down DP straightforward.
Read →
dsa2 min read
Word Search Problems — Trie + Backtracking Patterns
Word Search I and II solved with DFS backtracking. Word Search II uses a Trie to prune the search space from O(N·4^L) per word to O(N·4^L) total for all words.
Read →
dsa2 min read
Meta — Clone Graph (Deep Copy with DFS/BFS + HashMap)
Create a deep copy of an undirected graph using DFS with a HashMap to track visited/cloned nodes. Meta tests this to evaluate graph traversal and pointer manipulation.
Read →