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 →
Graph
31 articles
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
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 →
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 →
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
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 →
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
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 →
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 →
dsa3 min read
Amazon — Number of Islands II (Union-Find Dynamic)
Count islands after each addLand operation using incremental Union-Find. Each new land cell potentially merges with up to 4 neighbors — classic Amazon system-at-scale problem.
Read →
dsa2 min read
Meta — Accounts Merge (Union-Find on Emails)
Merge accounts sharing common email addresses using Union-Find. Group emails by owner, merge accounts with shared emails, sort each merged group.
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 →