Graphs · Commitwise

Friends of friends, flight connections, which screens link to which, which build modules depend on which, cells on a game board: all graphs. Many interview problems are graphs in disguise. “Count the islands on this map”, “how many minutes until every orange is rotten”, “can you finish all these courses given their prerequisites”: once you see the graph, the algorithm is usually BFS or DFS with one extra idea.

New to some of these? Open what you need, or skip ahead.

Basics:What are lists, sets and maps?

Collections hold many values:

A list (Swift Array, Kotlin List, Java List, a TypeScript array) keeps items in order, and allows duplicates: ["Ana", "Ben", "Ana"].
A set holds each value at most once and answers “is this in it?” very quickly.
A map (Swift Dictionary, Kotlin, Java and TypeScript Map) stores values under keys: "Ana" → 30, looked up by the key.

Lists use indexes starting at 0: in ["a", "b", "c"], "a" is at index 0 and "c" at index 2.

Basics:What is recursion?

A recursive function calls itself on a smaller version of the problem, until it reaches a case small enough to answer directly (the base case):

countdown(3) → prints 3, calls countdown(2) → prints 2, calls countdown(1) → prints 1, calls countdown(0) → stops

Two rules keep it correct: always have a base case, and make sure every call gets closer to it. Each call waits on the call stack until the smaller call finishes, so very deep recursion (hundreds of thousands of levels) can run out of stack space.

Basics:How do 2D grids work in code?

A grid (a game board, a map) is usually an array of rows, where each row is an array: grid[row][col]. The top-left cell is grid[0][0], grid.count / grid.size / grid.length is the number of rows, and grid[0].count the number of columns.

Moving around means changing the row or column by one: up is row - 1, down is row + 1, left is col - 1, right is col + 1. Before reading a neighbor, check that it’s still inside the grid (row >= 0, row < rows, and the same for columns), or you’ll read outside the array (in TypeScript, that quietly gives undefined).

Part Not started

Nodes, edges and a visited set

Think of a city map: places connected by roads. In a graph, the places are nodes (or vertices) and the roads are edges. Roads can be one-way (a directed graph, like “course A is required before B”) or two-way (undirected, like friendships), and they can have lengths (weighted, like travel time).

Exploring a graph works like exploring a tree with DFS or BFS, with one important difference: a graph can have cycles (A → B → C → A). Without care, you’d walk in circles forever. So every graph search keeps a visited set: before going to a node, check whether you’ve been there.

Graph problems reduce to a handful of algorithms once the modeling is right: what are the nodes (cells, words, states), what are the edges (moves, one-letter changes, prerequisites), are they directed or weighted? BFS gives shortest paths in unweighted graphs, DFS explores components and detects cycles, topological sort orders DAGs, Dijkstra handles non-negative weights, and union-find answers connectivity incrementally. Everything is O(V + E) or close, provided each node is processed once, which is where the bugs live: visited sets marked at the wrong moment, and Dijkstra variants that finalize too early. The Detailed version covers the algorithms and those traps.

An adjacency list, with BFS distances

// Undirected graph: each person maps to their friends
let friends: [String: [String]] = [
    "Ana": ["Ben", "Cleo"], "Ben": ["Ana", "Dan"], "Cleo": ["Ana", "Dan"],
    "Dan": ["Ben", "Cleo", "Eve"], "Eve": ["Dan"],
]

/// Fewest hops from start to every reachable person.
func distances(from start: String, in graph: [String: [String]]) -> [String: Int] {
    var distance = [start: 0]                         // doubles as the visited set
    var queue = [start], head = 0
    while head < queue.count {
        let person = queue[head]; head += 1
        for friend in graph[person, default: []] where distance[friend] == nil {
            distance[friend] = distance[person]! + 1  // mark when discovered
            queue.append(friend)
        }
    }
    return distance
}

print(distances(from: "Ana", in: friends)["Eve"]!)   // 3: Ana → Ben → Dan → Eve

// Undirected graph: each person maps to their friends
val friends = mapOf(
    "Ana" to listOf("Ben", "Cleo"), "Ben" to listOf("Ana", "Dan"), "Cleo" to listOf("Ana", "Dan"),
    "Dan" to listOf("Ben", "Cleo", "Eve"), "Eve" to listOf("Dan"),
)

/** Fewest hops from start to every reachable person. */
fun distances(start: String, graph: Map<String, List<String>>): Map<String, Int> {
    val distance = mutableMapOf(start to 0)           // doubles as the visited set
    val queue = ArrayDeque(listOf(start))
    while (queue.isNotEmpty()) {
        val person = queue.removeFirst()
        for (friend in graph[person].orEmpty()) {
            if (friend in distance) continue
            distance[friend] = distance.getValue(person) + 1   // mark when discovered
            queue.addLast(friend)
        }
    }
    return distance
}

println(distances("Ana", friends)["Eve"])           // 3: Ana → Ben → Dan → Eve

// Undirected graph: each person maps to their friends
Map<String, List<String>> friends = Map.of(
    "Ana", List.of("Ben", "Cleo"), "Ben", List.of("Ana", "Dan"), "Cleo", List.of("Ana", "Dan"),
    "Dan", List.of("Ben", "Cleo", "Eve"), "Eve", List.of("Dan"));

/** Fewest hops from start to every reachable person. */
static Map<String, Integer> distances(String start, Map<String, List<String>> graph) {
    Map<String, Integer> distance = new HashMap<>(Map.of(start, 0));   // doubles as the visited set
    Deque<String> queue = new ArrayDeque<>(List.of(start));
    while (!queue.isEmpty()) {
        String person = queue.pollFirst();
        for (String friend : graph.getOrDefault(person, List.of())) {
            if (distance.containsKey(friend)) continue;
            distance.put(friend, distance.get(person) + 1);            // mark when discovered
            queue.addLast(friend);
        }
    }
    return distance;
}

System.out.println(distances("Ana", friends).get("Eve"));             // 3: Ana → Ben → Dan → Eve

// Undirected graph: each person maps to their friends
const friends = new Map<string, string[]>([
  ["Ana", ["Ben", "Cleo"]], ["Ben", ["Ana", "Dan"]], ["Cleo", ["Ana", "Dan"]],
  ["Dan", ["Ben", "Cleo", "Eve"]], ["Eve", ["Dan"]],
]);

/** Fewest hops from start to every reachable person. */
function distances(start: string, graph: Map<string, string[]>): Map<string, number> {
  const distance = new Map([[start, 0]]);              // doubles as the visited set
  const queue = [start];
  for (let head = 0; head < queue.length; head++) {
    const person = queue[head];
    for (const friend of graph.get(person) ?? []) {
      if (distance.has(friend)) continue;
      distance.set(friend, distance.get(person)! + 1);  // mark when discovered
      queue.push(friend);
    }
  }
  return distance;
}

console.log(distances("Ana", friends).get("Eve"));     // 3: Ana → Ben → Dan → Eve

Two habits in that code prevent most graph bugs:

Mark a node as visited when you add it to the queue, not when you take it out. Otherwise the same node can be added many times by different neighbors before it’s processed.
BFS finds shortest paths (fewest edges) because it explores everything one hop away, then two hops, and so on: the first time it reaches a node is the shortest way there.

Ways to store a graph

Representation	Looks like	Good for
Adjacency list	`Map<Node, List<Node>>`	most problems: sparse graphs, iterating neighbors
Adjacency matrix	`Boolean[n][n]`	dense graphs, “is there an edge between a and b?” in O(1)
Edge list	`List<(from, to, weight)>`	algorithms that process edges (Kruskal, Bellman-Ford), input format
Implicit	neighbors computed on the fly	grids (4 or 8 directions), puzzles, word ladders

Interview inputs often come as an edge list or a grid; the first step is usually building an adjacency list.

Predict the output

In the friends graph (Ana–Ben, Ana–Cleo, Ben–Dan, Cleo–Dan, Dan–Eve), BFS from Ana visits people in which order, if neighbors are visited in the listed order?

The algorithms behind most graph questions

Problem	Algorithm	Complexity
Shortest path, unweighted	BFS	O(V + E)
Shortest path, weights 0 or 1	0-1 BFS with a deque	O(V + E)
Shortest path, non-negative weights	Dijkstra with a binary heap	O((V + E) log V)
Negative weights, negative cycles	Bellman-Ford	O(V · E)
Order with prerequisites, cycle check in a DAG	Topological sort (Kahn’s in-degrees, or DFS post-order)	O(V + E)
Connectivity under added edges, cycles in undirected graphs	Union-find with path compression and union by rank	~O(α(n)) per operation
Minimum spanning tree	Kruskal (sort edges + union-find) or Prim	O(E log E)

Cycle detection differs by graph type: in an undirected graph, an edge to a visited node that isn’t the parent is a cycle; in a directed graph, you need three states (unvisited, in progress, done), and an edge to an in-progress node is a cycle.

Need	Tool
Explore / components / islands	DFS or BFS + visited (mark on discovery)
Fewest edges	BFS; multi-source BFS for “nearest of many”
Weighted, non-negative	Dijkstra: finalize on pop, skip stale entries
Ordering with dependencies, DAG check	Kahn’s topological sort (in-degrees)
Directed cycle detection	DFS with 3 states (unvisited, in progress, done)
Dynamic connectivity	Union-find (path compression + union by rank)

Complexities: BFS/DFS/topo O(V + E), Dijkstra O((V + E) log V). Gotchas: no visited set (infinite loops), marking visited on dequeue in BFS (duplicates), marking visited on push in Dijkstra (wrong distances), BFS on weighted graphs, recursion depth on big grids, Swift arrays with removeFirst() (or TypeScript shift()) as queues.

Check this part

Why does every graph search need a visited set?
Trees have no cycles; graphs usually do.
Which search finds the path with the fewest edges?
BFS explores all nodes 1 hop away, then 2 hops, so it reaches each node first by a shortest path.
In BFS, when should a node be marked visited?
Otherwise several neighbors can add the same node before it's processed.
How do you detect a cycle in a directed graph with DFS?
In a directed graph, reaching a finished node by another path isn't a cycle; reaching one on the current path is.

A graph is nodes plus edges, usually stored as an adjacency list. Because graphs have cycles, every search keeps a visited set, marked when a node is first discovered. BFS reaches each node first by a path with the fewest edges.

Part Not started

Counting islands

A grid has "1" for land and "0" for water, and an island is land connected up, down, left or right. Counting islands is counting connected components: scan every cell, and each time you find land, count a new island and sink the whole island (turn it into water) with a DFS, so it isn’t counted again.

func numIslands(_ input: [[Character]]) -> Int {
    var grid = input
    let rows = grid.count, cols = grid.first?.count ?? 0

    func sink(_ r: Int, _ c: Int) {                   // DFS: turn the whole island into water
        guard r >= 0, r < rows, c >= 0, c < cols, grid[r][c] == "1" else { return }
        grid[r][c] = "0"
        sink(r + 1, c); sink(r - 1, c); sink(r, c + 1); sink(r, c - 1)
    }

    var islands = 0
    for r in 0..<rows {
        for c in 0..<cols where grid[r][c] == "1" {
            islands += 1
            sink(r, c)
        }
    }
    return islands
}

fun numIslands(grid: Array<CharArray>): Int {
    val rows = grid.size
    val cols = grid.firstOrNull()?.size ?: 0

    fun sink(r: Int, c: Int) {                        // DFS: turn the whole island into water
        if (r !in 0 until rows || c !in 0 until cols || grid[r][c] != '1') return
        grid[r][c] = '0'
        sink(r + 1, c); sink(r - 1, c); sink(r, c + 1); sink(r, c - 1)
    }

    var islands = 0
    for (r in 0 until rows) for (c in 0 until cols) {
        if (grid[r][c] == '1') { islands++; sink(r, c) }
    }
    return islands
}

int numIslands(char[][] grid) {
    int islands = 0;
    for (int r = 0; r < grid.length; r++) {
        for (int c = 0; c < grid[0].length; c++) {
            if (grid[r][c] == '1') { islands++; sink(grid, r, c); }
        }
    }
    return islands;
}

void sink(char[][] grid, int r, int c) {             // DFS: turn the whole island into water
    if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] != '1') return;
    grid[r][c] = '0';
    sink(grid, r + 1, c); sink(grid, r - 1, c); sink(grid, r, c + 1); sink(grid, r, c - 1);
}

function numIslands(input: string[][]): number {
  const grid = input.map((row) => [...row]);         // work on a copy
  const rows = grid.length;
  const cols = grid[0]?.length ?? 0;

  const sink = (r: number, c: number): void => {     // DFS: turn the whole island into water
    if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] !== "1") return;
    grid[r][c] = "0";
    sink(r + 1, c); sink(r - 1, c); sink(r, c + 1); sink(r, c - 1);
  };

  let islands = 0;
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === "1") { islands++; sink(r, c); }
    }
  }
  return islands;
}

Each cell is sunk at most once, so the whole scan is O(rows × cols). Turning land into water is the visited set, with no extra memory besides the recursion. The Kotlin and Java versions modify the caller’s grid (say so in an interview, or copy it first); the Swift and TypeScript versions work on a copy. A 1,000 × 1,000 grid that’s all land makes the recursion a million calls deep, which the senior section addresses.

Going around in circles

Spot the bugA reachability check that never returns

Tap the line with the bug.

func canReach(_ graph: [String: [String]], from: String, to: String) -> Bool {
    if from == to { return true }
    for next in graph[from, default: []] {
        if canReach(graph, from: next, to: to) { return true }
    }
    return false
}

fun canReach(graph: Map<String, List<String>>, from: String, to: String): Boolean {
    if (from == to) return true
    for (next in graph[from].orEmpty()) {
        if (canReach(graph, next, to)) return true
    }
    return false
}

boolean canReach(Map<String, List<String>> graph, String from, String to) {
    if (from.equals(to)) return true;
    for (String next : graph.getOrDefault(from, List.of())) {
        if (canReach(graph, next, to)) return true;
    }
    return false;
}

function canReach(graph: Map<string, string[]>, from: string, to: string): boolean {
  if (from === to) return true;
  for (const next of graph.get(from) ?? []) {
    if (canReach(graph, next, to)) return true;
  }
  return false;
}

Without a visited set, the search walks Ana → Ben → Ana → Ben → … forever (every undirected edge is a cycle of length 2). When the target is reachable, it may get lucky and find it first; when it isn’t, the recursion never ends and crashes with a stack overflow. Even on graphs without cycles, it can revisit the same node through different paths exponentially many times.

Remember where you’ve been:

func canReach(_ graph: [String: [String]], from: String, to: String, visited: inout Set<String>) -> Bool {
    if from == to { return true }
    guard visited.insert(from).inserted else { return false }   // seen before: stop
    for next in graph[from, default: []] where canReach(graph, from: next, to: to, visited: &visited) {
        return true
    }
    return false
}

fun canReach(graph: Map<String, List<String>>, from: String, to: String, visited: MutableSet<String> = HashSet()): Boolean {
    if (from == to) return true
    if (!visited.add(from)) return false                         // seen before: stop
    return graph[from].orEmpty().any { canReach(graph, it, to, visited) }
}

boolean canReach(Map<String, List<String>> graph, String from, String to, Set<String> visited) {
    if (from.equals(to)) return true;
    if (!visited.add(from)) return false;                        // seen before: stop
    for (String next : graph.getOrDefault(from, List.of())) {
        if (canReach(graph, next, to, visited)) return true;
    }
    return false;
}

function canReach(graph: Map<string, string[]>, from: string, to: string, visited = new Set<string>()): boolean {
  if (from === to) return true;
  if (visited.has(from)) return false;                        // seen before: stop
  visited.add(from);
  return (graph.get(from) ?? []).some((next) => canReach(graph, next, to, visited));
}

Production considerations

Recursion depth: a recursive DFS over a 1,000 × 1,000 grid can go a million calls deep; use an explicit stack or BFS for big inputs.
Implicit graphs can be huge (states of a puzzle, all words): generate neighbors on demand and bound the search (bidirectional BFS, A* with a good heuristic).
Real systems use these directly: dependency resolution and build ordering (topological sort), routing (Dijkstra, A*), social features (BFS with depth limits), and garbage collectors (graph reachability from roots).

Exercisemedium

Course Schedule II

There are n courses (0 to n − 1) and a list of prerequisites [a, b], meaning you must take b before a. Return an order in which you can take all courses, or an empty list if it’s impossible (because of a cycle).

n = 4, prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]]
→ [0, 1, 2, 3]   (or [0, 2, 1, 3])

n = 2, prerequisites = [[1, 0], [0, 1]]
→ []             (each requires the other)

›

This is a directed graph b → a. An order where every edge points forward is a topological order, which exists exactly when there’s no cycle.

›

Kahn’s algorithm: count each course’s incoming edges (in-degree). Start with every course whose in-degree is 0. Each time you take a course, decrement its dependents’ in-degrees and queue those that reach 0. If you took fewer than n courses, there’s a cycle.

SolutionTry it yourself firstTime O(V + E)Space O(V + E)

func findOrder(_ n: Int, _ prerequisites: [[Int]]) -> [Int] {
    var dependents = Array(repeating: [Int](), count: n)
    var inDegree = Array(repeating: 0, count: n)
    for pair in prerequisites {
        dependents[pair[1]].append(pair[0])
        inDegree[pair[0]] += 1
    }
    var queue = (0..<n).filter { inDegree[$0] == 0 }, head = 0
    while head < queue.count {
        let course = queue[head]; head += 1
        for next in dependents[course] {
            inDegree[next] -= 1
            if inDegree[next] == 0 { queue.append(next) }
        }
    }
    return queue.count == n ? queue : []              // the queue array is the order
}

fun findOrder(n: Int, prerequisites: Array<IntArray>): IntArray {
    val dependents = List(n) { mutableListOf<Int>() }
    val inDegree = IntArray(n)
    for ((course, required) in prerequisites) {
        dependents[required] += course
        inDegree[course]++
    }
    val queue = ArrayDeque((0 until n).filter { inDegree[it] == 0 })
    val order = mutableListOf<Int>()
    while (queue.isNotEmpty()) {
        val course = queue.removeFirst()
        order += course
        for (next in dependents[course]) {
            if (--inDegree[next] == 0) queue.addLast(next)
        }
    }
    return if (order.size == n) order.toIntArray() else intArrayOf()   // leftovers are in a cycle
}

int[] findOrder(int n, int[][] prerequisites) {
    List<List<Integer>> dependents = new ArrayList<>();
    for (int i = 0; i < n; i++) dependents.add(new ArrayList<>());
    int[] inDegree = new int[n];
    for (int[] p : prerequisites) {
        dependents.get(p[1]).add(p[0]);
        inDegree[p[0]]++;
    }
    Deque<Integer> queue = new ArrayDeque<>();
    for (int i = 0; i < n; i++) if (inDegree[i] == 0) queue.addLast(i);
    int[] order = new int[n];
    int taken = 0;
    while (!queue.isEmpty()) {
        int course = queue.pollFirst();
        order[taken++] = course;
        for (int next : dependents.get(course)) {
            if (--inDegree[next] == 0) queue.addLast(next);
        }
    }
    return taken == n ? order : new int[0];           // leftovers are in a cycle
}

function findOrder(n: number, prerequisites: [number, number][]): number[] {
  const dependents = Array.from({ length: n }, () => [] as number[]);
  const inDegree = new Array<number>(n).fill(0);
  for (const [course, required] of prerequisites) {
    dependents[required].push(course);
    inDegree[course]++;
  }
  const queue = [...Array(n).keys()].filter((c) => inDegree[c] === 0);
  for (let head = 0; head < queue.length; head++) {
    for (const next of dependents[queue[head]]) {
      if (--inDegree[next] === 0) queue.push(next);
    }
  }
  return queue.length === n ? queue : [];            // the queue array is the order
}

Every course enters the queue once its last prerequisite is taken, so each node and edge is processed once: O(V + E). Courses in a cycle never reach in-degree 0, which is why “fewer than n taken” detects the cycle without a separate search. The same algorithm orders build modules (Gradle, Bazel), database migrations with dependencies, and spreadsheet recalculation. Follow-ups: a DFS-based topological sort (reverse post-order with three-color cycle detection), and “minimum number of semesters” (count BFS levels).

Deep dives

Deep diveUnion-findInterview favorite

Union-find (disjoint set union) keeps groups of elements and answers “are these two in the same group?” while groups are merged. Each element points to a parent; the root is the group’s representative.

Two tricks make it nearly O(1) per operation: path compression (after finding a root, point every visited node straight at it) and union by rank (attach the shorter tree under the taller one). Together the amortized cost is O(α(n)), where α is the inverse Ackermann function, at most 4 for any realistic n. It powers Kruskal’s minimum spanning tree, cycle detection in undirected graphs, and “number of connected components” when edges arrive one at a time.

Components: scan, and on each unvisited node run DFS/BFS that marks the whole component. Union-find answers the same question as edges arrive.
Kahn’s topological sort: in-degrees, a queue of zero in-degree nodes; fewer than n outputs means a cycle. Recursive DFS on a big grid can go a million calls deep: use BFS or an explicit stack.

Grid neighbors, the reusable way

let directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
for (dr, dc) in directions {
    let nr = r + dr, nc = c + dc
    guard grid.indices.contains(nr), grid[nr].indices.contains(nc) else { continue }
    // visit (nr, nc)
}

val directions = listOf(1 to 0, -1 to 0, 0 to 1, 0 to -1)
for ((dr, dc) in directions) {
    val nr = r + dr; val nc = c + dc
    if (nr !in grid.indices || nc !in grid[nr].indices) continue
    // visit (nr, nc)
}

int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
for (int[] d : directions) {
    int nr = r + d[0], nc = c + d[1];
    if (nr < 0 || nr >= grid.length || nc < 0 || nc >= grid[nr].length) continue;
    // visit (nr, nc)
}

const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
for (const [dr, dc] of directions) {
  const nr = r + dr, nc = c + dc;
  if (nr < 0 || nr >= grid.length || nc < 0 || nc >= grid[nr].length) continue;
  // visit (nr, nc)
}

Check this part

How do you count islands in a grid?
Islands are connected components.
A reachability check with no visited set runs on an undirected graph, and the target can't be reached. What happens?
Every undirected edge is a cycle of length 2.
How does Kahn's algorithm detect a cycle?
Topological order exists exactly when the graph is acyclic.
Recursive Number of Islands runs on a 1,000 × 1,000 grid that is all land. What is the risk?
Use BFS or an explicit stack for large inputs.

Counting islands is counting connected components: each time you find unvisited land, count one and mark its whole component. Without a visited set, a search walks in circles; ordering with prerequisites is a topological sort that also detects cycles.

Part Not started

Shortest paths in a grid

A robot moves up, down, left or right on a grid with walls (#), and you need the fewest moves from start S to goal G. That’s BFS on an implicit graph, step by step:

Nodes are open cells (row, col); edges go to the four neighbors that are inside the grid and not walls.
Start BFS from S, with distance 0, marking it visited.
For each cell taken from the queue, look at its neighbors; each unvisited open neighbor gets distance + 1, is marked visited, and goes into the queue.
The first time you reach G, its distance is the answer. If the queue empties first, the goal is unreachable.

Fewest moves in a grid

func shortestPath(_ grid: [[Character]], from start: (Int, Int), to goal: (Int, Int)) -> Int? {
    let rows = grid.count, cols = grid[0].count
    var distance = Array(repeating: Array(repeating: -1, count: cols), count: rows)
    distance[start.0][start.1] = 0
    var queue = [start], head = 0
    while head < queue.count {
        let (r, c) = queue[head]; head += 1
        if (r, c) == goal { return distance[r][c] }
        for (dr, dc) in [(1, 0), (-1, 0), (0, 1), (0, -1)] {
            let nr = r + dr, nc = c + dc
            guard nr >= 0, nr < rows, nc >= 0, nc < cols, grid[nr][nc] != "#", distance[nr][nc] == -1 else { continue }
            distance[nr][nc] = distance[r][c] + 1
            queue.append((nr, nc))
        }
    }
    return nil
}

fun shortestPath(grid: List<String>, start: Pair<Int, Int>, goal: Pair<Int, Int>): Int? {
    val rows = grid.size
    val cols = grid[0].length
    val distance = Array(rows) { IntArray(cols) { -1 } }
    distance[start.first][start.second] = 0
    val queue = ArrayDeque(listOf(start))
    val directions = listOf(1 to 0, -1 to 0, 0 to 1, 0 to -1)
    while (queue.isNotEmpty()) {
        val (r, c) = queue.removeFirst()
        if (r to c == goal) return distance[r][c]
        for ((dr, dc) in directions) {
            val nr = r + dr
            val nc = c + dc
            if (nr !in 0 until rows || nc !in 0 until cols || grid[nr][nc] == '#' || distance[nr][nc] != -1) continue
            distance[nr][nc] = distance[r][c] + 1
            queue.addLast(nr to nc)
        }
    }
    return null
}

static int shortestPath(char[][] grid, int[] start, int[] goal) {
    int rows = grid.length, cols = grid[0].length;
    int[][] distance = new int[rows][cols];
    for (int[] row : distance) Arrays.fill(row, -1);
    distance[start[0]][start[1]] = 0;
    Deque<int[]> queue = new ArrayDeque<>(List.of(start));
    int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    while (!queue.isEmpty()) {
        int[] cell = queue.pollFirst();
        if (cell[0] == goal[0] && cell[1] == goal[1]) return distance[cell[0]][cell[1]];
        for (int[] d : directions) {
            int nr = cell[0] + d[0], nc = cell[1] + d[1];
            if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || grid[nr][nc] == '#' || distance[nr][nc] != -1) continue;
            distance[nr][nc] = distance[cell[0]][cell[1]] + 1;
            queue.addLast(new int[] {nr, nc});
        }
    }
    return -1;                                        // unreachable
}

function shortestPath(grid: string[], start: [number, number], goal: [number, number]): number | null {
  const rows = grid.length;
  const cols = grid[0].length;
  const distance = Array.from({ length: rows }, () => new Array<number>(cols).fill(-1));
  distance[start[0]][start[1]] = 0;
  const queue = [start];
  const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
  for (let head = 0; head < queue.length; head++) {
    const [r, c] = queue[head];
    if (r === goal[0] && c === goal[1]) return distance[r][c];
    for (const [dr, dc] of directions) {
      const nr = r + dr;
      const nc = c + dc;
      if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || grid[nr][nc] === "#" || distance[nr][nc] !== -1) continue;
      distance[nr][nc] = distance[r][c] + 1;
      queue.push([nr, nc]);
    }
  }
  return null;
}

The distance grid does double duty as the visited set (-1 means not yet visited). The same code works for knight moves or 8 directions: only the directions list changes.

Exercisemedium

Rotting Oranges

In a grid, 0 is empty, 1 is a fresh orange and 2 is a rotten one. Every minute, fresh oranges next to a rotten one (up, down, left, right) become rotten. Return the minutes until no fresh orange is left, or -1 if some can never rot.

2 1 1
1 1 0
0 1 1        → 4

2 1 1
0 1 1
1 0 1        → -1   (the bottom-left orange is cut off)

›

The rot spreads from all rotten oranges at once. What happens if you start BFS with every rotten orange in the queue?

›

Multi-source BFS: queue every rotten orange at minute 0, count the fresh ones, and process the queue level by level (one level = one minute). Each fresh orange you rot decrements the count. At the end, a non-zero count means -1.

SolutionTry it yourself firstTime O(rows × cols)Space O(rows × cols)

func orangesRotting(_ input: [[Int]]) -> Int {
    var grid = input
    let rows = grid.count, cols = grid[0].count
    var rotten: [(Int, Int)] = [], fresh = 0
    for r in 0..<rows { for c in 0..<cols {
        if grid[r][c] == 2 { rotten.append((r, c)) } else if grid[r][c] == 1 { fresh += 1 }
    } }

    var minutes = 0
    while !rotten.isEmpty && fresh > 0 {
        var next: [(Int, Int)] = []
        for (r, c) in rotten {
            for (nr, nc) in [(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)]
                where nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 1 {
                grid[nr][nc] = 2                      // rot it and mark it visited
                fresh -= 1
                next.append((nr, nc))
            }
        }
        rotten = next
        minutes += 1
    }
    return fresh == 0 ? minutes : -1
}

fun orangesRotting(grid: Array<IntArray>): Int {
    val queue = ArrayDeque<Pair<Int, Int>>()
    var fresh = 0
    for (r in grid.indices) for (c in grid[0].indices) {
        when (grid[r][c]) { 2 -> queue.addLast(r to c); 1 -> fresh++ }
    }
    var minutes = 0
    val directions = listOf(1 to 0, -1 to 0, 0 to 1, 0 to -1)
    while (queue.isNotEmpty() && fresh > 0) {
        repeat(queue.size) {                          // one minute = one level
            val (r, c) = queue.removeFirst()
            for ((dr, dc) in directions) {
                val nr = r + dr
                val nc = c + dc
                if (nr in grid.indices && nc in grid[0].indices && grid[nr][nc] == 1) {
                    grid[nr][nc] = 2
                    fresh--
                    queue.addLast(nr to nc)
                }
            }
        }
        minutes++
    }
    return if (fresh == 0) minutes else -1
}

int orangesRotting(int[][] grid) {
    Deque<int[]> queue = new ArrayDeque<>();
    int fresh = 0;
    for (int r = 0; r < grid.length; r++)
        for (int c = 0; c < grid[0].length; c++) {
            if (grid[r][c] == 2) queue.addLast(new int[] {r, c});
            else if (grid[r][c] == 1) fresh++;
        }
    int minutes = 0;
    int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    while (!queue.isEmpty() && fresh > 0) {
        for (int i = queue.size(); i > 0; i--) {      // one minute = one level
            int[] cell = queue.pollFirst();
            for (int[] d : directions) {
                int nr = cell[0] + d[0], nc = cell[1] + d[1];
                if (nr >= 0 && nr < grid.length && nc >= 0 && nc < grid[0].length && grid[nr][nc] == 1) {
                    grid[nr][nc] = 2;
                    fresh--;
                    queue.addLast(new int[] {nr, nc});
                }
            }
        }
        minutes++;
    }
    return fresh == 0 ? minutes : -1;
}

function orangesRotting(input: number[][]): number {
  const grid = input.map((row) => [...row]);
  let rotten: [number, number][] = [];
  let fresh = 0;
  grid.forEach((row, r) => row.forEach((cell, c) => {
    if (cell === 2) rotten.push([r, c]);
    else if (cell === 1) fresh++;
  }));

  let minutes = 0;
  while (rotten.length > 0 && fresh > 0) {
    const next: [number, number][] = [];
    for (const [r, c] of rotten) {
      for (const [nr, nc] of [[r + 1, c], [r - 1, c], [r, c + 1], [r, c - 1]]) {
        if (grid[nr]?.[nc] === 1) {                  // outside the grid reads undefined
          grid[nr][nc] = 2;                          // rot it and mark it visited
          fresh--;
          next.push([nr, nc]);
        }
      }
    }
    rotten = next;
    minutes++;
  }
  return fresh === 0 ? minutes : -1;
}

Starting with all sources in the queue is the key idea: the BFS levels then measure the distance from the nearest rotten orange, which is exactly when each orange rots. The same multi-source trick answers “distance from each cell to the nearest exit”, “walls and gates” and “01 matrix”. The fresh > 0 condition in the loop avoids counting an extra minute after the last orange rots.

Fewest edges isn’t cheapest

Predict the output

Edges: A–B costs 10, A–C costs 1, C–B costs 1. A function finds the path from A to B with BFS (fewest edges) and adds up its costs. What does it return?

Dijkstra that finalizes too early

Spot the bugRoutes that aren't the shortest

Tap the line with the bug.

fun shortest(graph: Map<Int, List<Pair<Int, Int>>>, start: Int): Map<Int, Int> {
    val dist = mutableMapOf(start to 0)
    val visited = mutableSetOf(start)
    val queue = PriorityQueue<Pair<Int, Int>>(compareBy { it.second })
    queue += start to 0
    while (queue.isNotEmpty()) {
        val (node, d) = queue.poll()
        for ((next, weight) in graph[node].orEmpty()) {
            if (next in visited) continue
            visited += next
            dist[next] = d + weight
            queue += next to d + weight
        }
    }
    return dist
}

Map<Integer, Integer> shortest(Map<Integer, List<int[]>> graph, int start) {
    Map<Integer, Integer> dist = new HashMap<>(Map.of(start, 0));
    Set<Integer> visited = new HashSet<>(Set.of(start));
    PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(e -> e[1]));
    queue.add(new int[] {start, 0});
    while (!queue.isEmpty()) {
        int[] top = queue.poll();
        for (int[] edge : graph.getOrDefault(top[0], List.of())) {
            if (visited.contains(edge[0])) continue;
            visited.add(edge[0]);
            dist.put(edge[0], top[1] + edge[1]);
            queue.add(new int[] {edge[0], top[1] + edge[1]});
        }
    }
    return dist;
}

// Heap: the small binary heap from the Heaps lesson
function shortest(graph: Map<number, [number, number][]>, start: number): Map<number, number> {
  const dist = new Map([[start, 0]]);
  const visited = new Set([start]);
  const queue = new Heap<[number, number]>((a, b) => a[1] < b[1]);
  queue.push([start, 0]);
  while (queue.size > 0) {
    const [node, d] = queue.pop()!;
    for (const [next, weight] of graph.get(node) ?? []) {
      if (visited.has(next)) continue;
      visited.add(next);
      dist.set(next, d + weight);
      queue.push([next, d + weight]);
    }
  }
  return dist;
}

Marking a node visited when it’s first discovered is right for BFS and wrong for Dijkstra. Here B is discovered from A at distance 10 and immediately locked in; when C is processed and offers B at distance 2, the visited check throws the better path away. The result: 10 instead of 2, on exactly the graphs where shortcuts exist.

In Dijkstra, a node’s distance is final only when it’s taken out of the priority queue; until then, keep improving it (“relaxing” edges) and push the improved entry:

fun shortest(graph: Map<Int, List<Pair<Int, Int>>>, start: Int): Map<Int, Int> {
    val dist = mutableMapOf(start to 0)
    val queue = PriorityQueue<Pair<Int, Int>>(compareBy { it.second })
    queue += start to 0
    while (queue.isNotEmpty()) {
        val (node, d) = queue.poll()
        if (d > dist.getValue(node)) continue                  // a stale, longer entry: skip
        for ((next, weight) in graph[node].orEmpty()) {
            val candidate = d + weight
            if (candidate < (dist[next] ?: Int.MAX_VALUE)) {   // relax: found a shorter way
                dist[next] = candidate
                queue += next to candidate
            }
        }
    }
    return dist
}

Map<Integer, Integer> shortest(Map<Integer, List<int[]>> graph, int start) {
    Map<Integer, Integer> dist = new HashMap<>(Map.of(start, 0));
    PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(e -> e[1]));
    queue.add(new int[] {start, 0});
    while (!queue.isEmpty()) {
        int[] top = queue.poll();
        if (top[1] > dist.get(top[0])) continue;                // a stale, longer entry: skip
        for (int[] edge : graph.getOrDefault(top[0], List.of())) {
            int candidate = top[1] + edge[1];
            if (candidate < dist.getOrDefault(edge[0], Integer.MAX_VALUE)) {   // relax
                dist.put(edge[0], candidate);
                queue.add(new int[] {edge[0], candidate});
            }
        }
    }
    return dist;
}

function shortest(graph: Map<number, [number, number][]>, start: number): Map<number, number> {
  const dist = new Map([[start, 0]]);
  const queue = new Heap<[number, number]>((a, b) => a[1] < b[1]);
  queue.push([start, 0]);
  while (queue.size > 0) {
    const [node, d] = queue.pop()!;
    if (d > dist.get(node)!) continue;                       // a stale, longer entry: skip
    for (const [next, weight] of graph.get(node) ?? []) {
      const candidate = d + weight;
      if (candidate < (dist.get(next) ?? Infinity)) {        // relax: found a shorter way
        dist.set(next, candidate);
        queue.push([next, candidate]);
      }
    }
  }
  return dist;
}

The “skip stale entries” line replaces a decrease-key operation, which Java’s and Kotlin’s PriorityQueue (and the TypeScript Heap from the Heaps lesson) don’t have. And Dijkstra is only correct for non-negative weights.

Swift note

Swift’s standard library has no priority queue; use Heap from the swift-collections package (import HeapModule), with an element type ordered by distance. The algorithm and the bug are the same.

Multi-source BFS (all sources queued at distance 0) gives the distance to the nearest source: rotting oranges, walls and gates, 01 matrix.
BFS on weighted graphs is wrong. Dijkstra (non-negative weights): finalize on pop, relax on discovery, skip stale entries instead of decrease-key; 0-1 BFS for weights 0 and 1.

Check this part

Rot spreads from all rotten oranges at once. How should BFS start?
Multi-source BFS measures the distance to the nearest source.
The grid robot can now also move diagonally. What changes in the BFS code?
The graph is implicit: neighbors come from the directions list.
Why is BFS wrong for weighted shortest paths?
Use Dijkstra for non-negative weights.
In Dijkstra, when is a node's distance final?
Until then, shorter paths may still be found; skip stale entries when popping.

Shortest paths in a grid are BFS on an implicit graph; starting with every source in the queue gives distances to the nearest one. BFS minimizes edges, not weights: weighted graphs need Dijkstra, which finalizes a node only when it's popped.

Key takeaways

A graph is nodes plus edges (directed or not, weighted or not); store it as an adjacency list.
Every search needs a visited set; mark nodes when you first discover them.
BFS finds shortest paths in unweighted graphs; DFS explores and counts components.
Grids are graphs: cells are nodes, the four neighbors are edges; multi-source BFS spreads from many starts at once.

Pick by problem shape: BFS, 0-1 BFS, Dijkstra, Bellman-Ford, topological sort, union-find.
Dijkstra finalizes on pop, relaxes on discovery, and skips stale entries; it needs non-negative weights.
Directed cycle detection needs three states; Kahn’s algorithm detects cycles by counting output.
Use explicit stacks or BFS for large inputs, and bound searches over implicit graphs.