Graph, BFS, DFS and union find interview questions
30 coding interview questions on graphs, BFS, DFS, matrix traversal and union find, each with the correct answer and a full explanation.
Graphs, BFS and DFS
Grid BFS for shortest path, 1000 x 1000 open grid. The code marks a cell visited when it is popped. What happens?
Show answer
Answer
Cells are enqueued many times, blowing up time and memory
Until a cell is popped, every neighbour that sees it pushes another copy, so the queue holds many duplicates and often times out. The first pop still has the right distance, so results are correct but slow. It is not equivalent to marking on push. The queue is still FIFO, so it is not DFS.
Shortest path by edge count in an unweighted graph. Which is correct and fastest?
Show answer
Answer
BFS, O(V + E)
BFS explores in distance order, so the first visit is shortest. Plain DFS with a visited set can reach a node by a long path first and never revisit it. Dijkstra is correct but adds a log factor for no reason. Bellman Ford is correct and much slower.
Number of Islands on an m x n grid with DFS. What is the time complexity?
Show answer
Answer
O(m n)
Each cell is visited a constant number of times, with 4 neighbour checks. Squaring the cell count treats it like a dense graph. O(m + n) counts rows and columns, not cells. There is no sorting or heap.
Python recursive DFS on a 1000 x 1000 grid that is one big island. What goes wrong?
Show answer
Answer
RecursionError, since depth can reach about 106 and the default limit is 1000
CPython's default recursion limit is about 1000 frames, and a snake shaped island can make DFS depth near the cell count. Use an explicit stack or BFS. The count would be right if it finished. Visited marking prevents infinite loops. Python does not grow the stack automatically.
Rotting Oranges: every rotten orange spreads each minute. How do you get the minimum minutes?
Show answer
Answer
Push all rotten oranges into the queue first, then BFS by levels
Multi source BFS gives each cell its distance to the nearest source in O(m n). One BFS per source is O(k m n). DFS does not give shortest distances. Full rescans are O((m n)2) in the worst case.
Clone Graph: deep copy a connected undirected graph that has a cycle. What prevents infinite recursion and duplicate clones?
Show answer
Answer
A dict from original node to its clone, checked before creating
The map both marks visited and returns the existing clone so edges point to one copy. A set of values knows a node was seen but cannot hand back its clone, so edges cannot be wired. Cloning neighbours first still recurses forever on a cycle. Depth limits produce partial copies.
Pacific Atlantic Water Flow on an m x n height grid: water flows to equal or lower neighbours; find cells that reach both the Pacific (top and left edges) and the Atlantic (bottom and right edges). Which is O(m n)?
Show answer
Answer
BFS or DFS inward from each ocean's border going uphill, then intersect
Reversing the flow lets two searches cover all cells once each. Per cell DFS is O((m n)2). Sorting is O(m n log(m n)) and does not by itself decide reachability. Dijkstra adds weights that do not exist.
Surrounded Regions: flip O regions not connected to the border. What is the clean approach?
Show answer
Answer
Mark border connected O cells first, then flip all unmarked O
Marking from the border first identifies safe cells in O(m n). Restoring only border cells forgets interior cells connected to them. Unmarked per cell DFS repeats work and is O((m n)2). Union find works only with a virtual border node; without one you cannot tell which components touch the edge.
Undirected graph from an edge list, n up to 105. Which representation fits BFS in O(V + E)?
Show answer
Answer
Adjacency list, adding each edge in both directions
An adjacency list stores E entries and both directions are needed for undirected edges. A matrix is 1010 cells. One direction only makes v unable to reach u. Scanning the edge list per node is O(V E).
Word Ladder (fewest one letter changes from beginWord to endWord, each step a dictionary word): word length L, dictionary size N. Which neighbour generation is usually fastest when N is large?
Show answer
Answer
For each position, try all 26 letters and check a word set, O(26 L) per word
Generating candidates costs O(26 L) lookups (each O(L) to hash) independent of N. Comparing to every word is O(N L) per node. All pairs is O(N2 L). DFS does not give the shortest transformation.
Flood Fill (recolor the connected same color region around a start pixel): what edge case makes a naive DFS loop forever, and how do you guard it?
Show answer
Answer
If the new color equals the starting color, recoloring does not mark cells, so DFS revisits them forever. Return immediately when image[sr][sc] already equals color, or use a visited set.
Kahn's topological sort on Course Schedule II (order all courses so each prerequisite comes first). How do you detect a cycle?
Show answer
Answer
The output has fewer than n nodes
Nodes on a cycle never reach indegree 0, so they are never output. The queue always empties eventually. Indegree 0 at the start is normal. Kahn's never visits a node twice by construction.
Cycle detection in a directed graph with DFS. Why is a single visited set not enough?
Show answer
Answer
A node visited in an earlier finished branch is not a back edge; you need in progress and done states
Cross edges to finished nodes look like revisits but are not cycles. Three colors mark on stack nodes. A single set gives false positives on diamonds. Recursion is fine. Directed and undirected cycle rules differ.
Course Schedule: prerequisites [a, b] means take b before a. For Kahn's, which edge and indegree?
Show answer
Answer
Edge b to a, indegree[a] += 1
b must come first, so b points to a and a waits. Reversing the edge returns the reverse order, which is wrong for Course Schedule II. Mixing directions breaks the counts. Both directions turns every edge into a cycle.
Alien Dictionary (derive the letter order of an alien language from its words in sorted order): words ["abc", "ab"]. What is the answer?
Show answer
Answer
Invalid, return "" because a word precedes its own prefix
A longer word cannot come before its prefix in a sorted list, so the input is inconsistent. Returning a letter order ignores that check, a frequent miss.
Is Graph Bipartite, graph may be disconnected. What is commonly missed?
Show answer
Answer
Starting a BFS coloring from every uncolored node, not just node 0
A component never reached from node 0 can contain an odd cycle. Bipartite means two colors. Self loops are one case of odd cycles, not the whole check. Sorting is irrelevant.
Shortest Path in a Grid with Obstacles Elimination (up to k removals). What is the BFS state?
Show answer
Answer
(row, col, removals used)
Reaching a cell with fewer removals left is a different state. Visited by cell only prunes paths that would succeed. Steps are the BFS level, not part of identity. Removals alone forget position.
Evaluate Division: a / b = 2.0, b / c = 3.0, query a / c. How do you model it?
Show answer
Answer
Weighted directed graph with edges a to b weight 2 and b to a weight 0.5, multiply along a path
Ratios multiply along paths and reverse edges invert. Hop counts lose values. Sorting has no meaning. Plain union find tells connectivity but not the ratio; it needs weights.
Reconstruct Itinerary: build a route from JFK using every airline ticket once, with the smallest lexical order. Approach?
Show answer
Answer
Eulerian path with Hierholzer's algorithm: adjacency lists sorted (or min heaps), DFS popping the smallest destination, append the airport after its edges are exhausted, then reverse. Plain greedy smallest next can dead end.
Shortest paths with some negative edge weights and no negative cycles. Which is correct?
Show answer
Answer
Bellman Ford
Bellman Ford relaxes all edges V - 1 times and handles negatives. Dijkstra finalizes nodes early and can be wrong. BFS ignores weights. Adding a constant penalizes paths with more edges and changes which path is shortest.
Lazy Dijkstra with heapq. When you pop (d, u) and d > dist[u], what do you do?
Show answer
Answer
Skip it, it is a stale entry
heapq has no decrease key, so old entries remain and must be skipped. Relaxing from stale entries wastes work. Setting dist to a larger value is wrong. Stopping ends early.
Rotate an n x n matrix 90 degrees clockwise in place. Which works?
Show answer
Answer
Transpose, then reverse each row
Transpose plus row reverse is clockwise. Row reverse then transpose gives counterclockwise. Transpose plus column reverse is also counterclockwise. Swapping over all i and j swaps every pair twice and returns the original.
Set Matrix Zeroes (if a cell is 0, set its whole row and column to 0) in O(1) extra space using the first row and column as markers. What extra state is needed?
Show answer
Answer
One flag for whether the first column (or row) itself had a zero
matrix[0][0] can mark only one of row 0 or column 0, so one more flag is needed for the other. Without it, row 0 or column 0 is wrongly zeroed or missed. A set of rows is O(m) space. Copying the first row is O(n) space.
Spiral Matrix (return all cells in clockwise spiral order) on a 3 x 1 matrix. A boundary loop goes right, down, left, up and shrinks top, right, bottom, left. What bug outputs some cells twice?
Show answer
Answer
Not checking top <= bottom and left <= right before the left and up passes
For single row or column leftovers, the left and up passes revisit cells unless guarded. Shrinking top after the right pass is correct. Inclusive ranges are correct with inclusive bounds. Starting at [0][0] is correct.
Search a 2D Matrix where each row is sorted and each row's first value exceeds the previous row's last. Best time?
Show answer
Answer
O(log(m n)) treating it as one sorted array
The global ordering makes it a flat sorted array of m n cells, so one binary search works. The staircase is O(m + n), correct but slower and meant for the weaker ordering of LeetCode 240. Per row search ignores the cross row order. Scanning is O(m n).
Valid Sudoku (check that no row, column or 3 x 3 box of a partly filled 9 x 9 board repeats a digit): which index gives the 3 x 3 box of cell (r, c)?
Show answer
Answer
(r // 3) * 3 + c // 3
Row band times 3 plus column band gives 0 to 8. r // 3 + c // 3 collides (band 0,1 and 1,0). The modulo version gives position within a box, not the box. r * 3 + c is out of range.
Union find without path compression or union by rank on n elements. Worst case per find?
Show answer
Answer
O(n)
Unions can build a chain, so find walks n links. Inverse Ackermann needs both optimizations. O(log n) needs union by rank or size. O(1) is never guaranteed.
Redundant Connection: an undirected graph is a tree plus one extra edge. Return the removable edge that comes last in the input. With union-find over edges in order, which edge is it?
Show answer
Answer
The first edge whose endpoints already share a root
Processing edges in order, the first edge whose endpoints are already connected closes the only cycle, and it is the cycle edge that appears last in the input, which is what the problem asks for. The literal last input edge may not lie on the cycle. Any cycle edge is not unique, the problem wants the last one. Node labels are irrelevant.
Number of connected components with union find over n nodes and m edges. How do you get the count?
Show answer
Answer
Start at n and decrement on each successful union
Each union of distinct sets merges two components. parent entries may not be roots without find. Edge count says nothing directly. n - m is wrong when edges are redundant.
Accounts Merge (merge accounts that share any email into one person): what do you union?
Show answer
Answer
Emails within the same account, then group emails by root
Emails identify people, so emails in one account join and shared emails join accounts. Names collide across different people. Letters are meaningless. Input order is arbitrary.
Bertopia