Graphs

Graphs model pairwise relationships between nodes and require explicit cycle prevention — you solve connectivity, ordering, reachability, and shortest-path problems using DFS with a visited set, BFS with a queue, or Dijkstra's algorithm for weighted edges.

• Replaces brute-force pairwise checks with O(V + E) traversal that handles directed, undirected, cyclic, and grid-based graphs
• Three traversal modes: DFS for connectivity and cycle detection, BFS for unweighted shortest path, Dijkstra's for weighted shortest path
• Reach for it when the problem mentions connected components, dependencies, cycle detection, reachability, or minimum cost between nodes

Quick Revision - Must Do Problems

If short on time, solve only these. They cover ~90% of graph patterns.

Practice Tips

How to Identify a Graph Problem

• Input is an adjacency list, edge list, or a grid of cells
• Problem mentions connected components, reachability, or shortest path
• Problem has dependency relationships between items (topological sort)
• Grid problem with connected regions (islands, walls, water flow)
• Problem asks to detect cycles in a directed or undirected graph
• Graph edges have weights and you need minimum cost or time

DFS vs BFS vs Dijkstra's

Interview Approach

1. Confirm the graph type: undirected vs directed, has cycles vs DAG, adjacency list vs grid, weighted vs unweighted
2. For undirected graphs: use a boolean visited[] array or set — 2 states are enough
3. For directed graphs with cycle detection: use 3-state state[] (0 = unvisited, 1 = in path, 2 = done)
4. For grids: define a 4-direction array at the top, bounds-check before recursing, mark visited by overwriting the cell value
5. For topological sort: build in-degree array first, then BFS from zero-in-degree nodes
6. For weighted graphs: use Dijkstra's with a min-heap [cost, node]; always skip stale heap entries with if (cost > dist[node]) continue
7. Always mark visited when adding to the queue (BFS) or at the start of recursion (DFS) — never on pop

6 Main Patterns

Not sure whether to use an adjacency list or matrix? See Adjacency List vs Matrix in Data Structures.

Pattern 1: Grid DFS

Copy// 4-direction grid traversal — mark visited by overwriting
int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};

private void dfs(char[][] grid, int r, int c) {
    if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length
            || grid[r][c] != '1') return;
    grid[r][c] = '0';                  // mark visited in-place
    for (int[] d : dirs) {
        dfs(grid, r + d[0], c + d[1]);
    }
}

Pattern 2: Graph DFS (Directed, Cycle Detection — 3 States)

Copy// 0 = unvisited, 1 = in current path, 2 = fully processed
int[] state = new int[n];

private boolean hasCycle(int node) {
    if (state[node] == 1) {
        return true;  // back edge = cycle
    }
    if (state[node] == 2) {
        return false; // already safe
    }
    state[node] = 1;
    for (int neighbor : graph.get(node)) {
        if (hasCycle(neighbor)) return true;
    }
    state[node] = 2;
    return false;
}

Pattern 3: Topological Sort (Kahn's BFS)

Start with every node that has no dependencies (in-degree = 0) and add them to a queue. Process each one, and for every node it points to, reduce that node's dependency count by one. The moment a node's count hits zero, all its dependencies are done — add it to the queue. If you process every node, you have a valid order. If you get stuck before that, there's a cycle.

Copy// Build in-degree array; BFS from all zero-in-degree nodes
// Each time a neighbor's in-degree hits 0, its prerequisites are all satisfied
int[] inDegree = new int[n];
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) {
    adj.add(new ArrayList<>());
}
for (int[] e : edges) {
    adj.get(e[0]).add(e[1]); inDegree[e[1]]++;
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < n; i++) {
    if (inDegree[i] == 0) queue.offer(i);
}
List<Integer> order = new ArrayList<>();
while (!queue.isEmpty()) {
    int node = queue.poll();
    order.add(node);
    for (int next : adj.get(node)) {
        inDegree[next]--;
        if (inDegree[next] == 0) {
            queue.offer(next);
        }
    }
}
// order.size() == n → valid topological order; else cycle exists

Pattern 4: Graph DFS (Deep Copy with Visited Map)

Copy// Use a HashMap from original node → cloned node as the visited set
// Register the clone before recursing to handle cycles
public Node cloneGraph(Node node) {
    if (node == null) {
        return null;
    }
    return dfs(node, new HashMap<>());
}

private Node dfs(Node node, Map<Node, Node> cloned) {
    if (cloned.containsKey(node)) {
        return cloned.get(node);
    }
    Node clone = new Node(node.val);
    cloned.put(node, clone);                    // register before recursing
    for (Node neighbor : node.neighbors) {
        clone.neighbors.add(dfs(neighbor, cloned));
    }
    return clone;
}

Pattern 5: Grid BFS (Unweighted Shortest Path)

Copy// BFS guarantees shortest path when all steps cost 1
// Carry distance as a third value in the queue
Queue<int[]> queue = new LinkedList<>();
boolean[][] visited = new boolean[m][n];
queue.offer(new int[]{startR, startC, 0});
visited[startR][startC] = true;

int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};

while (!queue.isEmpty()) {
    int[] curr = queue.poll();
    int r = curr[0], c = curr[1], dist = curr[2];
    if (r == targetR && c == targetC) return dist;
    for (int[] d : dirs) {
        int nr = r + d[0], nc = c + d[1];
        if (nr >= 0 && nr < m && nc >= 0 && nc < n
                && !visited[nr][nc] && grid[nr][nc] != 'X') {
            visited[nr][nc] = true;
            queue.offer(new int[]{nr, nc, dist + 1});
        }
    }
}
return -1; // target not reachable

Pattern 6: Dijkstra's (Weighted Shortest Path)

Copy// Min-heap always processes the cheapest node next
// Skip stale heap entries — a node may be added multiple times with different costs
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[start] = 0;

PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
minHeap.offer(new int[]{0, start}); // [cost, node]

while (!minHeap.isEmpty()) {
    int[] curr = minHeap.poll();
    int cost = curr[0], node = curr[1];

    if (cost > dist[node]) continue; // stale entry — skip

    for (int[] neighbor : adj.get(node)) {
        int next = neighbor[0], weight = neighbor[1];
        int newCost = cost + weight;
        if (newCost < dist[next]) {
            dist[next] = newCost;
            minHeap.offer(new int[]{newCost, next});
        }
    }
}

General Templates

Data Structure Definition

Copy// Graph Node (Clone Graph)
class Node {
    int val;
    List<Node> neighbors = new ArrayList<>();
    Node(int val) { this.val = val; }
}

Grid DFS — No Mutation (Separate Visited Array)

Copy// Use when the problem says not to modify the input grid
boolean[][] visited = new boolean[m][n];

private void dfs(char[][] grid, int r, int c, boolean[][] visited) {
    if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length
            || grid[r][c] != '1' || visited[r][c]) return;
    visited[r][c] = true;
    dfs(grid, r + 1, c, visited);
    dfs(grid, r - 1, c, visited);
    dfs(grid, r, c + 1, visited);
    dfs(grid, r, c - 1, visited);
}

Iterative DFS (Stack — Avoids Stack Overflow on Large Grids)

Copy// Use explicit Stack on very large grids where recursion depth causes stack overflow
// Mark visited before pushing to avoid duplicate processing
public void dfsIterative(char[][] grid, int startR, int startC) {
    Deque<int[]> stack = new ArrayDeque<>();
    stack.push(new int[]{startR, startC});
    grid[startR][startC] = '0'; // mark before pushing

    int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};

    while (!stack.isEmpty()) {
        int[] curr = stack.pop();
        int r = curr[0], c = curr[1];
        for (int[] d : dirs) {
            int nr = r + d[0], nc = c + d[1];
            if (nr >= 0 && nr < grid.length && nc >= 0 && nc < grid[0].length
                    && grid[nr][nc] == '1') {
                grid[nr][nc] = '0'; // mark before pushing
                stack.push(new int[]{nr, nc});
            }
        }
    }
}

Problem 1: Flood Fill ⭐ MUST DO

Given an image as a 2D grid of integers, a starting cell (sr, sc), and a new color, flood-fill the connected region of the original color starting at (sr, sc) with the new color.

Example:

CopyInput:  image = [[1,1,1],[1,1,0],[1,0,1]], sr=1, sc=1, color=2
Output:          [[2,2,2],[2,2,0],[2,0,1]]

Input:  image = [[0,0,0],[0,0,0]], sr=0, sc=0, color=0
Output:          [[0,0,0],[0,0,0]]  (already that color — no change)

Key Insight:

• Guard against the case where the starting cell is already the new color — otherwise the DFS loops forever because the termination condition grid[r][c] != originalColor is never true after the first write.

Solution:

Copypublic int[][] floodFill(int[][] image, int sr, int sc, int color) {
    int originalColor = image[sr][sc];
    if (originalColor != color) {
        dfs(image, sr, sc, originalColor, color);
    }
    return image;
}

private void dfs(int[][] image, int r, int c, int originalColor, int newColor) {
    if (r < 0 || r >= image.length || c < 0 || c >= image[0].length
            || image[r][c] != originalColor) {
        return;
    }
    image[r][c] = newColor;
    dfs(image, r + 1, c, originalColor, newColor);
    dfs(image, r - 1, c, originalColor, newColor);
    dfs(image, r, c + 1, originalColor, newColor);
    dfs(image, r, c - 1, originalColor, newColor);
}

Complexity:

Problem 2: Number of Islands ⭐ MUST DO [B75-200]

Count the number of islands in a grid of '1' (land) and '0' (water). Islands are groups of horizontally/vertically connected land cells.

Example:

CopyInput:
  1 1 0 0 0
  1 1 0 0 0
  0 0 1 0 0
  0 0 0 1 1
Output: 3

Key Insight:

• Each unvisited '1' is the start of a new island. DFS from it, marking every connected '1' as '0' (visited). Count how many times you start a DFS.

Solution:

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

private void dfs(char[][] grid, int r, int c) {
    if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length
            || grid[r][c] != '1') return;
    grid[r][c] = '0';  // mark visited
    dfs(grid, r + 1, c);
    dfs(grid, r - 1, c);
    dfs(grid, r, c + 1);
    dfs(grid, r, c - 1);
}

Complexity:

Problem 3: Max Area of Island ⭐ MUST DO

Given a grid of 0s and 1s, return the area of the largest island. An island is a group of horizontally/vertically connected 1s.

Example:

CopyInput:
  0 0 1 0 0 0 0 1 0 0 0 0 0
  0 0 0 0 0 0 0 1 1 1 0 0 0
  0 1 1 0 1 0 0 0 0 0 0 0 0
  0 1 0 0 1 1 0 0 1 0 1 0 0
  0 1 0 0 1 1 0 0 1 1 1 0 0
  0 0 0 0 0 0 0 0 0 0 1 0 0
  0 0 0 0 0 0 0 1 1 1 0 0 0
  0 0 0 0 0 0 0 1 1 0 0 0 0
Output: 6

Key Insight:

• Same as Number of Islands but the DFS returns the size of the island instead of void. Accumulate 1 + dfs(up) + dfs(down) + dfs(left) + dfs(right) at each cell.

Solution:

Copypublic int maxAreaOfIsland(int[][] grid) {
    int maxArea = 0;
    for (int r = 0; r < grid.length; r++) {
        for (int c = 0; c < grid[0].length; c++) {
            if (grid[r][c] == 1) {
                maxArea = Math.max(maxArea, dfs(grid, r, c));
            }
        }
    }
    return maxArea;
}

private int dfs(int[][] grid, int r, int c) {
    if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length
            || grid[r][c] != 1) {
        return 0;
    }
    grid[r][c] = 0;  // mark visited
    int size = 1;
    size += dfs(grid, r + 1, c);
    size += dfs(grid, r - 1, c);
    size += dfs(grid, r, c + 1);
    size += dfs(grid, r, c - 1);
    return size;
}

Complexity:

Problem 4: Island Perimeter

Given a grid where 1 = land and 0 = water, return the perimeter of the single island.

Example:

CopyInput:
  0 1 0 0
  1 1 1 0
  0 1 0 0
  1 1 0 0
Output: 16

Key Insight:

• A land cell contributes 1 perimeter edge for every boundary it has — either with water (grid[r][c] == 0) or with the grid border. In the DFS, return 1 for every boundary or out-of-bounds hit, and 0 for already-visited cells. Mark visited cells with a sentinel (e.g. 2) to avoid counting them again.

Solution:

Copypublic int islandPerimeter(int[][] grid) {
    for (int r = 0; r < grid.length; r++) {
        for (int c = 0; c < grid[0].length; c++) {
            if (grid[r][c] == 1) {
                return dfs(grid, r, c);
            }
        }
    }
    return 0;
}

private int dfs(int[][] grid, int r, int c) {
    if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length
            || grid[r][c] == 0) {
        return 1; // boundary or water = exposed edge
    }
    if (grid[r][c] == 2) {
        return 0; // already visited
    }
    grid[r][c] = 2; // mark visited
    int perimeter = 0;
    perimeter += dfs(grid, r + 1, c);
    perimeter += dfs(grid, r - 1, c);
    perimeter += dfs(grid, r, c + 1);
    perimeter += dfs(grid, r, c - 1);
    return perimeter;
}

Complexity:

Problem 5: Number of Enclaves

Given a grid where 1 = land and 0 = water, return the number of land cells you cannot walk off the grid boundary from.

Example:

CopyInput:
  0 0 0 0
  1 0 1 0
  0 1 1 0
  0 0 0 0
Output: 3

Key Insight:

• Two-pass approach: first sink all land reachable from the border (they can escape), then count the remaining land cells (true enclaves). Uses the same border-DFS idea as Surrounded Regions.

Solution:

Copypublic int numEnclaves(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    // Sink all border-connected land
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if ((r == 0 || r == m - 1 || c == 0 || c == n - 1)
                    && grid[r][c] == 1) {
                dfs(grid, r, c);
            }
        }
    }
    // Count remaining land (enclaves)
    int count = 0;
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if (grid[r][c] == 1) {
                count++;
            }
        }
    }
    return count;
}

private void dfs(int[][] grid, int r, int c) {
    if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length
            || grid[r][c] != 1) {
        return;
    }
    grid[r][c] = 0;
    dfs(grid, r + 1, c);
    dfs(grid, r - 1, c);
    dfs(grid, r, c + 1);
    dfs(grid, r, c - 1);
}

Complexity:

Problem 6: Surrounded Regions ⭐ MUST DO

Given an m × n grid containing 'X' and 'O', capture all 'O' regions that are fully surrounded by 'X' by flipping them to 'X'. Border-connected 'O' regions are never captured.

Example:

CopyInput:                  Output:
X X X X                 X X X X
X O O X      →          X X X X
X X O X                 X X X X
X O X X                 X O X X  ← border-connected, stays

Key Insight:

• Never try to identify surrounded regions directly — it is hard to define "fully surrounded." Instead, identify the safe ones: any 'O' connected to the border cannot be surrounded. Mark those safe with a sentinel 'S', then flip every remaining 'O' to 'X' and restore 'S' back to 'O'.

Solution:

Copypublic void solve(char[][] grid) {
    int m = grid.length, n = grid[0].length;
    // Pass 1: protect border-connected O's by marking them 'S'
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if ((r == 0 || r == m - 1 || c == 0 || c == n - 1)
                    && grid[r][c] == 'O') {
                dfs(grid, r, c);
            }
        }
    }
    // Pass 2: flip remaining O's to X, restore S to O
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if (grid[r][c] == 'O') {
                grid[r][c] = 'X';
            } else if (grid[r][c] == 'S') {
                grid[r][c] = 'O';
            }
        }
    }
}

private void dfs(char[][] grid, int r, int c) {
    if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length
            || grid[r][c] != 'O') {
        return;
    }
    grid[r][c] = 'S'; // safe
    dfs(grid, r + 1, c);
    dfs(grid, r - 1, c);
    dfs(grid, r, c + 1);
    dfs(grid, r, c - 1);
}

Complexity:

Problem 7: Pacific Atlantic Water Flow ⭐ MUST DO [B75-417]

Return all cells from which water can flow to both the Pacific Ocean (top/left border) and Atlantic Ocean (bottom/right border). Water flows to equal or lower neighbors.

Example:

CopyInput:
  1 2 2 3 5
  3 2 3 4 4
  2 4 5 3 1
  6 7 1 4 5
  5 1 1 2 4
Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]

Key Insight:

• Instead of simulating flow from every cell, reverse the direction: start from each ocean's border and flow uphill (to equal or higher neighbors). A cell reachable from both oceans satisfies the condition.
• Run two separate DFS passes — one from the Pacific border, one from the Atlantic border — then find the intersection.

Solution:

Copypublic List<List<Integer>> pacificAtlantic(int[][] h) {
    int m = h.length, n = h[0].length;
    boolean[][] pac = new boolean[m][n], atl = new boolean[m][n];

    for (int i = 0; i < m; i++) {
        dfs(h, pac, i, 0, m, n); dfs(h, atl, i, n - 1, m, n);
    }
    for (int j = 0; j < n; j++) {
        dfs(h, pac, 0, j, m, n); dfs(h, atl, m - 1, j, m, n);
    }

    List<List<Integer>> result = new ArrayList<>();
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (pac[i][j] && atl[i][j]) {
                result.add(Arrays.asList(i, j));
            }
        }
    }
    return result;
}

private void dfs(int[][] h, boolean[][] visited, int r, int c, int m, int n) {
    visited[r][c] = true;
    int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
    for (int[] d : dirs) {
        int nr = r + d[0], nc = c + d[1];
        if (nr >= 0 && nr < m && nc >= 0 && nc < n
                && !visited[nr][nc] && h[nr][nc] >= h[r][c]) {
            dfs(h, visited, nr, nc, m, n);
        }
    }
}

Complexity:

Problem 8: Rotting Oranges ⭐ MUST DO

You are given a grid where 0 = empty, 1 = fresh orange, 2 = rotten orange. Every minute, any fresh orange adjacent to a rotten orange becomes rotten. Return the minimum number of minutes until no fresh orange remains, or -1 if impossible.

Example:

CopyInput:
  2 1 1
  1 1 0
  0 1 1
Output: 4

Input:
  2 1 1
  0 1 1
  1 0 1
Output: -1  (bottom-left fresh orange is isolated)

Key Insight:

• Multi-source BFS: start from ALL rotten oranges simultaneously (add all 2s to the queue at time=0). BFS naturally processes them level by level — each level = one minute. After BFS, scan for any remaining 1s to detect the impossible case.

Solution:

Copypublic int orangesRotting(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    Queue<int[]> queue = new LinkedList<>();
    int fresh = 0;

    // Add all rotten oranges to the queue at time 0
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if (grid[r][c] == 2) {
                queue.offer(new int[]{r, c});
            } else if (grid[r][c] == 1) {
                fresh++;
            }
        }
    }

    if (fresh == 0) {
        return 0;
    }

    int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
    int minutes = 0;

    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            int[] curr = queue.poll();
            int r = curr[0], c = curr[1];
            for (int[] d : dirs) {
                int nr = r + d[0], nc = c + d[1];
                if (nr >= 0 && nr < m && nc >= 0 && nc < n
                        && grid[nr][nc] == 1) {
                    grid[nr][nc] = 2;
                    fresh--;
                    queue.offer(new int[]{nr, nc});
                }
            }
        }
        minutes++;
    }

    return fresh == 0 ? minutes - 1 : -1;
}

Complexity:

Problem 9: Shortest Path in Binary Matrix ⭐ MUST DO

Given an n × n binary grid, return the length of the shortest clear path from the top-left (0,0) to the bottom-right (n-1,n-1). A clear path only goes through 0-cells and can move in all 8 directions. Return -1 if no such path exists.

Example:

CopyInput:  [[0,1],[1,0]]
Output: 2

Input:  [[0,0,0],[1,1,0],[1,1,0]]
Output: 4

Key Insight:

• BFS guarantees shortest path. Mark cells visited as you add them to the queue (set to 1) to avoid revisiting. The path length starts at 1 (the start cell counts). Handle the edge case where the start or end cell is blocked (value = 1) upfront.

Solution:

Copypublic int shortestPathBinaryMatrix(int[][] grid) {
    int n = grid.length;
    if (grid[0][0] == 1 || grid[n - 1][n - 1] == 1) {
        return -1;
    }

    Queue<int[]> queue = new LinkedList<>();
    queue.offer(new int[]{0, 0, 1}); // [row, col, pathLength]
    grid[0][0] = 1; // mark visited

    int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}};

    while (!queue.isEmpty()) {
        int[] curr = queue.poll();
        int r = curr[0], c = curr[1], len = curr[2];

        if (r == n - 1 && c == n - 1) {
            return len;
        }

        for (int[] d : dirs) {
            int nr = r + d[0], nc = c + d[1];
            if (nr >= 0 && nr < n && nc >= 0 && nc < n
                    && grid[nr][nc] == 0) {
                grid[nr][nc] = 1; // mark visited
                queue.offer(new int[]{nr, nc, len + 1});
            }
        }
    }

    return -1;
}

Complexity:

Problem 10: Nearest Car ⭐ MUST DO

Given a city grid where 'R' = renter, 'C' = available car, and 'X' = blocked, return the minimum number of steps from the renter to the nearest available car.

Example:

CopyGrid:
  0 0 0 0
  R X 0 0
  X 0 0 0
  0 C 0 0

Output: 3  (R → up → right×2 → down×2... shortest is 3 steps)

Key Insight:

• BFS guarantees the first time you reach a 'C' is the shortest path — DFS cannot guarantee this. Carry dist as a third value in every queue entry: [row, col, dist]. Mark cells visited as you add to the queue, not when you poll — otherwise the same cell gets enqueued multiple times.

Solution:

Copypublic int nearestCar(char[][] grid, int startRow, int startCol) {
    int m = grid.length, n = grid[0].length;
    boolean[][] visited = new boolean[m][n];
    Queue<int[]> queue = new LinkedList<>();

    queue.offer(new int[]{startRow, startCol, 0});
    visited[startRow][startCol] = true;

    int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};

    while (!queue.isEmpty()) {
        int[] curr = queue.poll();
        int r = curr[0], c = curr[1], dist = curr[2];

        if (grid[r][c] == 'C') {
            return dist; // nearest car found
        }

        for (int[] d : dirs) {
            int nr = r + d[0], nc = c + d[1];
            if (nr >= 0 && nr < m && nc >= 0 && nc < n
                    && !visited[nr][nc] && grid[nr][nc] != 'X') {
                visited[nr][nc] = true;
                queue.offer(new int[]{nr, nc, dist + 1});
            }
        }
    }

    return -1; // no car reachable
}

Complexity:

Problem 11: Course Schedule ⭐ MUST DO [B75-207]

Given numCourses and prerequisites pairs [a, b] meaning "a requires b", return true if it is possible to finish all courses (no circular dependency).

Example:

CopyInput:  numCourses = 2,  prerequisites = [[1,0]]           →  true
Input:  numCourses = 2,  prerequisites = [[1,0],[0,1]]     →  false  (cycle)

Key Insight:

• This is cycle detection in a directed graph. Two visited states are not enough — you need three: unvisited (0), currently in the DFS path (1), fully processed (2). State 1 means "we're currently exploring this node's descendants" — if we reach it again, we've found a cycle.

Solution:

Copypublic boolean canFinish(int numCourses, int[][] prerequisites) {
    List<List<Integer>> graph = new ArrayList<>();
    
    for (int i = 0; i < numCourses; i++) {
        graph.add(new ArrayList<>());
    }
    
    for (int[] p : prerequisites) {
        graph.get(p[1]).add(p[0]);
    }

    int[] state = new int[numCourses]; // 0=unvisited, 1=visiting, 2=done

    for (int i = 0; i < numCourses; i++) {
        if (state[i] == 0 && hasCycle(graph, i, state)) 
            return false;
    }

    return true;
}

private boolean hasCycle(List<List<Integer>> graph, int node, int[] state) {
    if (state[node] == 1) {
        return true;  // back edge = cycle
    }
    if (state[node] == 2) {
        return false;
    }
    state[node] = 1;
    for (int neighbor : graph.get(node)) {
        if (hasCycle(graph, neighbor, state)) 
            return true;
    }
    state[node] = 2;
    return false;
}

Complexity:

Problem 12: Course Schedule II ⭐ MUST DO

Given numCourses and prerequisites pairs [a, b] meaning "a requires b", return a valid order to take all courses. Return [] if impossible.

Example:

CopyInput:  numCourses = 4,  prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,1,2,3]  (or [0,2,1,3])
Input:  numCourses = 2,  prerequisites = [[1,0],[0,1]]
Output: []  (cycle)

Key Insight:

• Course Schedule I only needs to detect if a cycle exists (DFS). This problem also needs the ordering. Use Kahn's algorithm: build an in-degree array, then BFS from all nodes with zero in-degree (no prerequisites). Each time a node is processed, decrement its neighbors' in-degrees; any neighbor that reaches zero has all its prerequisites satisfied — add it to the queue. If the final order contains all courses, return it; otherwise a cycle prevented full completion.

Solution:

Copypublic int[] findOrder(int numCourses, int[][] prerequisites) {
    int[] inDegree = new int[numCourses];
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < numCourses; i++) {
        adj.add(new ArrayList<>());
    }
    for (int[] p : prerequisites) {
        adj.get(p[1]).add(p[0]);    // p[1] must come before p[0]
        inDegree[p[0]]++;
    }

    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < numCourses; i++) {
        if (inDegree[i] == 0) queue.offer(i);
    }

    int[] order = new int[numCourses];
    int idx = 0;
    while (!queue.isEmpty()) {
        int course = queue.poll();
        order[idx] = course;
        idx++;
        for (int next : adj.get(course)) {
            inDegree[next]--;
            if (inDegree[next] == 0) {
                queue.offer(next);
            }
        }
    }
    return idx == numCourses ? order : new int[]{};
}

Complexity:

Problem 13: Clone Graph ⭐ MUST DO [B75-133]

Deep copy a connected undirected graph. Each node has a value and a list of neighbors.

Example:

CopyInput:  [[2,4],[1,3],[2,4],[1,3]]  (adjacency list)
Output: deep copy of the same graph

Key Insight:

• Use a HashMap from original node → cloned node as the visited set. Before recursing into a neighbor, check if it's already cloned. This prevents infinite loops in cyclic graphs and reuses already-cloned nodes.

Solution:

Copypublic Node cloneGraph(Node node) {
    if (node == null) {
        return null;
    }
    return dfs(node, new HashMap<>());
}

private Node dfs(Node node, Map<Node, Node> cloned) {
    if (cloned.containsKey(node)) {
        return cloned.get(node);
    }
    Node clone = new Node(node.val);
    cloned.put(node, clone);                    // register before recursing
    for (Node neighbor : node.neighbors) {
        clone.neighbors.add(dfs(neighbor, cloned));
    }
    return clone;
}

Complexity:

Problem 14: Network Delay Time ⭐ MUST DO

This is Dijkstra's shortest path algorithm. Imagine a network of computers — how long until a signal sent from computer k reaches every computer? Given n nodes, a source k, and directed weighted edges times[i] = [u, v, w] (signal travels from u to v in w time), return the minimum time for all nodes to receive the signal, or -1 if any node is unreachable.

Example:

CopyInput:  times = [[2,1,1],[2,3,1],[3,4,1]], n=4, k=2
Output: 2

Input:  times = [[1,2,1]], n=2, k=2
Output: -1  (node 1 unreachable from 2)

Key Insight:

• This is single-source shortest path on a weighted directed graph. Dijkstra's processes nodes in order of their cheapest known cost using a min-heap. The answer is the maximum entry in the dist[] array — the time when the last node finally receives the signal. If any node remains at MAX_VALUE, it was unreachable.

Solution:

Copypublic int networkDelayTime(int[][] times, int n, int k) {
    
    List<List<int[]>> adj = new ArrayList<>();
    
    // <= n: nodes are 1-indexed, so we need slots 0..n. Slot 0 is unused.
    // Same reason dist is new int[n + 1] — avoids writing (node - 1) everywhere.
    
    for (int i = 0; i <= n; i++) {
        adj.add(new ArrayList<>());
    }
    
    for (int[] t : times) {
        adj.get(t[0]).add(new int[]{t[1], t[2]}); // from - [to (neighbor), weight]
    }

    int[] dist = new int[n + 1];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[k] = 0;

    // minHeap is sorted by a[0] (cost), not node id.  
    // Always process the cheapest known path first.
    PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
    minHeap.offer(new int[]{0, k}); // [cost, node]

    while (!minHeap.isEmpty()) {
        int[] curr = minHeap.poll();
        int cost = curr[0], node = curr[1];

        if (cost > dist[node]) {
        // Stale entry: we found a cheaper path to this node after 
        //  it was already added to the heap.
        // We can't remove the old entry, so we skip it here when 
        //  a better one was already processed.
            continue;
        }

        for (int[] neighbor : adj.get(node)) {
            int next = neighbor[0], weight = neighbor[1];
            int newCost = cost + weight;
            if (newCost < dist[next]) {
                dist[next] = newCost;
                minHeap.offer(new int[]{newCost, next});
            }
        }
    }

    // maxDist = the time the LAST node receives the signal (the bottleneck).
    // All nodes must be reachable for the network to be fully notified,
    // so we return the maximum shortest-path cost across all nodes.
    int maxDist = 0;
    for (int i = 1; i <= n; i++) {
        if (dist[i] == Integer.MAX_VALUE) {
            return -1; // unreachable node
        }
        maxDist = Math.max(maxDist, dist[i]);
    }
    return maxDist;
}

Complexity:

Quick Reference Table

When to Use Each Pattern

Grid DFS

• Treat each grid cell as a graph node with up to 4 neighbors
• DFS: mark visited in-place (overwrite cell value) to avoid extra space
• BFS: use a queue with (row, col) pairs for shortest path or level distance
• Always bounds-check before recursing: r >= 0 && r < m && c >= 0 && c < n
• Two-pass pattern: sink/mark border-connected cells first when you need to exclude them

Grid BFS (Unweighted Shortest Path)

• Use BFS when the problem asks for minimum steps or nearest cell in a grid
• Carry dist as a third value in the queue: queue.offer(new int[]{r, c, dist})
• BFS level order guarantees the first time you reach the target is the shortest path
• Multi-source BFS: add all source cells to the queue before starting — they all spread simultaneously at time 0

Graph DFS (Directed, Cycle Detection)

• Directed graph cycle detection: 3-state visited (unvisited, in-path, done)
• Undirected graph: 2-state boolean visited array is sufficient
• Build adjacency list from edge array before starting any traversal
• Run DFS from every unvisited node — disconnected components must all be checked

Topological Sort (Kahn's BFS)

• Directed graph where you need a valid processing order respecting dependencies
• Build in-degree array: inDegree[node] = number of incoming edges
• Start BFS from all zero-in-degree nodes; decrement neighbors on each pop; enqueue when they reach 0
• If final order size equals n → valid DAG; otherwise a cycle prevented full ordering

Graph DFS (Deep Copy)

• Use a map from original → clone to handle cycles and sharing
• Register the clone in the map before recursing into neighbors
• The map doubles as the visited set — no need for a separate boolean array

Dijkstra's (Weighted Shortest Path)

• Use when edges have different weights and you need minimum cost from a source
• Always use a min-heap ordered by cost: new PriorityQueue<>((a, b) -> a[0] - b[0])
• Skip stale heap entries: if (cost > dist[node]) continue
• Does not work with negative edge weights — use Bellman-Ford for that case

Common Mistakes to Avoid

Grid DFS Mistakes

1. Not guarding the same-color case in Flood Fill — if originalColor == newColor, the termination condition is never triggered and DFS loops forever
2. Marking visited on pop instead of on add (BFS) — in BFS, mark a cell visited when you add it to the queue, not when you poll it; otherwise the same cell gets added multiple times
3. Forgetting bounds check before grid access — always check r >= 0 && r < m && c >= 0 && c < n before accessing grid[r][c]
4. Mutating the input grid when it must be preserved — if the problem says not to modify the input, use a separate boolean[][] visited array instead of overwriting cell values
5. Off-by-one in Rotting Oranges — the last BFS level increments minutes even though no new oranges rot; subtract 1 from the final count, or use a loop structure that only increments when the queue is non-empty after processing

Graph DFS Mistakes

5. Using 2 states for directed cycle detection — a simple boolean visited array cannot distinguish "currently exploring" from "fully explored"; use 0/1/2 states
6. Not registering the clone before recursing — in Clone Graph, put the clone in the map before recursing into neighbors; otherwise cycles cause infinite recursion
7. Not building adjacency list before traversal — never work directly from the edge list during DFS; build the adjacency list first so neighbor lookups are O(degree) not O(E)

Topological Sort Mistakes

8. Wrong edge direction — for prerequisite [a, b] meaning "b before a", the edge goes b → a; add a to b's adjacency list and increment inDegree[a]; reversing this produces a backwards order
9. Not checking cycle via size — always verify idx == numCourses before returning the order; if a cycle exists, some nodes' in-degrees never reach 0 and the order will be incomplete

Dijkstra's Mistakes

10. Not skipping stale heap entries — a node can be added to the heap multiple times with different costs; always check if (cost > dist[node]) continue when polling
11. Using Dijkstra's with negative weights — Dijkstra's assumes once a node is settled at minimum cost it won't be updated again; negative edges break this guarantee
12. Off-by-one on node indexing — when nodes are 1-indexed (as in Network Delay Time), allocate dist[n+1] and start the loop at i=1