dsa2 min read
Jump Game II [Medium] — Greedy BFS-Level Jumps
Find minimum number of jumps to reach the last index using greedy BFS-style level tracking.
Read →
Bfs
83 articles
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 →
dsa3 min read
Trapping Rain Water II
Calculate trapped water in a 3D height map using BFS with a min-heap to process cells from shortest boundary inward.
Read →
dsa1 min read
Kth Largest Sum in a Binary Tree
Find the kth largest level sum in a binary tree using BFS to compute level sums then sorting or using a heap.
Read →
dsa1 min read
Rotting Oranges — Multi-Source BFS
Find minutes until all oranges rot using multi-source BFS starting from all initially rotten oranges simultaneously.
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
Course Schedule — Topological Sort BFS (Kahns Algorithm)
Detect if all courses can be finished (no cycle) using Kahn's algorithm: BFS on in-degree zero nodes.
Read →
dsa1 min read
Course Schedule II — Topological Order via BFS
Return a valid course order using Kahn's BFS topological sort, or empty array if a cycle exists.
Read →
dsa2 min read
Word Ladder — BFS Shortest Transformation Path
Find the shortest word transformation sequence using BFS where each step changes exactly one character.
Read →
dsa2 min read
Pacific Atlantic Water Flow — Reverse BFS from Both Oceans
Find cells that can flow to both oceans by doing reverse BFS from each ocean's borders and finding the intersection.
Read →
dsa1 min read
Walls and Gates — Multi-Source BFS from All Gates
Fill each empty room with its distance to nearest gate using simultaneous multi-source BFS from all gates.
Read →
dsa1 min read
Serialize and Deserialize Binary Tree — BFS Level Order
Serialize a binary tree to a string using BFS level-order and deserialize back using a queue for reconstruction.
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
Binary Tree Level Order Traversal — BFS Queue
Return values grouped by level using BFS with a queue, processing each level in a batch loop.
Read →
dsa1 min read
Binary Tree Zigzag Level Order — Alternating Direction BFS
Traverse a binary tree in zigzag level order by toggling insertion direction at each level.
Read →
dsa1 min read
Binary Tree Right Side View — BFS Last Element Per Level
Find the rightmost node at each level using BFS and taking the last element seen at each depth.
Read →
dsa2 min read
Populating Next Right Pointers in Each Node
Connect each node to its next right node using BFS level order or O(1) space pointer manipulation.
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 →
dsa3 min read
Maximum Width of Binary Tree
Find the maximum width of a binary tree where width is measured from leftmost to rightmost non-null node per level.
Read →
dsa2 min read
Vertical Order Traversal of a Binary Tree
Group tree nodes by vertical column then row, sorting by value within same position using BFS with coordinates.
Read →
dsa2 min read
Check Completeness of a Binary Tree
Verify a binary tree is complete using BFS: once a null child is seen, no more non-null nodes should follow.
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
N-ary Tree Level Order Traversal
Perform level-order traversal of an N-ary tree using BFS, collecting all children at each level.
Read →
dsa2 min read
Maximum Level Sum of a Binary Tree
Find the level with the maximum sum using BFS level-order traversal to compute each level's total.
Read →
dsa2 min read
Amount of Time for Binary Tree to Be Infected
Find time for infection to spread through entire tree from a start node by converting to graph then doing BFS.
Read →
dsa3 min read
Minimum Number of Operations to Sort Binary Tree by Level
Find minimum swaps to sort each level of a binary tree using BFS and cycle-detection in permutation sorting.
Read →
dsa2 min read
Add One Row to Tree
Insert a new row of nodes at a given depth in a binary tree using BFS to reach the target depth level.
Read →
dsa1 min read
Deepest Leaves Sum
Sum all nodes at the deepest level of a binary tree using BFS to process level by level.
Read →
dsa2 min read
Cousins in Binary Tree
Determine if two nodes are cousins (same depth, different parents) using BFS to track depth and parent.
Read →
dsa3 min read
Remove Invalid Parentheses and Expression Parsing
Remove minimum invalid parentheses to produce all valid results. BFS approach for minimum removals, DFS for complete enumeration.
Read →
dsa2 min read
A* Search — Heuristic Shortest Path for Grid Problems
A* combines Dijkstra's correctness with a heuristic to guide search toward the goal. Uses f(n)=g(n)+h(n) priority. Optimal when heuristic is admissible.
Read →
dsa1 min read
Graph Coloring and Bipartite Check
Check if a graph is bipartite using BFS 2-coloring. A graph is bipartite if and only if it contains no odd-length cycles — equivalent to being 2-colorable.
Read →
dsa1 min read
Path with Minimum Maximum Weight — Binary Search + BFS
Find the path from source to destination minimising the maximum edge weight. Binary search on the answer + BFS/DFS connectivity check. O(E log W) total.
Read →
dsa2 min read
Network Flow Concepts — Max Flow and Min Cut Overview
Introduction to network flow: max flow problem, Ford-Fulkerson algorithm with BFS (Edmonds-Karp), max-flow min-cut theorem, and applications in matching and connectivity.
Read →
dsa3 min read
Google — Alien Dictionary (Topological Sort on Characters)
Derive character ordering from a sorted alien dictionary using topological sort. Build a directed graph from adjacent word comparisons and apply Kahn's BFS algorithm.
Read →
dsa2 min read
Meta — Serialize and Deserialize Binary Tree (BFS/Preorder)
Serialize a binary tree to a string and deserialize it back. Meta loves this problem for testing tree traversal and string parsing. Both BFS and preorder DFS approaches shown.
Read →
dsa2 min read
Meta — Binary Tree Right Side View (BFS Level Order)
Return the values visible from the right side of a binary tree — the last node of each BFS level. O(n) BFS with level tracking.
Read →
dsa2 min read
Google — Trapping Rain Water II (3D BFS + Min-Heap)
Calculate how much water can be trapped in a 3D height matrix. Uses a min-heap BFS starting from the boundary, always processing the lowest border cell to determine water trapped inside.
Read →