Graph Problems

Eight classic interview problems — Number of Islands, Max Area of Island, Clone Graph, Rotting Oranges, Course Schedule I and II, Connected Components and Graph Valid Tree, Word Ladder, and Network Delay Time — solved from zero. You will learn to see a grid as a graph, turn a list of edges into neighbour lists, explore with depth-first and breadth-first search, start a search from many places at once, order tasks that depend on each other, merge groups with union-find, and find the fastest route with Dijkstra's algorithm and a heap you write yourself. Every problem has an animation you can feed your own grid or graph, with the queue, stack, visited marks, in-degrees or distances drawn at each step.

Graphs, grids and the six graph tools

Some words first:

• A graph is a set of nodes (also called vertices — the dots) and edges (the lines joining two nodes). On this page nodes are numbered 0, 1, 2, …
• An edge is undirected when it works both ways (a two-way road, written 0-1) and directed when it works one way only (a one-way street, written 0->1). A weighted edge carries a number, such as a travel time (0->1:4).
• The neighbours of a node are the nodes one edge away. A path is a walk along edges. A cycle is a path that comes back to where it started.
• A connected component is a group of nodes that can all reach each other, with no edge leaving the group — one neighbourhood of the town.
• V is the number of nodes and E the number of edges. Most graph algorithms on this page cost O(V + E): they look at every node and every edge a fixed number of times. See C03 · Growth of Functions.

A grid is a graph in disguise

Many questions never say "graph". They give you a grid of numbers or letters instead — a map of land and water, a box of oranges, a maze. Treat every cell as a node, and join each cell to the cells directly up, down, left and right of it (four neighbours; diagonal cells are not neighbours unless the question says so). A cell in row r and column c is written (r, c), counting from 0. Before touching a neighbour, check that it is inside the grid: 0 ≤ nr < rows and 0 ≤ nc < cols. That check is the bounds check; forgetting it gives a RangeError on the first cell of the first row.

The four moves are stored as Dart records — small fixed groups of values like (-1, 0) — and unpacked with a pattern, for (final (dr, dc) in dirs). Records and patterns are explained in D11 · Records, Patterns & Sealed Classes. A grid with rows × cols cells has about 4 × rows × cols neighbour links, so a full search of a grid costs O(rows × cols).

From a list of edges to neighbour lists

Graph questions usually hand you the edges as pairs, like [[0, 1], [1, 2]]. To explore, you need the opposite view: for each node, the list of its neighbours. That is an adjacency list — a list with one bucket per node. Build it once in O(V + E), and every later "who are my neighbours?" question is answered instantly.

The visited mark

Graphs can contain cycles, and an undirected edge can be walked both ways, so a search that does not remember where it has been walks in circles forever. Every search keeps a visited mark per node (a List<bool>, a Set, or a distance list where −1 means "not yet"). The important question is when to set it. In breadth-first search, mark a node the moment you put it in the queue, not when you take it out — otherwise two neighbours can both add the same node before either takes it out, and it gets processed twice (question p09-q6 shows the wrong count this produces).

Breadth-first search (BFS): ripples on a pond

BFS explores in rings: first the start, then everything one edge away, then everything two edges away, and so on, like ripples spreading from a stone dropped in a pond. It keeps a queue — first in, first out, like a line at a ticket counter. Dart's Queue from dart:collection adds at the back and removes from the front in O(1); a plain List with removeAt(0) would shift every item each time (O(n)) — see D28 · Queue, ListQueue & LinkedList.

Because the rings go out one step at a time, the first time BFS reaches a node is along a path with the fewest edges. That is why BFS is the tool for "minimum number of steps" when every step costs the same.

Depth-first search (DFS): one corridor at a time

DFS is the explorer in a maze who always takes the first unexplored corridor, goes as deep as possible, and only backs up at a dead end. Written recursively it is very short — the call stack (the stack of waiting function calls, D07 · Functions & the Call Stack) remembers where to come back to. Written with your own stack (last in, first out; a Dart List with add and removeLast), it cannot run out of call-stack space on a huge grid. Both find the same nodes; DFS does not find shortest paths.

In the iterative version a node can be pushed more than once (two neighbours both push it before it is popped), so it checks seen when popping. Pushing the neighbours in reverse makes it visit them in the same order as the recursion — the verification program checks that on 400 random graphs.

The other four tools

1. Multi-source BFS. Put several starting nodes in the queue before the loop begins. The ripples spread from all of them at once, and each cell is reached first from its nearest start. (Rotting Oranges; distance to the nearest gate or zero, p09-q15 and p09-q20.)
2. Topological sort with in-degrees (Kahn's algorithm). For one-way "a before b" rules, count for every node how many arrows point into it — its in-degree. Nodes with in-degree 0 can go first. Taking one removes its outgoing arrows, which may free other nodes. If some nodes never reach in-degree 0, they sit on a cycle. (Course Schedule, alien dictionary p09-q23.)
3. Union-find (disjoint sets). Keeps groups of nodes, each with a root that names it. find(x) follows parent links to the root; union(a, b) joins two groups. With path compression and union by rank both are almost O(1). Answers "are these connected?" while edges keep arriving, and spots the edge that closes a cycle. (Connected Components, Graph Valid Tree, redundant connection p09-q16.)
4. Dijkstra's algorithm with a heap. For edges with different positive costs, BFS's rings no longer mean "cheapest". Dijkstra always finishes the closest unfinished node next, picking it from a min-heap (a structure that hands back the smallest item in O(log n)). (Network Delay Time, swim in rising water p09-q24.)

Dart has no heap in its core libraries — so write one

dart:core and dart:collection have no priority queue. The package:collection package does (HeapPriorityQueue), but interview pads and online judges often allow only the core libraries. A binary min-heap fits in thirty lines: items live in a list, the parent of index i is at (i − 1) ~/ 2, its children at 2i + 1 and 2i + 2, and every parent comes out no later than its children. push adds at the end and lets the item rise; pop takes index 0, moves the last item to the top and lets it sink. Both cost O(log n). The verification program checks this heap against List.sort on 300 random lists. The heap itself is built up step by step in C06 · Priority queues.

How to choose

Number of Islands

The task. You get a grid where 1 is land and 0 is water. An island is a group of land cells joined up, down, left or right (touching only at a corner does not count). Return how many islands there are.

Brute force. For every land cell, search its whole island from scratch and name the island after its first cell in reading order; then count the different names. Correct, but a big island is searched once for each of its cells: O((rows × cols)²).

Key insight. Remember what you have already explored. Scan the grid once; when you meet land that is not yet seen, add one to the count and flood the whole island with a BFS, marking each cell seen as you push it. Every later land cell of that island is skipped by the scan, so each cell is pushed at most once and looked at a few times in total.

Why it is correct. The count goes up exactly once per island: the first cell of the island the scan meets starts a search, that search reaches every cell joined to it (BFS reaches everything reachable), and from then on every cell of that island is seen, so no other cell of it can start another search.

An edge case: a grid with no land at all. The scan looks at every cell, never finds land, and the count stays 0.

Complexity. Time O(rows × cols) — the scan visits each cell once, and each land cell is pushed and popped once, checking four neighbours. Space O(rows × cols) for the seen grid (the queue holds at most about rows + cols cells at a time for a BFS on a grid, but the seen grid dominates). You may instead overwrite land with 0 ("sink" it) to save the extra grid — only if the caller allows changing the input.

Follow-ups interviewers ask. Count with union-find instead (the verification program does — each union of two neighbouring land cells removes one island). Land is added one cell at a time and you must report the count after each addition: union-find again, since a search per addition is too slow. Count the islands whose cells are all away from the border (p09-q13 uses the same border trick). Find the perimeter of the one island (p09-q5).

The idea underneath: breadth-first search in C22 · Breadth-first search, and connected components with union-find in C21 · Connected components.

Max Area of Island

The task. Same kind of grid: 1 is land, 0 is water, and islands are joined up, down, left or right. The area of an island is how many land cells it has. Return the largest area, or 0 if there is no land.

Brute force. Search the island of every land cell from scratch and keep the biggest size found. A field of a hundred squares is walked a hundred times.

Key insight. It is Number of Islands with a counter. While flooding an island, add one each time a cell comes off the stack; when the stack is empty, that counter is the island's area. Here the search uses a stack (DFS) instead of a queue — the order of visiting does not matter for an area, only that every cell is visited once.

An edge case: the empty grid. There is no first row, so the code must not read grid[0]; it returns 0 straight away.

The recursive version — and its danger. The shortest code asks "the area at (r, c) is 1 plus the area of its four neighbours", with off-grid, water and already-seen cells giving 0. It is correct and pleasant to write, but every recursive call waits on the call stack. On a big island shaped like a long snake the recursion goes one call deeper per cell; the verification program shows that on a 1000 × 1000 grid of land Dart's VM throws a StackOverflowError, while the stack version above finishes.

Complexity. Time O(rows × cols); space O(rows × cols) for seen plus the stack, which in the worst case (one island covering everything) can hold a large share of the cells.

Follow-ups interviewers ask. Turn at most one water cell into land: what is the largest island you can make? (Label every island with an id and its area, then for each water cell add up the areas of the different islands around it.) Return the island's cells, not only its size. Count the land cells that cannot reach the border (enclaves — the border trick of p09-q13).

The idea underneath: depth-first search in C22 · Depth-first search; the explicit stack is the one built in C10 · Stacks, Queues, Linked Lists, Trees.

Clone Graph

The task. You get one node of a connected undirected graph. Each node has a value and a list of neighbours. Build a deep copy: brand-new node objects with the same values and the same pattern of edges, so that changing the copy never touches the original. Return the copy of the node you were given.

The first idea, and why it fails. Copy a node, then copy each neighbour the same way. On any cycle — even a single edge, since an undirected edge is a cycle of length two — the copying goes 0 → 1 → 0 → 1 → … and never stops. The verification program shows it ending in a StackOverflowError on just two nodes.

Key insight. Keep a map copyOf from each original node to its copy. The map does two jobs at once: it is the visited set (a node is in the map once it has been met) and it lets you find a neighbour's copy when wiring an edge. Walk the graph with BFS; for each edge u → v, make v's copy if it does not exist yet, then add copyOf[v] to copyOf[u]'s neighbours.

Dart detail: GraphNode does not override == or hashCode, so a Map<GraphNode, GraphNode> compares keys by identity — two different nodes holding the same value are still different keys, which is exactly right here. See D29 · Object (==, hashCode).

An edge case: the graph you are given only part of. Nodes 3 and 4 below are not connected to node 0, so a search from 0 never meets them and the copy has only three nodes. That is correct — "the graph" in this task means everything reachable from the given node.

Complexity. Time O(V + E) — each node is taken from the queue once, and each of its edges is wired once (an undirected edge is wired twice, once from each end). Space O(V) for the map and the queue, plus the copy itself.

Follow-ups interviewers ask. Do it with DFS (recursive: create the copy, put it in the map before visiting neighbours). Copy a linked list whose nodes also point at random nodes — the same map idea (Step 13.6 · Linked List Problems). Copy a directed graph that may not be connected: start a copy from every node not yet in the map.

The idea underneath: BFS with a visited map, C22 · Breadth-first search; references versus copies in D22 · Mutable vs Immutable.

Rotting Oranges

The task. A box is a grid of cells: 0 is empty, 1 is a fresh orange, 2 is a rotten orange. Every minute, each fresh orange that touches a rotten one (up, down, left or right) turns rotten. Return how many minutes pass until no fresh orange is left, or −1 if some fresh orange can never rot.

Brute force. Replay the world: each minute, scan the whole box, find every fresh orange next to a rotten one, rot them all together, and count the minute. Stop when no fresh orange is left, or when a minute changes nothing (then the answer is −1). Each minute costs a full scan.

Key insight. This is BFS with many starting points. Put every rotten orange into the queue before the loop starts. Then process the queue one level at a time: the oranges in the queue when a minute begins are exactly the ones that spread during that minute, and the oranges they rot form the next level. Counting levels counts minutes. Keep a fresh counter, so at the end you know at once whether any orange was never reached.

The level trick in Dart: read queue.length once, into the loop variable, before taking anything out — for (var k = queue.length; k > 0; k--). Oranges added during the minute go behind that count and wait for the next minute.

An edge case: an orange nobody can reach. The rot spreads as far as it can, the queue empties, and fresh is still 1, so the answer is −1.

Complexity. Time O(rows × cols) — every orange enters the queue at most once. Space O(rows × cols) for the queue and the copy of the grid.

Follow-ups interviewers ask. Distance from every room to its nearest gate (p09-q15) and from every cell to its nearest 0 (p09-q20) — the same multi-source BFS. Some cells are walls the rot cannot cross: they are simply not fresh oranges. Return which orange rots last: remember the last cell taken from the queue.

The idea underneath: BFS distances from a set of sources, C22 · Breadth-first search (adding a fake "super source" joined to every start gives the same result).

Course Schedule I and II

The task. There are n courses numbered 0 to n − 1, and a list of pairs [a, b], each meaning "course a must be finished before course b". Part I: return true if every course can be finished. Part II: return one order in which to take all the courses, or an empty list if it is impossible. (Some versions write each pair the other way round, as [course, what it needs]; read the statement carefully and flip the pair if so.)

Brute force. Sweep through the courses, taking any course whose earlier courses are all done; repeat the sweep until a whole sweep takes nothing. Checking "are all its earlier courses done?" means reading the whole pair list for each course, every sweep.

Key insight. Instead of re-checking, count. A course's in-degree is how many unfinished courses it still waits for. Courses with in-degree 0 go into a queue. Taking a course lowers the in-degree of every course that waited for it by one; any course that drops to 0 joins the queue. This is Kahn's algorithm for topological sort (an order of the nodes in which every arrow points forward).

Why it detects a cycle. On a cycle, every course waits for the course before it on the cycle, so none of them can be the first to reach in-degree 0 — they all stay stuck. So the order contains all n courses exactly when there is no cycle; that one length check answers Part I, and the order itself answers Part II.

An edge case: a cycle. Course 3 and course 0 are taken, but courses 1 and 2 each wait for the other, their in-degrees never reach 0, and the function returns the empty list.

Another way: DFS with three colours. Mark a course "on the current path" while you explore its later courses and "finished" when done. Meeting a course that is on the current path means you walked in a circle. Recursion depth can reach n, which is fine for n = 2000.

Complexity. Time O(n + pairs) — each course enters the queue once and each pair lowers an in-degree once. Space O(n + pairs) for the neighbour lists.

Follow-ups interviewers ask. The smallest number of terms if you can take any number of free courses per term — count Kahn levels, exactly like the minutes in Rotting Oranges. The order of letters in an alien alphabet from a sorted word list (p09-q23). The lexicographically smallest order — use a min-heap instead of a queue.

The idea underneath: topological sort in C22 · Topological sort.

Connected Components and Graph Valid Tree

The task. You get n nodes numbered 0 to n − 1 and a list of undirected edges. Part I: return how many connected components there are. Part II: return true if the edges form a tree — every node reachable from every other, and no cycle.

The plain way. Build neighbour lists, then start a search from every node not seen yet; each start is a new component. This is O(n + E) and perfectly good for Part I.

Key insight: union-find. Keep parent[x] (who x reports to; a root reports to itself) and a counter sets, starting at n. For each edge, find both roots. Different roots: join the groups and lower sets by one. Same root: the edge closes a cycle. Two tricks keep the trees flat:

• Union by rank — hang the shorter tree under the taller one (rank is an upper bound on the tree's height), so trees grow tall only very slowly.
• Path compression — after find(x) walks up to the root, point every node on that walk straight at the root, so the next walk is one step.

Together they make each operation O(α(n)), where α is the inverse Ackermann function — a number that is at most 4 for any n you could ever store. For Part II, a tree on n nodes has exactly n − 1 edges; with that many edges and no cycle, everything must be connected.

An edge case: a cycle. The third edge joins two nodes that already have the same root, so it is flagged — the graph is connected, but it is not a tree.

Complexity. Union-find: time O(n + E · α(n)) — practically O(n + E); space O(n) for parent and rank, with no neighbour lists at all. DFS: O(n + E) time and space.

Follow-ups interviewers ask. Which edge to remove to make a tree (p09-q16). Number of provinces from a matrix (p09-q10). Edges arrive over time and you must report the number of groups after each — union-find is the natural fit, a search per edge is too slow. Why the two tricks matter (p09-q29 measures the tree depths).

The idea underneath: C21 · Disjoint-set forests & union by rank and C21 · Path compression; union-find also drives Kruskal's algorithm in C23 · Kruskal's algorithm.

Word Ladder

The task. You get a start word, an end word, and a list of allowed words, all the same length. One move changes exactly one letter, and every word you step on after the start must be in the list. Return the number of words in the shortest chain from start to end, counting both, or 0 if there is no chain.

Brute force. The words are nodes and "one letter apart" is an edge, so this is a fewest-steps question: BFS. Finding the edges by comparing every pair of words letter by letter costs O(N² · L).

Key insight: wildcard buckets. Two words are one letter apart exactly when they match after hiding the same position. Replace position i by *: "cold" gives the patterns *old, c*ld, co*d, col*. Put each word into the bucket of each of its L patterns. A word's neighbours are then the other words in its L buckets — found without ever comparing pairs. Building the buckets costs O(N · L) patterns of length L, so O(N · L²).

An edge case: the end word is in the list but unreachable. "lead" can step to "load" and "lend", but neither is one letter from "gold", so the queue runs dry and the answer is 0.

Complexity. Time O(N · L²): N words, L patterns each, and building or hashing each pattern costs L. Space O(N · L²) for the buckets. (When a bucket is huge, a word's neighbours can number in the thousands; that is still each edge looked at a bounded number of times.)

Follow-ups interviewers ask. Return every shortest chain, not only its length (BFS records each word's parents on the previous level, then walk back). Search from both ends at once — two smaller ripples meet in the middle and touch far fewer words. Genes or lock combinations with a fixed alphabet: try all 26 (or 4, or 10) letters at each position instead of buckets.

The idea underneath: BFS on an implicit graph (one whose edges are computed when needed), C22 · Breadth-first search; buckets are hash maps, C11 · Hash Tables.

Network Delay Time

The task. A network has n nodes numbered 0 to n − 1 and one-way links [from, to, ms], each taking a positive number of milliseconds. Node k sends a signal. Return the time until every node has received it, or −1 if some node never does.

Brute force (Bellman-Ford). Start with "0 for the sender, infinity for everyone else", then go over every link again and again, improving a node's time whenever "time at the start of the link + the link's ms" is smaller. After n − 1 rounds every shortest route (it has at most n − 1 links) has been found. O(n · E), and it also copes with negative times.

Key insight: Dijkstra's algorithm. Keep a min-heap of (time, node). Pop the smallest; that node's time is now final, because every other route to it passes through some node that is already at least as late. Then relax its links: for each link u → v taking w, if dist[u] + w < dist[v], record the better time and push it. A node can be pushed several times with older, larger times; when such a stale entry is popped, skip it. The answer is the largest final time, or −1 if some node is still at infinity.

An edge case: an unreachable node. Nothing links into node 3, so its time stays infinite and the answer is −1.

Complexity. Time O((n + E) log n) — each link can push one heap entry, and each push or pop costs O(log) of the heap size. Space O(n + E). The verification program compares this function with Bellman-Ford and with Floyd-Warshall (all pairs at once) on 400 random networks.

Follow-ups interviewers ask. Cheapest flight with at most k stops — Dijkstra ignores the stop limit, Bellman-Ford with k + 1 rounds respects it (p09-q21). Count the number of fastest routes (p09-q25). The path whose highest point is lowest, not whose sum is smallest (p09-q24). Print the route: store each node's parent when you improve it, then walk back.

The idea underneath: C24 · Dijkstra's algorithm, C24 · Bellman-Ford and all-pairs distances in C25 · All-Pairs Shortest Paths; the heap of C06 · Priority queues also merges lists in Step 13.6 · Merge K Sorted Lists.

Quiz

Interview questions

Variations and follow-ups of the eight problems above — the questions interviewers move to once you have solved the classic version. Every solution is tested in Dart on its examples and on hundreds of random grids or graphs against a slower reference.

Cheat sheet

Name the nodes and edges first, then choose the tool. Mark visited when you push. Use an explicit stack when the grid can be huge. And test the empty input, a single node, a cycle, and something unreachable.