Graphs

Master this topic with zero to advance depth.

Graph Algorithms: The Zero-to-Hero Guide

A Graph $G = (V, E)$ is the ultimate tool for modeling relationships. From social networks to Google Maps, graphs are everywhere. Mastery involves understanding three things: Representation, Traversal, and Specific Patterns.

1. Representing Graphs: The Choice Matters

Representation	Memory	Edge Query	Use Case
Adjacency List	$O(V + E)$	$O(\text{degree})$	Sparse graphs (standard for most interviews).
Adjacency Matrix	$O(V^2)$	$O(1)$	Dense graphs where $E \\approx V^2$ .
Edge List	$O(E)$	$O(E)$	Used in Kruskal's or Bellman-Ford where edge iteration is key.

2. The Golden Rule of Traversals

A. Breadth-First Search (BFS) - "The Shortest Path King"

Process: Level-by-level using a Queue.
Visual: Like a ripple in a pond.
Guarantee: Finds the shortest path in an unweighted graph.

B. Depth-First Search (DFS) - "The Exhaustive Explorer"

Process: Deep-dive using Recursion/Stack.
Visual: Like exploring a maze.
Best For: Connectivity, Cycle detection, and Pathfinding (Backtracking).

3. Complexity Cheat Sheet

Algorithm	Goal	Complexity
BFS/DFS	Connectivity / Traversal	$O(V + E)$
Topological Sort	Ordering Dependencies (DAG)	$O(V + E)$
Dijkstra	Shortest Path (Weighted, No Neg)	$O(E \\log V)$
Bellman-Ford	Shortest Path (Handles Neg Weights)	$O(V \\cdot E)$
Floyd-Warshall	All-Pairs Shortest Path	$O(V^3)$
Prim's / Kruskal's	Minimum Spanning Tree (MST)	$O(E \\log V)$

4. The Expert's Mental Model

Is it a Graph?: If you see "Relationships", "Connections", or "States", it's a graph. Cells in a Grid are nodes; adjacent cells have edges.
Directed vs. Undirected: Does $A \\to B$ imply $B \\to A$ ? (e.g., Follower vs. Friend).
Weighted vs. Unweighted: Does the connection have a cost? (e.g., Distance vs. Connection).
Implicit Graphs: The graph isn't nodes/edges yet. Nodes are states and edges are logical transitions (e.g., Word Ladder).

[!IMPORTANT] For Grid Problems, avoid building an actual adjacency list. Use directional arrays dx = {0,0,1,-1} and dy = {1,-1,0,0} to traverse implicitly.

Course Schedule

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [a_i, b_i] indicates that you must take course b_i first if you want to take course a_i.

Return true if you can finish all courses. Otherwise, return false.

Visual Representation

Courses: 2, Prerequisites: [[1, 0]]
Graph: 0 -> 1
Cycle? No. Result: true

Prerequisites: [[1, 0], [0, 1]]
Graph: 0 <-> 1 (Cycle!)
Cycle? Yes. Result: false

Medium

Examples

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
To take course 1 you should have finished course 0. So it is possible.

Approach 1

Level II: Intermediate (DFS - Cycle Detection)

Intuition

A graph is a Directed Acyclic Graph (DAG) if there are no Back Edges during DFS. We use three states for each node: 0 (unvisited), 1 (visiting/in current path), and 2 (visited). If we encounter a node with state 1, a cycle exists.

Thought Process

Build an adjacency list.
For each course, if not visited, launch DFS.
In DFS:
- Mark node as 1 (visiting).
- Traverse neighbors. If a neighbor is in state 1, return false (cycle).
- Mark node as 2 (fully processed).
If no cycle is found for any node, return true.

Pattern: DFS Cycle Detection

⏱ O(V + E) - Standard DFS traversal.💾 O(V + E) - Adjacency list + recursion stack.

Detailed Dry Run

pre=[[1,0],[0,1]]

Node	State	Neighbors	Result
0	1	[1]	Launch DFS(1)
1	1	[0]	0 is state 1! CYCLE!
Return	-	-	false

java

import java.util.*;

public class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<Integer>[] adj = new List[numCourses];
        for (int i = 0; i < numCourses; i++) adj[i] = new ArrayList<>();
        for (int[] p : prerequisites) adj[p[1]].add(p[0]);

        int[] visited = new int[numCourses]; // 0: unvisited, 1: visiting, 2: visited
        for (int i = 0; i < numCourses; i++) {
            if (hasCycle(i, adj, visited)) return false;
        }
        return true;
    }

    private boolean hasCycle(int u, List<Integer>[] adj, int[] visited) {
        if (visited[u] == 1) return true;
        if (visited[u] == 2) return false;

        visited[u] = 1;
        for (int v : adj[u]) {
            if (hasCycle(v, adj, visited)) return true;
        }
        visited[u] = 2;
        return false;
    }
}

Approach 2

Level III: Optimal (Kahn's Algorithm - BFS)

Intuition

Kahn's algorithm uses In-Degrees to peel off nodes with no dependencies. This is the gold standard for Topological Sort as it's iterative and avoids recursion stack issues.

Thought Process

Calculate the in-degree of each course (number of prerequisites).
Add all courses with in-degree == 0 to a queue.
While the queue is not empty:
- Pop a course, increment completed count.
- For each course that depends on it, decrement its in-degree.
- If in-degree becomes 0, add to queue.
If completed == numCourses, return true.

Pattern: Topological Sort

⏱ O(V + E) - Each node and edge is processed once.💾 O(V + E) - For the adjacency list and in-degree array.

Detailed Dry Run

num=2, pre=[[1,0]]

Pop	Queue	In-Degrees	Count
-	[0]	[0:0, 1:1]	0
0	[1]	[1:0]	1
1	[]	-	2
Result: 2 == 2 (True)

java

import java.util.*;

public class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] indegree = new int[numCourses];
        List<Integer>[] adj = new List[numCourses];
        for (int i = 0; i < numCourses; i++) adj[i] = new ArrayList<>();
        
        for (int[] p : prerequisites) {
            adj[p[1]].add(p[0]);
            indegree[p[0]]++;
        }

        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) if (indegree[i] == 0) q.add(i);

        int count = 0;
        while (!q.isEmpty()) {
            int curr = q.poll();
            count++;
            for (int neighbor : adj[curr]) {
                if (--indegree[neighbor] == 0) q.add(neighbor);
            }
        }
        return count == numCourses;
    }
}

Number of Islands

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Visual Representation

Grid:
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

Islands: 3 (Top-left, Middle, Bottom-right)

Medium

Examples

Input: grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]
Output: 3
Three distinct connected groups of '1's.

Approach 1

Level II: Intermediate (Union-Find)

Intuition

Each land cell '1' can be seen as a node. Adjacent '1's belong to the same connected component. We can use the Disjoint Set Union (DSU) to group these cells and count the number of resulting sets.

Thought Process

Count total '1's in the grid (initial component count).
Iterate through every cell. If it's a '1', check its Right and Down neighbors.
If a neighbor is also '1', perform a union. If they were in different sets, decrement the component count.
Return the final count of components.

Pattern: Disjoint Set Union (DSU)

⏱ O(M * N * alpha(MN)) - alpha is the inverse Ackermann function.💾 O(M * N) - For the parent array in DSU.

Detailed Dry Run

Grid: [[1,1], [0,1]]

Cell	Neighbors	Action	Sets
(0,0)	(0,1) is '1'	Union(0,1)	{0,1}, {1,1} (Count: 2)
(0,1)	(1,1) is '1'	Union(1,1)	{0,1,1,1} (Count: 1)
Result: 1

java

class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) return 0;
        int rows = grid.length, cols = grid[0].length;
        DSU dsu = new DSU(grid);
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == '1') {
                    if (r + 1 < rows && grid[r + 1][c] == '1') dsu.union(r * cols + c, (r + 1) * cols + c);
                    if (c + 1 < cols && grid[r][c + 1] == '1') dsu.union(r * cols + c, r * cols + (c + 1));
                }
            }
        }
        return dsu.count;
    }
    class DSU {
        int[] parent; int count;
        DSU(char[][] grid) {
            int m = grid.length, n = grid[0].length;
            parent = new int[m * n];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (grid[i][j] == '1') {
                        parent[i * n + j] = i * n + j;
                        count++;
                    }
                }
            }
        }
        int find(int i) { if (parent[i] == i) return i; return parent[i] = find(parent[i]); }
        void union(int i, int j) {
            int rootI = find(i), rootJ = find(j);
            if (rootI != rootJ) { parent[rootI] = rootJ; count--; }
        }
    }
}

Approach 2

Level III: Optimal (DFS / BFS)

Intuition

Each cell '1' is a node, and adjacent '1's have edges. We can use a traversal to find Connected Components. When we find a '1', we launch a DFS/BFS to visit all reachable '1's and mark them as '0' ("sinking" the island) to avoid re-visiting.

Thought Process

Iterate through every cell (r, c).
If grid[r][c] == '1':
- Increment count.
- Launch DFS starting from (r, c).
In DFS:
- Reached Water or Out of Bounds? Return.
- Mark current cell as '0' (visited).
- Recurse in 4 directions.

Pattern: Connected Components / Flood Fill

⏱ O(M * N) - Each cell is visited constant number of times.💾 O(M * N) - Recursion stack in the worst case (all land).

Detailed Dry Run

Grid: [[1,1], [0,1]]

i, j	Val	Action	Count
0,0	'1'	Start DFS. Sink (0,0), (0,1), (1,1)	1
0,1	'0'	Skip	1
1,1	'0'	Skip	1
Final Count: 1

java

public class Solution {
    public int numIslands(char[][] grid) {
        int count = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    count++;
                    dfs(grid, i, j);
                }
            }
        }
        return count;
    }
    private void dfs(char[][] grid, int r, int c) {
        if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length || grid[r][c] == '0') return;
        grid[r][c] = '0'; // Sink it
        dfs(grid, r + 1, c);
        dfs(grid, r - 1, c);
        dfs(grid, r, c + 1);
        dfs(grid, r, c - 1);
    }
}

Clone Graph

Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph.

Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors.

Visual Representation

1 -- 2
|    |
4 -- 3

Clone:
1' -- 2'
|     |
4' -- 3'

Medium

Examples

Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]
Node 1 is connected to 2 and 4. Node 2 is connected to 1 and 3, etc.

Approach 1

Level II: Intermediate (BFS + HashMap)

Intuition

BFS uses a queue to visit nodes level-by-level. By using a HashMap to store original -> clone, we can manage complexity and cycles. Every time we encounter a neighbor, if it's not in the map, we clone it and add to the queue.

Thought Process

Use a HashMap to store originalNode -> clonedNode.
Push the start node to a queue and create its clone.
While the queue is not empty:
- Pop curr. For each neighbor nbr:
  - If nbr is NOT in the map (unvisited):
    - Create its clone and add it to the map.
    - Push nbr to the queue.
  - Add the cloneMap.get(nbr) to the cloneMap.get(curr)'s neighbors list.
Return the clone of the input node.

Pattern: BFS with Mapping

⏱ O(V + E) - Standard BFS traversal.💾 O(V) - For the queue and the mapping.

Detailed Dry Run

1 -- 2

Map	Queue	Action
{1:1'}	[1]	Init
{1:1', 2:2'}	[2]	Pop 1, clone 2, add 2' to 1' neighbors
{1:1', 2:2'}	[]	Pop 2, 1 is in map, add 1' to 2' neighbors

java

import java.util.*;

public class Solution {
    public Node cloneGraph(Node node) {
        if (node == null) return null;
        Map<Node, Node> map = new HashMap<>();
        map.put(node, new Node(node.val));
        Queue<Node> q = new LinkedList<>();
        q.add(node);

        while (!q.isEmpty()) {
            Node curr = q.poll();
            for (Node nbr : curr.neighbors) {
                if (!map.containsKey(nbr)) {
                    map.put(nbr, new Node(nbr.val));
                    q.add(nbr);
                }
                map.get(curr).neighbors.add(map.get(nbr));
            }
        }
        return map.get(node);
    }
}

Approach 2

Level III: Optimal (DFS + HashMap)

Intuition

DFS is often more concise for graph cloning as it mimics the structure of the graph through the call stack. The HashMap acts as our "visited" set while also storing the deep copies.

Thought Process

Use a HashMap to store originalNode -> clonedNode.
In DFS function:
- If the node is NULL, return NULL.
- If the node is already in the map, return the existing clone.
- Otherwise, create a new clone and add it to the map.
- For each neighbor of the original node, recursively call DFS and add the result to the clone's neighbor list.
Return the DFS call for the input node.

Pattern: DFS with Mapping

⏱ O(V + E) - Each node and edge is visited once.💾 O(V) - For the recursion stack and the mapping.

Detailed Dry Run

1 -> [2, 4]

Map	Call	Action
{}	DFS(1)	Create 1', Map {1:1'}, Call DFS(2)
{1:1'}	DFS(2)	Create 2', Map {1:1', 2:2'}, Call DFS(3)
...	...	...
{1:1', 2:2', 3:3', 4:4'}	DFS(4)	Return 4' to 1' neighbors list

java

import java.util.*;

public class Solution {
    private Map<Node, Node> visited = new HashMap<>();
    public Node cloneGraph(Node node) {
        if (node == null) return null;
        if (visited.containsKey(node)) return visited.get(node);

        Node clone = new Node(node.val);
        visited.put(node, clone);

        for (Node neighbor : node.neighbors) {
            clone.neighbors.add(cloneGraph(neighbor));
        }
        return clone;
    }
}

Pacific Atlantic Water Flow

There is an m x n rectangular island that borders both the Pacific Ocean and Atlantic Ocean. The Pacific Ocean touches the island's left and top edges, and the Atlantic Ocean touches the island's right and bottom edges.

Water can flow to a neighboring cell (north, south, east, west) if the neighboring cell's height is less than or equal to the current cell's height.

Return a list of grid coordinates where rain water can flow to both the Pacific and Atlantic oceans.

Visual Representation

Pacific Ocean
   |  1  2  2  3  2  |
   |  3  2  3  4  4  |
   |  2  4  5  3  1  | Atlantic Ocean
   |  6  7  1  4  5  |
   |  5  1  1  2  4  |

Medium

Examples

Input: heights = [[1,2,2,3,2],[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]]
Cells at these coordinates can flow to both oceans.

Approach 1

Level I: Brute Force (DFS from Every Cell)

Intuition

For every single cell in the grid, we start a traversal (DFS) to see if we can reach both the Pacific and Atlantic oceans. A cell can reach an ocean if there is a path of decreasing or equal heights to the boundary.

Thought Process

For each cell (r, c):
- Run canReachPacific(r, c) using DFS.
- Run canReachAtlantic(r, c) using DFS.
- If both are true, add (r, c) to results.

Why it's inefficient

We repeat the same exploration many times for neighboring cells. Many paths are re-calculated.

⏱ O((M * N)^2) - For each of MN cells, we might explore MN cells.💾 O(M * N) - Recursion stack.

Detailed Dry Run

Grid: [[1, 2], [1, 1]]

Cell	Reach Pac?	Reach Atl?	Result
(0,0)	Yes (Edge)	No (Trapped)	No
(0,1)	Yes (Edge)	Yes (Edge)	YES

java

class Solution {
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        List<List<Integer>> res = new ArrayList<>();
        int R = heights.length, C = heights[0].length;
        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                if (canReach(heights, r, c, true, new boolean[R][C]) && 
                    canReach(heights, r, c, false, new boolean[R][C])) {
                    res.add(Arrays.asList(r, c));
                }
            }
        }
        return res;
    }
    private boolean canReach(int[][] h, int r, int c, boolean isPac, boolean[][] vis) {
        if (isPac && (r == 0 || c == 0)) return true;
        if (!isPac && (r == h.length - 1 || c == h[0].length - 1)) return true;
        vis[r][c] = true;
        int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
        for (int[] d : dirs) {
            int nr = r + d[0], nc = c + d[1];
            if (nr >= 0 && nr < h.length && nc >= 0 && nc < h[0].length && !vis[nr][nc] && h[nr][nc] <= h[r][c]) {
                if (canReach(h, nr, nc, isPac, vis)) return true;
            }
        }
        return false;
    }
}

Approach 2

Level III: Optimal (DFS from Ocean Coasts)

Intuition

Instead of asking "Can this cell reach the ocean?", we ask "What cells can the ocean reach?". Water flows from high to low, so if we start at the ocean and go uphill (height >= current), we can find all reachable cells efficiently.

Thought Process

Create two boolean grids: canReachPacific and canReachAtlantic.
Start DFS from all Pacific boundary cells (left and top edges) and mark reachable uphill cells in canReachPacific.
Start DFS from all Atlantic boundary cells (right and bottom edges) and mark reachable uphill cells in canReachAtlantic.
Cells marked in both grids are the result.

Pattern: Inverse Search / Multi-Source DFS

⏱ O(M * N) - Each cell is visited twice (once for each ocean).💾 O(M * N) - For the boolean grids and recursion stack.

Detailed Dry Run

Grid: [[1,2],[1,1]]

Ocean	Start Cells	Reachable (Uphill)
Pacific	(0,0),(0,1),(1,0)	(0,0), (0,1), (1,0)
Atlantic	(1,1),(0,1),(1,0)	(1,1), (0,1), (1,0)
Intersection: (0,1), (1,0), (1,1)

java

class Solution {
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        List<List<Integer>> res = new ArrayList<>();
        int R = heights.length, C = heights[0].length;
        boolean[][] pac = new boolean[R][C], atl = new boolean[R][C];
        
        for (int i = 0; i < R; i++) { dfs(heights, i, 0, pac); dfs(heights, i, C - 1, atl); }
        for (int i = 0; i < C; i++) { dfs(heights, 0, i, pac); dfs(heights, R - 1, i, atl); }

        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                if (pac[r][c] && atl[r][c]) res.add(Arrays.asList(r, c));
            }
        }
        return res;
    }
    private void dfs(int[][] h, int r, int c, boolean[][] vis) {
        vis[r][c] = true;
        int[][] dirs = {{0,1}, {0,-1}, {1,0}, {-1,0}};
        for (int[] d : dirs) {
            int nr = r + d[0], nc = c + d[1];
            if (nr >= 0 && nr < h.length && nc >= 0 && nc < h[0].length && !vis[nr][nc] && h[nr][nc] >= h[r][c]) {
                dfs(h, nr, nc, vis);
            }
        }
    }
}

Rotting Oranges

You are given an m x n grid where each cell can have one of three values:

0 representing an empty cell,
1 representing a fresh orange, or
2 representing a rotten orange.

Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.

Visual Representation

Minute 0: [[2,1,1],[1,1,0],[0,1,1]]
Minute 1: [[2,2,1],[2,1,0],[0,1,1]]
Minute 2: [[2,2,2],[2,2,0],[0,1,1]]
Minute 3: [[2,2,2],[2,2,0],[0,2,1]]
Minute 4: [[2,2,2],[2,2,0],[0,2,2]]
Result: 4

Medium

Examples

Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4
Fresh oranges at (0,1), (0,2), (1,0), (1,1), (2,1), (2,2) rot in 4 minutes.

Approach 1

Level I: Brute Force (Simulation)

Intuition

Simulate the rotting process minute by minute. In each minute, look for fresh oranges that are adjacent to any rotten orange. Mark them to rot in the next minute. Repeat this until no new oranges rot.

Thought Process

In a loop:
- Check every cell. If it's fresh ('1') and has a rotten neighbor ('2'), mark it to rot.
- Update the grid. Increment time.
- If no orange rotted in this round, stop.
After the loop, check if any fresh oranges remain.

Why it's inefficient

We iterate through the entire $M \times N$ grid multiple times (up to $M \times N$ times).

⏱ O((M * N)^2) - We may loop $M \times N$ times, each scanning the whole grid.💾 O(M * N) - To keep track of which oranges rot in the next step.

Detailed Dry Run

Grid: [[2,1,1],[0,1,1],[1,0,1]] Min 1: (0,0) rots (0,1). Grid: [[2,2,1],...] Min 2: (0,1) rots (0,2). Grid: [[2,2,2],...] ...

java

class Solution {
    public int orangesRotting(int[][] grid) {
        int R = grid.length, C = grid[0].length, time = 0;
        while (true) {
            List<int[]> toRot = new ArrayList<>();
            for (int r = 0; r < R; r++) {
                for (int c = 0; c < C; c++) {
                    if (grid[r][c] == 1) {
                        if (hasRottenNeighbor(grid, r, c)) toRot.add(new int[]{r, c});
                    }
                }
            }
            if (toRot.isEmpty()) break;
            for (int[] cell : toRot) grid[cell[0]][cell[1]] = 2;
            time++;
        }
        for (int[] row : grid) for (int val : row) if (val == 1) return -1;
        return time;
    }
    private boolean hasRottenNeighbor(int[][] grid, int r, int c) {
        int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
        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] == 2) return true;
        }
        return false;
    }
}

Approach 2

Level III: Optimal (Multi-source BFS)

Intuition

Rotting spreads like a wave. BFS is perfect for level-by-level spreading. Instead of one source, we start with all initial rotten oranges in the queue.

Thought Process

Count fresh oranges and add all rotten orange coordinates to a Queue.
While queue is not empty and fresh > 0:
- For all oranges currently in the queue (this level/minute):
  - Poll an orange, visit its 4 neighbors.
  - If neighbor is fresh:
    - Mark it rotten, decrement fresh, add to queue.
- Increment minutes after processing each level.
Return minutes if fresh == 0, else -1.

Pattern: Multi-source BFS

⏱ O(M * N) - Each cell is visited once.💾 O(M * N) - Queue size in worst case.

Detailed Dry Run

Grid: [[2,1,1],[1,1,0],[0,1,1]]

Queue: [(0,0)], Fresh: 6
Min 1: Rot (0,1), (1,0). Queue: [(0,1),(1,0)], Fresh: 4
Min 2: Rot (0,2), (1,1). Queue: [(0,2),(1,1)], Fresh: 2 ...

java

import java.util.*;

public class Solution {
    public int orangesRotting(int[][] grid) {
        Queue<int[]> q = new LinkedList<>();
        int fresh = 0, R = grid.length, C = grid[0].length;
        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                if (grid[r][c] == 2) q.add(new int[]{r, c});
                else if (grid[r][c] == 1) fresh++;
            }
        }
        if (fresh == 0) return 0;
        int mins = 0;
        int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
        while (!q.isEmpty() && fresh > 0) {
            mins++;
            int size = q.size();
            for (int i = 0; i < size; i++) {
                int[] curr = q.poll();
                for (int[] d : dirs) {
                    int nr = curr[0] + d[0], nc = curr[1] + d[1];
                    if (nr >= 0 && nr < R && nc >= 0 && nc < C && grid[nr][nc] == 1) {
                        grid[nr][nc] = 2; fresh--; q.add(new int[]{nr, nc});
                    }
                }
            }
        }
        return fresh == 0 ? mins : -1;
    }
}

Course Schedule II

Return the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.

Visual Representation

Prerequisites: [[1, 0], [2, 0], [3, 1], [3, 2]]
Graph:
0 -> 1 -> 3
0 -> 2 -> 3
Possible Order: [0, 1, 2, 3] or [0, 2, 1, 3]

Medium

Examples

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,1,2,3]
To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0.

Approach 1

Level II: Intermediate (DFS - Post-order)

Intuition

In a DAG, if we perform DFS and record nodes in Post-order (after visiting all neighbors), and then reverse that list, we get a topological sort. We must also check for cycles using the recursion stack.

Thought Process

Build adjacency list.
Use a visited set to track globally visited nodes and a path (recursion stack) set for cycle detection.
In DFS(u):
- If u in path, return False (cycle found).
- If u in visited, return True (already processed).
- Add u to path and visited.
- DFS neighbors. If any fails, return False.
- Remove u from path and append u to a Result List.
Call DFS for all unvisited nodes. Reverse the result list.

Pattern: DFS Topological Sort

⏱ O(V + E) - Visits each node and edge once.💾 O(V + E) - Adjacency list and recursion depth.

Detailed Dry Run

num=2, pre=[[1,0]]

Call	Path	Result	Action
DFS(0)	{0}	[]	Visit 1
DFS(1)	{0,1}	[1]	No neighbors, backtrack
-	{0}	[1,0]	Done with 0
Reverse [1,0] -> [0,1]

java

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        List<Integer>[] adj = new List[numCourses];
        for (int i = 0; i < numCourses; i++) adj[i] = new ArrayList<>();
        for (int[] p : prerequisites) adj[p[1]].add(p[0]);

        int[] visited = new int[numCourses]; // 0: unvisited, 1: visiting, 2: visited
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            if (hasCycle(i, adj, visited, res)) return new int[0];
        }
        Collections.reverse(res);
        return res.stream().mapToInt(i -> i).toArray();
    }
    private boolean hasCycle(int u, List<Integer>[] adj, int[] visited, List<Integer> res) {
        if (visited[u] == 1) return true;
        if (visited[u] == 2) return false;
        visited[u] = 1;
        for (int v : adj[u]) if (hasCycle(v, adj, visited, res)) return true;
        visited[u] = 2;
        res.add(u);
        return false;
    }
}

Approach 2

Level III: Optimal (Kahn's Algorithm - BFS)

Intuition

Kahn's algorithm uses the concept of in-degrees (number of incoming edges). Nodes with 0 in-degree are ready to be taken. We repeatedly take such nodes and 'remove' their outgoing edges, potentially creating new 0 in-degree nodes.

Thought Process

Calculate indegree for all nodes.
Add all nodes with indegree == 0 to a Queue.
While queue is not empty:
- Pop u, add it to the result list.
- For each neighbor v of u:
  - Decrement indegree[v].
  - If indegree[v] == 0, add v to queue.
If result length == numCourses, return it; otherwise, a cycle exists.

Pattern: Topological Sort (BFS)

⏱ O(V + E) - Standard traversal.💾 O(V + E) - For adjacency list and indegree mapping.

Detailed Dry Run

2 courses, 1 -> 0

Indegrees: {0:1, 1:0}
Queue: [1]
Pop 1, Res: [1], Indegree 0 becomes 0, Queue [0]
Pop 0, Res: [1, 0] Result: [1, 0]

java

class Solution {
    public 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]);
            indegree[p[0]]++;
        }
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) if (indegree[i] == 0) q.add(i);
        int[] res = new int[numCourses];
        int count = 0;
        while (!q.isEmpty()) {
            int curr = q.poll();
            res[count++] = curr;
            for (int neighbor : adj.get(curr)) {
                if (--indegree[neighbor] == 0) q.add(neighbor);
            }
        }
        return count == numCourses ? res : new int[0];
    }
}

Graph Valid Tree

You have a graph of n nodes labeled from 0 to n - 1. You are given an array edges where edges[i] = [a_i, b_i] indicates that there is an undirected edge between nodes a_i and b_i in the graph.

Return true if the edges of the given graph make up a valid tree, and false otherwise.

Visual Representation

n=5, edges=[[0,1],[0,2],[0,3],[1,4]]

    0
   /|\n  1 2 3
  |
  4
Valid Tree! Result: true

Medium

Examples

Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
Output: true
All nodes are connected and there are no cycles.

Approach 1

Level I: Brute Force (DFS / BFS)

Intuition

A graph is a tree if it is connected and has no cycles. We can perform a traversal from any node and check:

Did we visit all $N$ nodes?
Did we encounter any already-visited nodes during traversal (cycle)?

Thought Process

Build adjacency list.
Start DFS from node 0.
Keep track of visited nodes. For each neighbor, make sure it's not the immediate parent (to handle undirected edges).
If a neighbor is already in visited, return False (cycle).
After DFS, check if visited.size() == n.

Pattern: Cycle Detection in Undirected Graph

⏱ O(V + E) - Standard traversal.💾 O(V + E) - Adjacency list and visited set.

Detailed Dry Run

n=3, edges=[[0,1],[1,2],[2,0]]

DFS(0): mark 0 visited, neighbor 1.
DFS(1): mark 1 visited, neighbor 0 (skip), neighbor 2.
DFS(2): mark 2 visited, neighbor 1 (skip), neighbor 0 (ALREADY VISITED!) -> Cycle found, return False.

java

class Solution {
    public boolean validTree(int n, int[][] edges) {
        if (edges.length != n - 1) return false;
        List<Integer>[] adj = new List[n];
        for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
        for (int[] e : edges) { adj[e[0]].add(e[1]); adj[e[1]].add(e[0]); }
        Set<Integer> visited = new HashSet<>();
        if (!dfs(0, -1, adj, visited)) return false;
        return visited.size() == n;
    }
    private boolean dfs(int u, int p, List<Integer>[] adj, Set<Integer> vis) {
        if (vis.contains(u)) return false;
        vis.add(u);
        for (int v : adj[u]) {
            if (v == p) continue;
            if (!dfs(v, u, adj, vis)) return false;
        }
        return true;
    }
}

Approach 2

Level III: Optimal (Union-Find)

Intuition

This is the most efficient way to check for both conditions. As we add edges, if two nodes already have the same root, adding an edge between them creates a cycle. Connectivity is guaranteed if we process exactly $N-1$ edges without cycles.

Thought Process

Fundamental Tree Property: A valid tree with $N$ nodes MUST have exactly $N-1$ edges. If len(edges) != n - 1, return False.
Use Union-Find (DSU) with Path Compression.
For each edge (u, v):
- Find roots of u and v.
- If roots are the same, return False (cycle detected).
- Otherwise, union them.
If all edges processed, return True.

Pattern: Disjoint Set Union (DSU)

⏱ O(E * alpha(N)) - Where alpha is the inverse Ackermann function (nearly constant).💾 O(V) - For the parent/rank arrays.

Detailed Dry Run

n=4, edges=[[0,1],[1,2],[2,3]]

Edge (0,1): Union(0,1). Roots: 0,1. OK.
Edge (1,2): Union(1,2). Roots: 0,2. OK.
Edge (2,3): Union(2,3). Roots: 0,3. OK. All connected, no cycles. True.

java

class Solution {
    public boolean validTree(int n, int[][] edges) {
        if (edges.length != n - 1) return false;
        int[] parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
        for (int[] e : edges) {
            int root1 = find(parent, e[0]), root2 = find(parent, e[1]);
            if (root1 == root2) return false;
            parent[root1] = root2;
        }
        return true;
    }
    private int find(int[] parent, int i) {
        if (parent[i] == i) return i;
        return parent[i] = find(parent, parent[i]);
    }
}

Minimum Height Trees

A tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.

For a tree of $n$ nodes, you can choose any node as the root. The height of the tree is the maximum distance between the root and any leaf.

Return a list of all MHTs' root labels.

Visual Representation

n = 4, edges = [[1, 0], [1, 2], [1, 3]]

  0
  |
  1
 / \n2   3
Root 1 has height 1. Other roots have height 2.
Result: [1]

Medium

Examples

Input: n = 4, edges = [[1, 0], [1, 2], [1, 3]]
Output: [1]
Root 1 gives the minimum height tree.

Approach 1

Level I: Brute Force (DFS/BFS from every node)

Intuition

To find the root that minimizes height, we can treat every node as the root one-by-one, perform a BFS/DFS to find its height, and pick the minimum.

Thought Process

For each node $i$ $i$ from $0$ $0$ to $n-1$ $n - 1$ :
- Start a BFS/DFS from $i$ .
- Find the maximum distance from $i$ to any other node (this is the height).
Record the height of each node. Find the minimum height.
Return all nodes that produce this minimum height.

Why it's inefficient

For each of the $N$ nodes, we traverse $V+E$ elements. This leads to $O(N^2)$ complexity.

⏱ O(N^2) - MN traversal.💾 O(V + E) - Adjacency list.

Detailed Dry Run

n=3, edges=[[0,1],[1,2]]

Root 0: Height 2 (path 0-1-2)
Root 1: Height 1 (paths 1-0, 1-2)
Root 2: Height 2 (path 2-1-0) Min Height: 1. Result: [1]

java

class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        if (n == 1) return Collections.singletonList(0);
        List<Integer>[] adj = new List[n];
        for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
        for (int[] e : edges) { adj[e[0]].add(e[1]); adj[e[1]].add(e[0]); }
        
        Map<Integer, Integer> heights = new HashMap<>();
        int minH = n;
        for (int i = 0; i < n; i++) {
            int h = getHeight(i, adj, n);
            heights.put(i, h);
            minH = Math.min(minH, h);
        }
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < n; i++) if (heights.get(i) == minH) res.add(i);
        return res;
    }
    private int getHeight(int root, List<Integer>[] adj, int n) {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{root, 0});
        boolean[] vis = new boolean[n];
        vis[root] = true;
        int maxD = 0;
        while (!q.isEmpty()) {
            int[] curr = q.poll();
            maxD = Math.max(maxD, curr[1]);
            for (int v : adj[curr[0]]) {
                if (!vis[v]) { vis[v] = true; q.add(new int[]{v, curr[1] + 1}); }
            }
        }
        return maxD;
    }
}

Approach 2

Level III: Optimal (Leaf Removal - BFS)

Intuition

The center of a tree is limited to 1 or 2 nodes. If we continuously remove the 'outer layers' (leaves), we will eventually converge on the center. This is similar to Kahn's algorithm but for undirected trees.

Thought Process

Use an adjacency list and calculate the degree of each node.
Add all nodes with degree == 1 to a Queue (initial leaves).
In a loop, while remainingNodes > 2:
- Subtract current leaves count from remainingNodes.
- For each leaf in the queue:
  - Pop it, find its only neighbor nbr.
  - Decrement degree[nbr].
  - If degree[nbr] becomes 1, add nbr to the next level queue.
The final remaining nodes in the queue are the roots of MHTs.

Pattern: Topological Trimming

⏱ O(V + E) - Visits each node and edge once.💾 O(V + E) - Adjacency list.

Detailed Dry Run

n=4, edges=[[1,0],[1,2],[1,3]]

Degrees: {0:1, 1:3, 2:1, 3:1}. Leaves: [0, 2, 3]
remainingNodes = 4. 4 > 2 is true.
Remove 0,2,3. Neighbors: 1's degree 3->0. But we only decrement once for each leaf.
1's degree becomes 0. Queue empty. Result: [1]

java

class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        if (n < 2) {
            List<Integer> res = new ArrayList<>();
            for (int i = 0; i < n; i++) res.add(i);
            return res;
        }
        List<Set<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new HashSet<>());
        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]);
            adj.get(e[1]).add(e[0]);
        }
        List<Integer> leaves = new ArrayList<>();
        for (int i = 0; i < n; i++) if (adj.get(i).size() == 1) leaves.add(i);
        int remaining = n;
        while (remaining > 2) {
            remaining -= leaves.size();
            List<Integer> newLeaves = new ArrayList<>();
            for (int leaf : leaves) {
                int neighbor = adj.get(leaf).iterator().next();
                adj.get(neighbor).remove(leaf);
                if (adj.get(neighbor).size() == 1) newLeaves.add(neighbor);
            }
            leaves = newLeaves;
        }
        return leaves;
    }
}

Network Delay Time

You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (u_i, v_i, w_i), where u_i is the source node, v_i is the target node, and w_i is the time it takes for a signal to travel from source to target.

We will send a signal from a given node k. Return the minimum time it takes for all the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1.

Visual Representation

Nodes: 4, Times: [[2,1,1],[2,3,1],[3,4,1]], K: 2

   (1) <--1-- (2) --1--> (3) --1--> (4)

Signal at 2 reaches 1 and 3 at T=1.
Signal reaches 4 at T=2.
Result: 2

Medium

Examples

Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2
Signal reaches all nodes in 2 units of time.

Approach 1

Level I: Brute Force (Bellman-Ford)

Intuition

Bellman-Ford is a simpler shortest path algorithm that works by repeatedly relaxing all edges. After $N-1$ iterations, all shortest paths are guaranteed to be found.

Thought Process

Initialize dist array with infinity, dist[k] = 0.
For $N-1$ $N - 1$ iterations:
- For each edge $(u, v, w)$ $(u, v, w)$ in times:
  - If dist[u] + w < dist[v], update dist[v] = dist[u] + w.
After $N-1$ iterations, check max(dist). If any node is still at infinity, return -1.

Why it's Level I

It is computationally slower than Dijkstra but much simpler to implement correctly as it doesn't require a priority queue.

⏱ O(V * E) - Where V is nodes and E is edges.💾 O(V) - To store distances.

Detailed Dry Run

n=4, k=2, edges=[[2,1,1],[2,3,1],[3,4,1]]

Init: dist=[inf, 0, inf, inf] (using 1st index for node 1)
Iter 1:
- edge (2,1,1): dist[1]=1
- edge (2,3,1): dist[3]=1
- edge (3,4,1): dist[4]=1+1=2
Iter 2 & 3: No changes. Max dist = 2

java

class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        int[] dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[k] = 0;
        for (int i = 0; i < n - 1; i++) {
            for (int[] t : times) {
                int u = t[0], v = t[1], w = t[2];
                if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                }
            }
        }
        int maxT = 0;
        for (int i = 1; i <= n; i++) {
            if (dist[i] == Integer.MAX_VALUE) return -1;
            maxT = Math.max(maxT, dist[i]);
        }
        return maxT;
    }
}

Approach 2

Level III: Optimal (Dijkstra's Algorithm)

Intuition

This is a single-source shortest path problem on a weighted graph with non-negative weights. Dijkstra's algorithm uses a priority queue to always expand the node with the smallest known distance.

Thought Process

Build an adjacency list: u -> (v, w).
Initialize a dist array with infinity, dist[k] = 0.
Use a Min-Priority Queue to store (time, node) pairs.
While the queue is not empty:
- Pop (t, u). If t > dist[u], continue (stale entry).
- For each neighbor (v, weight) of u:
  - If dist[u] + weight < dist[v]:
    - Update dist[v] = dist[u] + weight and push to queue.
The answer is max(dist). If any node is unreachable (infinity), return -1.

Pattern: Shortest Path (Dijkstra)

⏱ O(E log V) where E is edges and V is nodes.💾 O(V + E) for the adjacency list.

Detailed Dry Run

n=4, k=2, edges=[[2,1,1],[2,3,1],[3,4,1]]

PQ (t,u)	dist[]	Action
(0,2)	[inf, 0, inf, inf]	Init
(1,1), (1,3)	[1, 0, 1, inf]	Pop 2, relax 1 & 3
(1,3)	[1, 0, 1, inf]	Pop 1
(2,4)	[1, 0, 1, 2]	Pop 3, relax 4
Max(dist) = 2

java

import java.util.*;

public class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        Map<Integer, List<int[]>> adj = new HashMap<>();
        for (int[] t : times) {
            adj.computeIfAbsent(t[0], x -> new ArrayList<>()).add(new int[]{t[1], t[2]});
        }

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

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        pq.offer(new int[]{0, k});

        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int t = curr[0], u = curr[1];
            if (t > dist[u]) continue;
            if (adj.containsKey(u)) {
                for (int[] next : adj.get(u)) {
                    int v = next[0], w = next[1];
                    if (dist[u] + w < dist[v]) {
                        dist[v] = dist[u] + w;
                        pq.offer(new int[]{dist[v], v});
                    }
                }
            }
        }

        int maxTime = 0;
        for (int i = 1; i <= n; i++) {
            if (dist[i] == Integer.MAX_VALUE) return -1;
            maxTime = Math.max(maxTime, dist[i]);
        }
        return maxTime;
    }
}

Cheapest Flights Within K Stops

There are n cities connected by some number of flights. You are given an array flights where flights[i] = [from_i, to_i, price_i] indicates that there is a flight from city from_i to city to_i with cost price_i.

You are also given three integers src, dst, and k. Return the cheapest price from src to dst with at most k stops. If there is no such route, return -1.

Visual Representation

(0) --100--> (1) --100--> (2)
 |                         ^
 |----------500------------|

K = 1:
Path 0 -> 1 -> 2: Price 200. Stops: 1 (OK)
Result: 200

K = 0:
Path 0 -> 2: Price 500. Stops: 0 (OK)
Path 0 -> 1 -> 2: Stops: 1 (FAIL)
Result: 500

Medium

Examples

Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
Output: 200
0 to 1 then to 2 is cheapest within 1 stop.

Approach 1

Level I: Brute Force (BFS with Depth)

Intuition

We can use BFS to explore paths level by level. Each level represents one 'stop'. We stop exploring when we exceed $K$ stops.

Thought Process

Build adjacency list.
Queue stores (node, current_price, current_stops).
Keep a min_prices array to prune paths that are more expensive than what we've seen at a certain node.
While queue is not empty:
- Pop (u, price, stops).
- If stops > k, skip.
- For each neighbor v with flight cost w:
  - If price + w < min_prices[v]:
    - min_prices[v] = price + w.
    - Push (v, price + w, stops + 1).

Pattern: Level-wise BFS

⏱ O(E * K) - Similar to Bellman-Ford in effect.💾 O(V * K) - In worst case queue size.

Detailed Dry Run

k=1, src=0, dst=2, edges=[[0,1,100],[1,2,100],[0,2,500]]

Queue: [(0, 0, -1)] (stops starts at -1 as first flight is 0 stops)
Pop (0,0,-1). Neighbors: (1, 100, 0), (2, 500, 0). min_prices: {1:100, 2:500}
Pop (1,100,0). Neighbors: (2, 200, 1). 200 < 500. min_prices: {2:200}
Pop (2,500,0). Neighbors: None.
Pop (2,200,1). Stops = k. Done. Result: 200

java

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        List<int[]>[] adj = new List[n];
        for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
        for (int[] f : flights) adj[f[0]].add(new int[]{f[1], f[2]});
        
        int[] minPrices = new int[n];
        Arrays.fill(minPrices, Integer.MAX_VALUE);
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{src, 0, -1});
        
        while (!q.isEmpty()) {
            int[] curr = q.poll();
            int u = curr[0], price = curr[1], stops = curr[2];
            if (stops >= k) continue;
            for (int[] next : adj[u]) {
                int v = next[0], w = next[1];
                if (price + w < minPrices[v]) {
                    minPrices[v] = price + w;
                    q.add(new int[]{v, price + w, stops + 1});
                }
            }
        }
        return minPrices[dst] == Integer.MAX_VALUE ? -1 : minPrices[dst];
    }
}

Approach 2

Level III: Optimal (Bellman-Ford / BFS)

Intuition

Dijkstra focuses on shortest distance, but here we have a constraint on the number of edges (stops). Bellman-Ford is perfect for this: we run the relaxation process exactly k+1 times to find the shortest path with at most k edges.

Thought Process

Initialize prices array with infinity, prices[src] = 0.
For i from 0 to k:
- Create a temp copy of prices to avoid using updated prices from the SAME iteration (level-wise relaxation).
- For each flight (u, v, cost):
  - If prices[u] is not infinity, update temp[v] = min(temp[v], prices[u] + cost).
- Set prices = temp.
Return prices[dst] if reachable, else -1.

Pattern: Constrained Shortest Path

⏱ O(K * E) where E is number of flights.💾 O(N) for price array.

Detailed Dry Run

k=1, src=0, dst=2, flights=[[0,1,100],[1,2,100],[0,2,500]]

Iter	0	1	2	Actions
Init	0	inf	inf	-
1	0	100	500	Relax edges from 0
2	0	100	200	Relax edge 1->2 (100+100=200)
Result: 200

java

import java.util.*;

public class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        int[] prices = new int[n];
        Arrays.fill(prices, Integer.MAX_VALUE);
        prices[src] = 0;

        for (int i = 0; i <= k; i++) {
            int[] temp = Arrays.copyOf(prices, n);
            for (int[] f : flights) {
                int u = f[0], v = f[1], cost = f[2];
                if (prices[u] == Integer.MAX_VALUE) continue;
                temp[v] = Math.min(temp[v], prices[u] + cost);
            }
            prices = temp;
        }

        return prices[dst] == Integer.MAX_VALUE ? -1 : prices[dst];
    }
}

Word Ladder

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words such that:

Every adjacent pair of words differs by a single letter.
Every s_i for 1 <= i <= k is in wordList.
s_k == endWord.

Return the number of words in the shortest transformation sequence, or 0 if no such sequence exists.

Visual Representation

Begin: "hit", End: "cog", List: ["hot","dot","dog","lot","log","cog"]

"hit" -> "hot" -> "dot" -> "dog" -> "cog"
Path length: 5

Hard

Examples

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
hit -> hot -> dot -> dog -> cog (5 words).

Approach 1

Level I: Brute Force (BFS with Word Comparison)

Intuition

The simplest BFS approach is to compare the current word with every word in the dictionary to find neighbors (words with only 1 character difference).

Thought Process

Use a Queue for BFS, starting with (beginWord, 1).
In each step:
- Pop word, dist.
- Iterate through every w in wordList:
  - If w is not visited and isNeighbor(word, w):
    - If w == endWord, return dist + 1.
    - Mark w as visited and add to queue.

Why it's Level I

If $N$ is the number of words, this involves $O(N)$ comparisons for every word we visit, leading to $O(N^2)$ total work.

⏱ O(N^2 * M) - Where N is word list size and M is word length.💾 O(N) - To store visited set.

Detailed Dry Run

"hit" -> "cog", ["hot", "dot", "dog", "cog"]

"hit": neighbors? Scan list. Found "hot".
"hot": neighbors? Scan list. Found "dot", "lot".
"dot": neighbors? Scan list. Found "dog".
"dog": neighbors? Scan list. Found "cog". DONE.

java

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> set = new HashSet<>(wordList);
        if (!set.contains(endWord)) return 0;
        Queue<Object[]> q = new LinkedList<>();
        q.add(new Object[]{beginWord, 1});
        Set<String> vis = new HashSet<>();
        vis.add(beginWord);
        while (!q.isEmpty()) {
            Object[] curr = q.poll();
            String word = (String) curr[0];
            int dist = (int) curr[1];
            if (word.equals(endWord)) return dist;
            for (String w : set) {
                if (!vis.contains(w) && isNbr(word, w)) {
                    vis.add(w); q.add(new Object[]{w, dist + 1});
                }
            }
        }
        return 0;
    }
    private boolean isNbr(String s1, String s2) {
        int diff = 0;
        for (int i = 0; i < s1.length(); i++) if (s1.charAt(i) != s2.charAt(i)) if (++diff > 1) return false;
        return diff == 1;
    }
}

Approach 2

Level III: Optimal (BFS with Char Change)

Intuition

Instead of comparing with every word, we can generate all 26 possible neighbors for each character position. This is much faster when the alphabet size is small.

Thought Process

Store all words in a set for $O(1)$ lookups.
Use a Queue for BFS, starting with (beginWord, 1).
While the queue is not empty:
- Pop word, dist.
- For each character position $i$ $i$ in word:
  - Replace word[i] with every letter from 'a' to 'z'.
  - If the new string exists in the set:
    - If it's the endWord, return dist + 1.
    - Add to queue and remove from set (marking it visited).

Pattern: BFS State Generation

⏱ O(M * 26 * N) - Usually much faster than O(N^2 * M).💾 O(N * M) - To store the word set.

Detailed Dry Run

hit -> hot -> dot -> dog -> cog

hit: change h to i,j,k... change i to a,b,c... change t to a,b,c,s,o (hot!)
Add hot to queue, remove from set.
Process 'hot' similarly.

java

import java.util.*;

public class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> set = new HashSet<>(wordList);
        if (!set.contains(endWord)) return 0;
        Queue<String> q = new LinkedList<>();
        q.offer(beginWord);
        int level = 1;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                String curr = q.poll();
                if (curr.equals(endWord)) return level;
                char[] chars = curr.toCharArray();
                for (int j = 0; j < chars.length; j++) {
                    char orig = chars[j];
                    for (char c = 'a'; c <= 'z'; c++) {
                        chars[j] = c;
                        String next = new String(chars);
                        if (set.contains(next)) {
                            q.offer(next);
                            set.remove(next);
                        }
                    }
                    chars[j] = orig;
                }
            }
            level++;
        }
        return 0;
    }
}

Shortest Path in Binary Matrix

Given an n x n binary matrix grid, return the length of the shortest clear path in the matrix. If there is no clear path, return -1.

A clear path in a binary matrix is a path from the top-left cell (i.e., (0, 0)) to the bottom-right cell (i.e., (n - 1, n - 1)) such that:

All the visited cells of the path are 0.
All the adjacent cells of the path are 8-directionally connected.
The length of a clear path is the number of visited cells of this path.

Visual Representation

Grid:
0 0 0
1 1 0
1 1 0

Path: (0,0) -> (0,1) -> (1,2) -> (2,2)
Length: 4

Medium

Examples

Input: grid = [[0,0,0],[1,1,0],[1,1,0]]
Output: 4
Clear path found with 4 units length.

Approach 1

Level II: Intermediate (BFS without In-place Modification)

Intuition

A standard BFS using a visited set instead of modifying the input grid. This is often preferred in production code to avoid side effects.

Thought Process

Check starting and ending cells.
Use a visited set to store (r, c).
Queue stores (r, c, distance).
Standard 8-directional exploration.

Pattern: BFS with Visited Set

⏱ O(N^2) - Same as optimal but with higher constant factor due to hashing.💾 O(N^2) - For the visited set.

Detailed Dry Run

3x3 grid, (0,0) is clear.

Queue: [(0,0,1)], Visited: {(0,0)}
Pop (0,0,1). Neighbors: (0,1), (1,1), (1,0). Add all to Visited and Queue.
Continue until (n-1, n-1) is reached.

java

class Solution {
    public int shortestPathBinaryMatrix(int[][] grid) {
        int n = grid.length;
        if (grid[0][0] == 1 || grid[n-1][n-1] == 1) return -1;
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{0, 0, 1});
        Set<String> vis = new HashSet<>();
        vis.add("0,0");
        int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};
        while (!q.isEmpty()) {
            int[] curr = q.poll();
            int r = curr[0], c = curr[1], d = curr[2];
            if (r == n - 1 && c == n - 1) return d;
            for (int[] dr : dirs) {
                int nr = r + dr[0], nc = c + dr[1];
                String key = nr + "," + nc;
                if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] == 0 && !vis.contains(key)) {
                    vis.add(key); q.add(new int[]{nr, nc, d + 1});
                }
            }
        }
        return -1;
    }
}

Approach 2

Level III: Optimal (BFS with In-place Marking)

Intuition

To optimize space and constant time, we can mark visited cells directly in the grid (e.g., set grid[r][c] = 1). BFS finds the shortest path in an unweighted grid.

Thought Process

Early exits for blocked start/end.
Queue for BFS starting at (0, 0, 1).
Mark grid[0][0] = 1.
Explore all 8 neighbors using a predefined directions array.
If neighbor is 0, mark as 1 and queue it.

Pattern: 8-Direction BFS

⏱ O(N^2) - Every cell visited once.💾 O(N^2) - Worst case queue size (perimeter of search).

Detailed Dry Run

2x2 grid [[0,1],[1,0]]

(0,0) Start. Mark grid[0][0]=1.
Neighbors: (0,1)-X, (1,0)-X, (1,1)-OK.
(1,1) reached. Return 2.

java

class Solution {
    public int shortestPathBinaryMatrix(int[][] grid) {
        int n = grid.length;
        if (grid[0][0] == 1 || grid[n-1][n-1] == 1) return -1;
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{0, 0, 1});
        grid[0][0] = 1;
        int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};
        while (!q.isEmpty()) {
            int[] curr = q.poll();
            if (curr[0] == n - 1 && curr[1] == n - 1) return curr[2];
            for (int[] d : dirs) {
                int nr = curr[0] + d[0], nc = curr[1] + d[1];
                if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] == 0) {
                    grid[nr][nc] = 1;
                    q.add(new int[]{nr, nc, curr[2] + 1});
                }
            }
        }
        return -1;
    }
}

Alien Dictionary

There is a new alien language that uses the English alphabet. However, the order among the letters is unknown to you.

You are given a list of strings words from the alien language's dictionary, where the strings in words are sorted lexicographically by the rules of this new language.

Return a string of the unique letters in the new alien language sorted in lexicographically increasing order by the new language's rules. If there is no solution, return "". If there are multiple solutions, return any of them.

Visual Representation

Words: ["wrt","wrf","er","ett","rftt"]

Comparisons:
1. "wrt" vs "wrf" -> t comes before f (t -> f)
2. "wrf" vs "er" -> w comes before e (w -> e)
3. "er" vs "ett" -> r comes before t (r -> t)
4. "ett" vs "rftt" -> e comes before r (e -> r)

Graph: w -> e -> r -> t -> f
Result: "wertf"

Hard

Examples

Input: words = ["wrt","wrf","er","ett","rftt"]
Output: "wertf"
From the comparisons, the order is w < e < r < t < f.

Approach 1

Level II: Intermediate (Topological Sort / DFS)

Intuition

Alternatively, you can use DFS to perform a topological sort. For each character, we explore all its 'neighbors' and then add the character to a stack.

Thought Process

Graph preparation is the same as Level III.
Use a state map: 0 = unvisited, 1 = visiting (checking for cycles), 2 = visited.
In DFS(u):
- If state is 1, return cycle found.
- If state is 2, return OK.
- Set state to 1.
- DFS neighbors. If any fails, return false.
- Set state to 2 and prepend u to result list.

Pattern: DFS Cycle Detection

⏱ O(C) - Where C is total characters.💾 O(1) - alphabet size fix.

Detailed Dry Run

["wrt","wrf","er"]

t->f, w->e
DFS(w): DFS(e), prepend e, prepend w. Order: we...
DFS(r)... final order wertf.

java

class Solution {
    public String alienOrder(String[] words) {
        Map<Character, Set<Character>> adj = new HashMap<>();
        for (String w : words) for (char c : w.toCharArray()) adj.putIfAbsent(c, new HashSet<>());
        for (int i = 0; i < words.length - 1; i++) {
            String w1 = words[i], w2 = words[i+1];
            if (w1.length() > w2.length() && w1.startsWith(w2)) return "";
            for (int j = 0; j < Math.min(w1.length(), w2.length()); j++) {
                if (w1.charAt(j) != w2.charAt(j)) {
                    adj.get(w1.charAt(j)).add(w2.charAt(j));
                    break;
                }
            }
        }
        Map<Character, Integer> visited = new HashMap<>(); // 0: unvisited, 1: visiting, 2: visited
        StringBuilder sb = new StringBuilder();
        for (char c : adj.keySet()) if (!dfs(c, adj, visited, sb)) return "";
        return sb.reverse().toString();
    }
    private boolean dfs(char u, Map<Character, Set<Character>> adj, Map<Character, Integer> visited, StringBuilder sb) {
        if (visited.getOrDefault(u, 0) == 1) return false;
        if (visited.getOrDefault(u, 0) == 2) return true;
        visited.put(u, 1);
        for (char v : adj.get(u)) if (!dfs(v, adj, visited, sb)) return false;
        visited.put(u, 2);
        sb.append(u);
        return true;
    }
}

Approach 2

Level III: Optimal (Topological Sort / Kahn's)

Intuition

The sorted list of words gives us relative ordering of characters. This is a classic Topological Sort problem. We extract dependencies from adjacent words and then apply Kahn's algorithm.

Thought Process

Initialize a graph adj and indegree map for all unique characters.
Compare every two adjacent words word1 and word2:
- Find the first non-matching character c1 in word1 and c2 in word2.
- Add edge c1 -> c2 and increment indegree[c2].
- Edge case: If word2 is a prefix of word1 (e.g., "abc", "ab"), return "" (invalid).
Apply Kahn's Algorithm (standard BFS topological sort).
If the resulting string length != number of unique characters, a cycle exists; return "".

Pattern: Lexicographical Ordering / Kahn's

⏱ O(C) where C is the total number of characters in all words (comparison and graph building).💾 O(1) - alphabet size is fixed (26).

Detailed Dry Run

["wrt","wrf","er"]

t -> f, w -> e
Unique: {w,r,t,f,e}
Indegrees: f:1, e:1, others:0
Queue: [w, r, t]
Pop w: Order "w", e's indegree -> 0, Queue [r, t, e]
... final order "wertf"

java

import java.util.*;

public class Solution {
    public String alienOrder(String[] words) {
        Map<Character, Set<Character>> adj = new HashMap<>();
        Map<Character, Integer> indegree = new HashMap<>();
        for (String w : words) for (char c : w.toCharArray()) indegree.put(c, 0);
        for (int i = 0; i < words.length - 1; i++) {
            String w1 = words[i], w2 = words[i+1];
            if (w1.length() > w2.length() && w1.startsWith(w2)) return "";
            for (int j = 0; j < Math.min(w1.length(), w2.length()); j++) {
                if (w1.charAt(j) != w2.charAt(j)) {
                    if (!adj.getOrDefault(w1.charAt(j), new HashSet<>()).contains(w2.charAt(j))) {
                        adj.computeIfAbsent(w1.charAt(j), k -> new HashSet<>()).add(w2.charAt(j));
                        indegree.put(w2.charAt(j), indegree.get(w2.charAt(j)) + 1);
                    }
                    break;
                }
            }
        }
        Queue<Character> q = new LinkedList<>();
        for (char c : indegree.keySet()) if (indegree.get(c) == 0) q.add(c);
        StringBuilder sb = new StringBuilder();
        while (!q.isEmpty()) {
            char c = q.poll(); sb.append(c);
            if (adj.containsKey(c)) {
                for (char nbr : adj.get(c)) {
                    indegree.put(nbr, indegree.get(nbr) - 1);
                    if (indegree.get(nbr) == 0) q.add(nbr);
                }
            }
        }
        return sb.length() == indegree.size() ? sb.toString() : "";
    }
}

Minimum Cost to Connect All Points

You are given an array points representing integer coordinates of some points on a 2D-plane, where points[i] = [x_i, y_i].

The cost of connecting two points [x_i, y_i] and [x_j, y_j] is the manhattan distance between them: |x_i - x_j| + |y_i - y_j|.

Return the minimum cost to make all points connected. All points are connected if there is exactly one simple path between any two points.

Visual Representation

Points: [[0,0],[2,2],[3,10],[5,2],[7,0]]

     (3,10)
       |
       |
(0,0)-(2,2)-(5,2)-(7,0)

Min Cost to connect all points: 20

Hard

Examples

Input: points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
Output: 20
Points are connected with total manhattan distance 20.

Approach 1

Level II: Intermediate (Kruskal's Algorithm)

Intuition

Kruskal's algorithm works by sorting all potential edges by weight and adding them one by one if they don't form a cycle (using Union-Find).

Thought Process

Generate all $N(N-1)/2$ possible edges with their Manhattan distances.
Sort edges by weight.
Use Union-Find to process edges.
Add edge to MST if endpoints are in different components.
Stop when $N-1$ edges are added.

Why it's Level II

It's very intuitive but slightly slower for dense graphs ( $O(E \log E) = O(N^2 \log N)$ ) compared to Prim's $O(N^2)$ .

⏱ O(N^2 log N) - Due to sorting O(N^2) edges.💾 O(N^2) - To store all possible edges.

Detailed Dry Run

Points: [0,0], [2,2], [7,0]

Edges: (0,1):4, (1,2):7, (0,2):7.
Sort: [(0,1):4, (1,2):7, (0,2):7]
Add (0,1): Cost=4. OK.
Add (1,2): Cost=4+7=11. OK. Result: 11

java

class Solution {
    public int minCostConnectPoints(int[][] points) {
        int n = points.length;
        List<int[]> edges = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int d = Math.abs(points[i][0]-points[j][0]) + Math.abs(points[i][1]-points[j][1]);
                edges.add(new int[]{d, i, j});
            }
        }
        Collections.sort(edges, (a, b) -> a[0] - b[0]);
        int[] parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
        int res = 0, count = 0;
        for (int[] e : edges) {
            int rootU = find(e[1], parent), rootV = find(e[2], parent);
            if (rootU != rootV) {
                parent[rootU] = rootV;
                res += e[0]; count++;
                if (count == n - 1) break;
            }
        }
        return res;
    }
    private int find(int i, int[] p) {
        if (p[i] == i) return i;
        return p[i] = find(p[i], p);
    }
}

Approach 2

Level III: Optimal (Prim's Algorithm)

Intuition

For a dense graph (where every point connects to every other point), Prim's algorithm with a simple array is more efficient than Kruskal's or Prim's with a heap.

Thought Process

Maintain a minDist array where minDist[i] is the shortest distance from the current MST to point i.
Start with point 0, minDist[0] = 0.
In each of $N$ $N$ iterations:
- Find the unvisited point u with the smallest minDist.
- Add minDist[u] to total cost.
- Mark u as visited.
- For every unvisited point v, update minDist[v] = min(minDist[v], dist(u, v)).

Pattern: Prim's on Dense Graph

⏱ O(N^2) - No priority queue needed for dense graphs.💾 O(N) - To store minDist and visited status.

Detailed Dry Run

Points: [0,0], [2,2], [3,10]

Start with node 0.
Node 0 to 1: dist 4. Node 0 to 2: dist 13.
Choose node 1 (min dist 4). Total = 4.
Node 1 to 2: dist 9. 9 < 13. Update minDist[2] = 9.
Choose node 2. Total = 4 + 9 = 13. Result: 13

java

class Solution {
    public int minCostConnectPoints(int[][] points) {
        int n = points.length, res = 0, count = 0;
        boolean[] visited = new boolean[n];
        int[] minDist = new int[n];
        Arrays.fill(minDist, Integer.MAX_VALUE);
        minDist[0] = 0;
        while (count < n) {
            int u = -1;
            for (int i = 0; i < n; i++) {
                if (!visited[i] && (u == -1 || minDist[i] < minDist[u])) u = i;
            }
            visited[u] = true; res += minDist[u]; count++;
            for (int v = 0; v < n; v++) {
                if (!visited[v]) {
                    int d = Math.abs(points[u][0]-points[v][0]) + Math.abs(points[u][1]-points[v][1]);
                    if (d < minDist[v]) minDist[v] = d;
                }
            }
        }
        return res;
    }
}

Swim in Rising Water

You are given an n x n integer matrix grid where each value grid[i][j] represents the elevation at that point (i, j).

At time t, the water level everywhere is t. You can swim from a square to another 4-directionally adjacent square if and only if the elevation of both squares are at most t. You can swim infinite distances in zero time. You start at the top left square (0, 0) at time 0.

Return the least time until you can reach the bottom right square (n - 1, n - 1).

Visual Representation

Grid:
0 1 2
3 4 5
6 7 8

You start at 0. You need time 8 to reach 8 because the bottom-right corner itself is 8.
At t=8, all cells are <= 8, so a path exists.
Result: 8

Hard

Examples

Input: grid = [[0,2],[1,3]]
Output: 3
At time 3, we can swim along the path 0-1-3.

Approach 1

Level II: Intermediate (Binary Search on Answer + BFS)

Intuition

Since the possible time answers range from 0 to $N^2-1$ , we can binary search for the minimum time $T$ such that there is a path from $(0,0)$ to $(N-1,N-1)$ using only cells with elevation $\≤ T$ .

Thought Process

Search range low = 0, high = N*N - 1.
For each mid (candidate time):
- Run a BFS/DFS from (0,0).
- Only move to neighbors with grid[nr][nc] <= mid.
- If (N-1, N-1) is reachable, mid is possible; try lower.
- Otherwise, mid is impossible; try higher.

Why it's Level II

It's very robust and often easier to come up with than the Dijkstra/heap-based approach.

⏱ O(N^2 log(N^2)) = O(N^2 log N).💾 O(N^2) - For BFS visited array.

Detailed Dry Run

3x3, grid[0][0]=3, grid[2][2]=5

high=8, low=0. mid=4. Can we reach 2,2? Start (0,0) is 3. OK. BFS explores neighbors <= 4. If path exists, high=4.
mid=2. grid[0][0]=3 > 2. Impossible. low=3.
Continue binary search.

java

class Solution {
    public int swimInWater(int[][] grid) {
        int n = grid.length;
        int l = 0, r = n * n - 1, res = r;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (canReach(mid, grid)) {
                res = mid; r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return res;
    }
    private boolean canReach(int t, int[][] grid) {
        int n = grid.length;
        if (grid[0][0] > t) return false;
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{0, 0});
        boolean[][] vis = new boolean[n][n];
        vis[0][0] = true;
        int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
        while (!q.isEmpty()) {
            int[] curr = q.poll();
            if (curr[0] == n - 1 && curr[1] == n - 1) return true;
            for (int[] d : dirs) {
                int nr = curr[0] + d[0], nc = curr[1] + d[1];
                if (nr >= 0 && nr < n && nc >= 0 && nc < n && !vis[nr][nc] && grid[nr][nc] <= t) {
                    vis[nr][nc] = true; q.add(new int[]{nr, nc});
                }
            }
        }
        return false;
    }
}

Approach 2

Level III: Optimal (Dijkstra's Algorithm)

Intuition

This is a pathfinding problem where the weight of a path is the maximum elevation on that path. We want to find the path with the minimum such weight. This is a variant of Dijkstra where the 'distance' is the max-so-far elevation.

Thought Process

Use a Min-Heap/Priority Queue to store (max_elevation_so_far, r, c).
Start with (grid[0][0], 0, 0).
Keep a visited set to avoid cycles.
In each step:
- Pop (t, r, c). This t is the minimum time needed to reach this cell.
- If (r, c) is (n-1, n-1), return t.
- For each 4-directional neighbor (nr, nc):
  - The time needed to reach neighbor is max(t, grid[nr][nc]).
  - If unvisited, push to queue.

Pattern: Min-Max Path (Dijkstra)

⏱ O(N^2 log N) - Standard Dijkstra on N^2 nodes.💾 O(N^2) - For minDist array and PQ.

Detailed Dry Run

Grid: [[0,2],[1,3]]

PQ: [(0, 0, 0)]
Pop (0,0,0). Neighbors: (0,1): max(0,2)=2, (1,0): max(0,1)=1.
PQ: [(1, 1, 0), (2, 0, 1)]
Pop (1,1,0). Neighbors: (1,1): max(1,3)=3.
PQ: [(2, 0, 1), (3, 1, 1)]
Pop (2,0,1). Neighbors: (1,1): max(2,3)=3. (Already in PQ with 3, no update).
Pop (3,1,1). Reached (1,1). Return 3. Result: 3

java

import java.util.*;

public class Main {
    public static int swimInWater(int[][] grid) {
        int n = grid.length;
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        pq.offer(new int[]{grid[0][0], 0, 0});
        boolean[][] visited = new boolean[n][n];
        visited[0][0] = true;

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

        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int t = curr[0], r = curr[1], c = curr[2];
            if (r == n - 1 && c == n - 1) return t;

            for (int[] d : dirs) {
                int nr = r + d[0], nc = c + d[1];
                if (nr >= 0 && nr < n && nc >= 0 && nc < n && !visited[nr][nc]) {
                    visited[nr][nc] = true;
                    pq.offer(new int[]{Math.max(t, grid[nr][nc]), nr, nc});
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        // Test setup
    }
}

Critical Connections in a Network

There are n servers numbered from 0 to n - 1 connected by undirected server-to-server connections forming a network where connections[i] = [a_i, b_i] represents a connection between servers a_i and b_i.

Any connected graph with no cycles is a tree. A critical connection is a connection that, if removed, will make some servers unable to reach some other server.

Return all critical connections in the network in any order.

Visual Representation

Servers: 4, Connections: [[0,1],[1,2],[2,0],[1,3]]

  0---1---3
   \ / 
    2

Removing [1,3] splits the graph.
Removing [0,1], [1,2], or [2,0] doesn't split it (cycle 0-1-2).
Result: [[1,3]]

Hard

Examples

Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
Output: [[1,3]]
[1,3] is the only bridge.

Approach 1

Level I: Brute Force (Edge Removal + Connectivity)

Intuition

Try removing each edge one by one and check if the graph remains connected. If it doesn't, that edge is a critical connection.

Complexity

Time: $O(E * (V + E))$
Space: $O(V + E)$

⏱ O(E * (V + E))💾 O(V + E)

Detailed Dry Run

4 nodes, edges [[0,1],[1,2],[2,0],[1,3]]. Remove [1,3]: unreachable. Critical!

java

class Solution {
    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < connections.size(); i++) {
            if (isCritical(n, connections, i)) res.add(connections.get(i));
        }
        return res;
    }
    private boolean isCritical(int n, List<List<Integer>> connections, int skip) {
        List<Integer>[] adj = new List[n];
        for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
        for (int i = 0; i < connections.size(); i++) {
            if (i == skip) continue;
            List<Integer> e = connections.get(i);
            adj[e.get(0)].add(e.get(1)); adj[e.get(1)].add(e.get(0));
        }
        boolean[] vis = new boolean[n];
        return dfs(0, adj, vis) < n;
    }
    private int dfs(int u, List<Integer>[] adj, boolean[] vis) {
        vis[u] = true; int count = 1;
        for (int v : adj[u]) if (!vis[v]) count += dfs(v, adj, vis);
        return count;
    }
}

Approach 2

Level III: Optimal (Tarjan's Bridge-Finding Algorithm)

Intuition

Tarjan's algorithm uses DFS to find bridges by tracking discovery times and the lowest discovery time reachable via back-edges.

Pattern: Bridge Finding (Tarjan)

⏱ O(V + E)💾 O(V + E)

Detailed Dry Run

Graph: 0-1, 1-2, 2-0, 1-3. Bridge condition: low[v] > disc[u]. At node 1, child 3 has low[3]=3, disc[1]=1. 3 > 1 is TRUE. [1,3] is bridge.

java

class Solution {
    int timer = 0;
    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
        List<Integer>[] adj = new List[n];
        for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
        for (List<Integer> c : connections) { adj[c.get(0)].add(c.get(1)); adj[c.get(1)].add(c.get(0)); }
        int[] disc = new int[n], low = new int[n];
        Arrays.fill(disc, -1);
        List<List<Integer>> bridges = new ArrayList<>();
        dfs(0, -1, adj, disc, low, bridges);
        return bridges;
    }
    private void dfs(int u, int p, List<Integer>[] adj, int[] disc, int[] low, List<List<Integer>> bridges) {
        disc[u] = low[u] = timer++;
        for (int v : adj[u]) {
            if (v == p) continue;
            if (disc[v] == -1) {
                dfs(v, u, adj, disc, low, bridges);
                low[u] = Math.min(low[u], low[v]);
                if (low[v] > disc[u]) bridges.add(Arrays.asList(u, v));
            } else low[u] = Math.min(low[u], disc[v]);
        }
    }
}

Longest Path in a DAG

Given a Directed Acyclic Graph (DAG) and a source vertex src, find the distance to the farthest vertex from src.

In a general graph, finding the longest path is NP-hard. However, in a DAG, it can be solved in linear time using Topological Sort.

Visual Representation

Nodes: 0 to 5
Edges: (0,1,5), (0,2,3), (1,3,6), (1,2,2), (2,4,4), (2,5,2), (2,3,7), (3,4,-1), (4,5,-2)

Topological Order: 0, 1, 2, 3, 4, 5
Relax edges in this order to find max distances.

Hard

Examples

Input: n=6, src=1, edges=[[0,1,5],[0,2,3],[1,3,6],[1,2,2],[2,4,4],[2,5,2],[2,3,7],[3,4,-1],[4,5,-2]]
Output: [inf, 0, 2, 9, 8, 6]
Distances from node 1: to 3 is 9 (1->2->3 is 2+7), to 4 is 8, etc.

Approach 1

Level I: Brute Force (Recursion + Memoization)

Intuition

The longest path from a node u is max(weight(u, v) + longestPath(v)) for all neighbors v. Since the graph is a DAG, we can use memoization to avoid redundant computations.

Thought Process

Define dfs(u) as the longest path starting from node u.
In dfs(u):
- If u is already in memo, return memo[u].
- Initialize max_dist = 0 (or some base case).
- For each neighbor v with weight w:
  - max_dist = max(max_dist, w + dfs(v)).
- Store and return max_dist.

Complexity

Time: $O(V + E)$
Space: $O(V)$

⏱ O(V + E)💾 O(V)

Detailed Dry Run

src=1. Edges from 1: (3,6), (2,2).

dfs(3): edge (4,-1). dfs(4): edge (5,-2). dfs(5): 0.
dfs(4) = -1 + 0 = -1.
dfs(3) = -1 + -1 = -2. (Wait, let's say base case is 0 for sink).
dfs(1) = max(6 + dfs(3), 2 + dfs(2))...

java

class Solution {
    public int[] longestPath(int n, int src, List<Edge>[] adj) {
        Integer[] memo = new Integer[n];
        int[] res = new int[n];
        for (int i = 0; i < n; i++) res[i] = dfs(i, adj, memo);
        return res; // Distance from each node to sink
    }
    private int dfs(int u, List<Edge>[] adj, Integer[] memo) {
        if (memo[u] != null) return memo[u];
        int maxDist = 0;
        for (Edge e : adj[u]) maxDist = Math.max(maxDist, e.w + dfs(e.v, adj, memo));
        return memo[u] = maxDist;
    }
}

Approach 2

Level III: Optimal (Topological Sort + Relaxation)

Intuition

Processing nodes in topological order allows finding the longest path in $O(V+E)$ .

Pattern: DAG Relaxation

⏱ O(V + E)💾 O(V + E)

Detailed Dry Run

Order: 0,1,2,3,4,5. Relax edges from 1. 1->2->3 is longer than 1->3 directly.

java

class Solution {
    public int[] longestPath(int n, int src, List<int[]>[] adj) {
        Stack<Integer> s = new Stack<>(); boolean[] vis = new boolean[n];
        for (int i=0; i<n; i++) if (!vis[i]) topo(i, vis, s, adj);
        int[] dist = new int[n]; Arrays.fill(dist, -1000000); dist[src] = 0;
        while (!s.isEmpty()) {
            int u = s.pop();
            if (dist[u] != -1000000) {
                for (int[] e : adj[u]) if (dist[e[0]] < dist[u] + e[1]) dist[e[0]] = dist[u] + e[1];
            }
        }
        return dist;
    }
    private void topo(int u, boolean[] vis, Stack<Integer> s, List<int[]>[] adj) {
        vis[u] = true; for (int[] e : adj[u]) if (!vis[e[0]]) topo(e[0], vis, s, adj);
        s.push(u);
    }
}

Reconstruct Itinerary

You are given a list of airline tickets where tickets[i] = [from_i, to_i] represent the departure and the arrival airports of one flight. Reconstruct the itinerary in order and return it.

All of the tickets belong to a man who departs from "JFK", thus, the itinerary must begin with "JFK". If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string.

Visual Representation

Tickets: [["MUC","LHR"], ["JFK","MUC"], ["SFO","SJC"], ["LHR","SFO"]]

Graph: JFK -> MUC -> LHR -> SFO -> SJC
Result: ["JFK", "MUC", "LHR", "SFO", "SJC"]

Hard

Examples

Input: tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
Output: ["JFK","MUC","LHR","SFO","SJC"]
Standard path starting from JFK.

Approach 1

Level III: Optimal (Hierholzer's Algorithm)

Intuition

This is finding an Eulerian Path in a directed graph. An Eulerian Path visits every edge exactly once. Hierholzer's algorithm finds this by performing DFS and appending nodes to the result only when they have no more outgoing edges.

Thought Process

Build a graph where each node leads to a PriorityQueue of destinations (to handle lexicographical order requirement).
Start DFS from "JFK".
In DFS:
- While the current airport has outgoing tickets:
  - Pop the smallest destination and recurse.
- Add current airport to the head of the result list (or append and reverse at the end).

Pattern: Eulerian Path (Hierholzer)

⏱ O(E \\log E) due to sorting/priority queue.💾 O(V + E) for the graph.

Detailed Dry Run

JFK -> [MUC, SFO], MUC -> [LHR], LHR -> [JFK]

DFS(JFK): Pop MUC, DFS(MUC)
- DFS(MUC): Pop LHR, DFS(LHR)
  - DFS(LHR): Pop JFK... Final order built in reverse: [SFO, JFK, LHR, MUC, JFK]. Reverse it.

java

import java.util.*;

public class Main {
    private Map<String, PriorityQueue<String>> adj = new HashMap<>();
    private LinkedList<String> res = new LinkedList<>();

    public List<String> findItinerary(List<List<String>> tickets) {
        for (List<String> t : tickets) {
            adj.computeIfAbsent(t.get(0), x -> new PriorityQueue<>()).add(t.get(1));
        }
        dfs("JFK");
        return res;
    }

    private void dfs(String s) {
        PriorityQueue<String> pq = adj.get(s);
        while (pq != null && !pq.isEmpty()) {
            dfs(pq.poll());
        }
        res.addFirst(s);
    }
}

Shortest Path to Get All Keys

You are given an m x n grid grid where:

'.' is an empty cell.
'#' is a wall.
'@' is the starting point.
lowercase letters are keys.
uppercase letters are locks.

You start at the starting point and one move consists of walking one space in one of the four cardinal directions. You cannot walk outside the grid, or through a wall. If you walk over a key, you pick it up. If you walk over a lock and have the matching key, you can pass through it.

Return the lowest number of moves to acquire all keys. If it's impossible, return -1.

Visual Representation

Grid:
@ . a . #
# # # . #
b . A . B

Starting at @. Path:
1. Pick 'a'
2. Use 'a' to open 'A'
3. Pick 'b'
Done! Return shortest path length.

Hard

Examples

Input: grid = ["@.a.#","###.#","b.A.B"]
Output: 8
Shortest path to pick up all keys 'a' and 'b'.

Approach 1

Level III: Optimal (BFS with State - Bitmask)

Intuition

The 'state' of our BFS is not just our position (r, c), but also which keys we possess. We can represent the set of obtained keys as a bitmask. This turns the problem into a standard shortest path BFS in a state space of (r, c, mask).

Thought Process

Find start position @ and count total number of keys K.
Target mask is (1 << K) - 1.
Queue stores (r, c, mask, distance).
visited[r][c][mask] tracks seen states.
In each step:
- If current cell is a key, update newMask = mask | (1 << (key - 'a')).
- If newMask == targetMask, return dist.
- If current cell is a lock and we don't have the key, skip.
- Standard 4-direction BFS flow.

Pattern: BFS with State Bitmasking

⏱ O(M * N * 2^K) where K is number of keys.💾 O(M * N * 2^K) for visited array.

Detailed Dry Run

2 keys. Target mask = 11 (3). Start (0,0) mask 00.

Reach 'a' (0,2). Mask = 01.
Reach 'A' (2,2). Lock 'A' (bit 0) matches mask bit 0. Passage allowed.
Reach 'b' (2,0). Mask = 11. Target reached!

java

import java.util.*;

public class Main {
    public static int shortestPathAllKeys(String[] grid) {
        int m = grid.length, n = grid[0].length();
        int startR = -1, startC = -1, totalKeys = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                char c = grid[i].charAt(j);
                if (c == '@') { startR = i; startC = j; }
                else if (c >= 'a' && c <= 'f') totalKeys++;
            }
        }

        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{startR, startC, 0, 0});
        boolean[][][] visited = new boolean[m][n][1 << totalKeys];
        visited[startR][startC][0] = true;

        int[][] dirs = {{0,1}, {0,-1}, {1,0}, {-1,0}};
        while (!q.isEmpty()) {
            int[] curr = q.poll();
            int r = curr[0], c = curr[1], mask = curr[2], dist = curr[3];
            if (mask == (1 << totalKeys) - 1) return dist;

            for (int[] d : dirs) {
                int nr = r + d[0], nc = c + d[1];
                if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
                    char next = grid[nr].charAt(nc);
                    if (next == '#') continue;
                    int nextMask = mask;
                    if (next >= 'a' && next <= 'f') nextMask |= (1 << (next - 'a'));
                    if (next >= 'A' && next <= 'F' && (mask & (1 << (next - 'A'))) == 0) continue;
                    
                    if (!visited[nr][nc][nextMask]) {
                        visited[nr][nc][nextMask] = true;
                        q.offer(new int[]{nr, nc, nextMask, dist + 1});
                    }
                }
            }
        }
        return -1;
    }
}

Find the City With the Smallest Number of Neighbors at a Threshold Distance

There are n cities numbered from 0 to n-1. Given the array edges where edges[i] = [from_i, to_i, weight_i] represents a bidirectional weighted edge between cities from_i and to_i, and given the integer distanceThreshold.

Return the city with the smallest number of cities that are reachable through some path and whose distance is at most distanceThreshold. If there are multiple such cities, return the city with the greatest number.

Visual Representation

Cities 4, Edges: [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], Threshold 4

0 --3-- 1 --1-- 2
         \     /
          4---3
           (1)

City 0: Neighbors {1,2} (Dist 3, 4) - Count 2
City 3: Neighbors {1,2} (Dist 2, 1) - Count 2
... compare all, find min count.

Hard

Examples

Input: n = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4
Output: 3
City 3 has 2 neighbors within distance 4, same as city 0, but 3 > 0.

Approach 1

Level III: Optimal (Floyd-Warshall Algorithm)

Intuition

This problem requires finding all-pairs shortest paths to count how many cities are within the threshold for each city. Floyd-Warshall is the standard algorithm for all-pairs shortest paths in a small number of vertices ( $N \\≤ 100$ ).

Thought Process

Initialize a dist matrix of size $N \times N$ with infinity, and dist[i][i] = 0.
For each edge (u, v, w), set dist[u][v] = dist[v][u] = w.
Run Floyd-Warshall: three nested loops k, i, j to update dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]).
For each city i, count how many j have dist[i][j] <= distanceThreshold.
Tracking the minimum count and the maximum index among cities with that count.

Pattern: All-Pairs Shortest Path

⏱ O(N^3) (three nested loops).💾 O(N^2) for the distance matrix.

Detailed Dry Run

N=4, Threshold=4

After Floyd-Warshall, dist[0][1]=3, dist[0][2]=4, dist[0][3]=5.
City 0 count (<= 4): 2 (cities 1 and 2).
City 3 count (<= 4): dist[3][1]=2, dist[3][2]=1, dist[3][0]=5. Count 2 (cities 1 and 2).
Since counts are equal, pick city 3 (larger index).

java

import java.util.*;

public class Main {
    public static int findTheCity(int n, int[][] edges, int distanceThreshold) {
        int[][] dist = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dist[i], 1000000); // Infinity
            dist[i][i] = 0;
        }
        for (int[] e : edges) {
            dist[e[0]][e[1]] = dist[e[1]][e[0]] = e[2];
        }

        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }

        int minCount = n, resultLocal = -1;
        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = 0; j < n; j++) {
                if (dist[i][j] <= distanceThreshold) count++;
            }
            if (count <= minCount) {
                minCount = count;
                resultLocal = i;
            }
        }
        return resultLocal;
    }
}

← Previous TopicBacktracking

Next Topic →Trees

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.