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 →
Graphs
67 articles
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 →
RAG10 min read
GraphRAG — Combining Knowledge Graphs With Vector Search
Build GraphRAG systems using knowledge graph traversal and vector search together to handle complex multi-hop questions and relationship-aware context retrieval.
Read →
dsa2 min read
Advanced Graphs — Complete Guide (MST, SCC, Bridges, Floyd-Warshall, A*)
Master advanced graph algorithms: Kruskal and Prim MST, Tarjan SCC, articulation points, bridges, Floyd-Warshall all-pairs shortest path, and A* search.
Read →
dsa2 min read
Kruskal's Algorithm — Minimum Spanning Tree with Union-Find
Find the minimum spanning tree of a weighted graph using Kruskal's algorithm. Sort edges by weight, use Union-Find to avoid cycles. O(E log E) time.
Read →
dsa2 min read
Prim's Algorithm — MST via Min-Heap Greedy Expansion
Build the minimum spanning tree using Prim's algorithm: start from any vertex, greedily expand by always adding the minimum-weight crossing edge using a min-heap.
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
Floyd-Warshall — All-Pairs Shortest Path
Compute shortest paths between all pairs of vertices using Floyd-Warshall's O(V³) DP. Handles negative weights and detects negative cycles.
Read →
dsa2 min read
Bellman-Ford — SSSP with Negative Edges and Cycle Detection
Compute single-source shortest paths in graphs with negative weight edges using Bellman-Ford. V-1 relaxation passes detect negative cycles on the Vth pass.
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 →
dsa2 min read
Topological Sort — Advanced Applications (DFS, Kahn, Cycle Detection)
Advanced topological sort: DFS-based with 3-color marking for cycle detection, Kahn's BFS approach, and applications in course scheduling, build systems, and task ordering.
Read →
dsa2 min read
Dijkstra Advanced — Modified Dijkstra Patterns (K Stops, States, Constraints)
Advanced Dijkstra patterns: state-space Dijkstra for problems with extra constraints like K stops, fuel limit, or restricted nodes. The key is augmenting the state beyond just the node.
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
Minimum Cost to Connect All Points — Prim's on Complete Graph
Connect all n points with minimum total Manhattan distance cost. Models the problem as a complete graph MST and applies optimised Prim's without building all O(n²) edges explicitly.
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
Number of Ways to Arrive at Destination — Dijkstra + Count
Count the number of shortest paths from source to destination using modified Dijkstra that tracks both minimum distance and path count simultaneously.
Read →
dsa2 min read
Find Critical Connections in Network — Bridge Finding
LeetCode 1192: Find all critical edges (bridges) in a network. A connection is critical if removing it disconnects the network. Uses Tarjan's bridge algorithm.
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
Swim in Rising Water — Dijkstra / Binary Search + BFS
Find the minimum time to swim from (0,0) to (n-1,n-1) where you can only move to a cell when time >= cell value. Two approaches: Dijkstra O(n² log n) and binary search + BFS O(n² log n).
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
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
Advanced Graphs — Master Recap and Algorithm Selection Guide
Complete recap of all 20 advanced graph problems with algorithm selection guide, complexity comparison, and pattern recognition cues.
Read →