🎯 JavaScript Graphs — Top 25 Interview Questions

---

Q1 — Number of Islands

🧠 How to Approach This

Step 1 — Recognize the pattern: Count connected components in a grid; DFS sinks each island.

Step 2 — Brute force (what NOT to do): Check every cell repeatedly — O(R²C²).

Step 3 — Optimal insight: DFS from each unvisited '1'; mark all reachable cells as '0'.

Step 4 — Algorithm:

1. Iterate all cells; if '1' → DFS to sink island, increment count

2. DFS: mark cell '0', recurse 4 directions

Step 5 — Edge cases: All water; all land; single cell.

function numIslands(grid) {
    const R = grid.length, C = grid[0].length;
    let count = 0;
    function dfs(r, c) {
        if (r < 0 || r >= R || c < 0 || c >= C || grid[r][c] !== '1') return;
        grid[r][c] = '0';
        dfs(r+1,c); dfs(r-1,c); dfs(r,c+1); dfs(r,c-1);
    }
    for (let r = 0; r < R; r++)
        for (let c = 0; c < C; c++)
            if (grid[r][c] === '1') { dfs(r, c); count++; }
    return count;
}

Time: O(R × C) | Space: O(R × C)

---

Q2 — Clone Graph

🧠 How to Approach This

Step 1 — Recognize the pattern: BFS with a visited Map storing original → clone.

Step 2 — Brute force (what NOT to do): Rebuild without tracking clones → infinite loop on cycles.

Step 3 — Optimal insight: Map from original node to its clone; create clone on first visit.

Step 4 — Algorithm:

1. BFS queue; on first visit create clone and add to map

2. For each neighbor: create if not seen; add to clone's neighbors

Step 5 — Edge cases: Null input; single node with no neighbors.

function cloneGraph(node) {
    if (!node) return null;
    const map = new Map();
    const queue = [node];
    map.set(node, { val: node.val, neighbors: [] });
    while (queue.length) {
        const curr = queue.shift();
        for (const nb of curr.neighbors) {
            if (!map.has(nb)) {
                map.set(nb, { val: nb.val, neighbors: [] });
                queue.push(nb);
            }
            map.get(curr).neighbors.push(map.get(nb));
        }
    }
    return map.get(node);
}

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

---

Q3 — Course Schedule (Cycle Detection)

🧠 How to Approach This

Step 1 — Recognize the pattern: Directed graph cycle detection — cycle means impossible to finish.

Step 2 — Brute force (what NOT to do): Try all orderings — O(n!).

Step 3 — Optimal insight: Kahn's topological sort; if all nodes processed → no cycle.

Step 4 — Algorithm:

1. Build graph + indegree array

2. Enqueue all indegree-0 nodes; process queue decrementing neighbors

3. If processed count === n → true

Step 5 — Edge cases: No prerequisites; self-loop.

function canFinish(n, prereqs) {
    const graph    = Array.from({ length: n }, () => []);
    const indegree = new Array(n).fill(0);
    for (const [a, b] of prereqs) { graph[b].push(a); indegree[a]++; }
    const queue = [];
    for (let i = 0; i < n; i++) if (indegree[i] === 0) queue.push(i);
    let count = 0;
    while (queue.length) {
        const node = queue.shift(); count++;
        for (const nb of graph[node]) if (--indegree[nb] === 0) queue.push(nb);
    }
    return count === n;
}

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

---

Q4 — Course Schedule II (Topological Order)

🧠 How to Approach This

Step 1 — Recognize the pattern: Same as Q3 but return the actual ordering.

Step 2 — Brute force (what NOT to do): DFS without tracking — O(V²).

Step 3 — Optimal insight: Kahn's BFS; collect order while processing.

Step 4 — Algorithm:

1. Same as Course Schedule

2. Append each dequeued node to order

3. Return order if complete, else []

Step 5 — Edge cases: Multiple valid orderings exist.

function findOrder(n, prereqs) {
    const graph    = Array.from({ length: n }, () => []);
    const indegree = new Array(n).fill(0);
    for (const [a, b] of prereqs) { graph[b].push(a); indegree[a]++; }
    const queue = [], order = [];
    for (let i = 0; i < n; i++) if (indegree[i] === 0) queue.push(i);
    while (queue.length) {
        const node = queue.shift(); order.push(node);
        for (const nb of graph[node]) if (--indegree[nb] === 0) queue.push(nb);
    }
    return order.length === n ? order : [];
}

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

---

Q5 — Pacific Atlantic Water Flow

🧠 How to Approach This

Step 1 — Recognize the pattern: Multi-source BFS from ocean borders inward; find cells reachable from both.

Step 2 — Brute force (what NOT to do): DFS from every cell to both oceans — O(R²C²).

Step 3 — Optimal insight: BFS from Pacific border AND Atlantic border separately; return intersection.

Step 4 — Algorithm:

1. BFS from top+left (Pacific); BFS from bottom+right (Atlantic)

2. Return cells in both visited sets

Step 5 — Edge cases: 1×1 grid; uniform height.

function pacificAtlantic(heights) {
    const R = heights.length, C = heights[0].length;
    const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
    function bfs(starts) {
        const visited = new Set(starts.map(([r,c]) => `${r},${c}`));
        const queue = [...starts];
        while (queue.length) {
            const [r, c] = queue.shift();
            for (const [dr, dc] of dirs) {
                const nr = r+dr, nc = c+dc;
                const key = `${nr},${nc}`;
                if (nr>=0&&nr<R&&nc>=0&&nc<C&&!visited.has(key)&&heights[nr][nc]>=heights[r][c]) {
                    visited.add(key); queue.push([nr, nc]);
                }
            }
        }
        return visited;
    }
    const pac = [], atl = [];
    for (let r = 0; r < R; r++) { pac.push([r, 0]); atl.push([r, C-1]); }
    for (let c = 0; c < C; c++) { pac.push([0, c]); atl.push([R-1, c]); }
    const pv = bfs(pac), av = bfs(atl);
    const res = [];
    for (let r = 0; r < R; r++) for (let c = 0; c < C; c++)
        if (pv.has(`${r},${c}`) && av.has(`${r},${c}`)) res.push([r, c]);
    return res;
}

Time: O(R × C) | Space: O(R × C)

---

Q6 — Surrounded Regions

🧠 How to Approach This

Step 1 — Recognize the pattern: Mark border-connected 'O' cells safe; flip remaining 'O' to 'X'.

Step 2 — Brute force (what NOT to do): Check every 'O' for border reachability — repeated traversal.

Step 3 — Optimal insight: DFS from all border 'O' cells → mark safe; then flip/restore.

Step 4 — Algorithm:

1. DFS from border 'O' → mark as 'S'

2. Scan: 'O' → 'X', 'S' → 'O'

Step 5 — Edge cases: No 'O'; all border 'O'.

function solve(board) {
    const R = board.length, C = board[0].length;
    function dfs(r, c) {
        if (r < 0 || r >= R || c < 0 || c >= C || board[r][c] !== 'O') return;
        board[r][c] = 'S';
        dfs(r+1,c); dfs(r-1,c); dfs(r,c+1); dfs(r,c-1);
    }
    for (let r = 0; r < R; r++) { dfs(r, 0); dfs(r, C-1); }
    for (let c = 0; c < C; c++) { dfs(0, c); dfs(R-1, c); }
    for (let r = 0; r < R; r++) for (let c = 0; c < C; c++)
        board[r][c] = board[r][c] === 'S' ? 'O' : board[r][c] === 'O' ? 'X' : board[r][c];
}

Time: O(R × C) | Space: O(R × C)

---

Q7 — Rotting Oranges

🧠 How to Approach This

Step 1 — Recognize the pattern: Multi-source BFS from all rotten oranges simultaneously.

Step 2 — Brute force (what NOT to do): BFS from each rotten orange separately — O(R²C²).

Step 3 — Optimal insight: Enqueue all rotten at t=0; BFS spreads rot level by level.

Step 4 — Algorithm:

1. Enqueue all rotten (2), count fresh

2. BFS: each level = 1 minute; convert fresh neighbors to rotten, decrement fresh

3. Return minutes if fresh === 0, else -1

Step 5 — Edge cases: No fresh → 0; isolated fresh → -1.

function orangesRotting(grid) {
    const R = grid.length, C = grid[0].length;
    const queue = []; let fresh = 0;
    for (let r = 0; r < R; r++) for (let c = 0; c < C; c++) {
        if (grid[r][c] === 2) queue.push([r, c, 0]);
        if (grid[r][c] === 1) fresh++;
    }
    const dirs = [[1,0],[-1,0],[0,1],[0,-1]]; let mins = 0;
    while (queue.length) {
        const [r, c, t] = queue.shift(); mins = Math.max(mins, t);
        for (const [dr, dc] of dirs) {
            const nr = r+dr, nc = c+dc;
            if (nr>=0&&nr<R&&nc>=0&&nc<C&&grid[nr][nc]===1) {
                grid[nr][nc]=2; fresh--; queue.push([nr,nc,t+1]);
            }
        }
    }
    return fresh === 0 ? mins : -1;
}

Time: O(R × C) | Space: O(R × C)

---

Q8 — Walls and Gates

🧠 How to Approach This

Step 1 — Recognize the pattern: Multi-source BFS from all gates; fill rooms with shortest distance.

Step 2 — Brute force (what NOT to do): BFS from each room to nearest gate — O((RC)²).

Step 3 — Optimal insight: Multi-source BFS from all gates; distance propagates outward.

Step 4 — Algorithm:

1. Enqueue all gates (0)

2. BFS: set neighbor's dist = curr dist + 1 if currently INF

Step 5 — Edge cases: No gates; no rooms.

function wallsAndGates(rooms) {
    const INF = Infinity, R = rooms.length, C = rooms[0].length;
    const queue = [], dirs = [[1,0],[-1,0],[0,1],[0,-1]];
    for (let r = 0; r < R; r++) for (let c = 0; c < C; c++)
        if (rooms[r][c] === 0) queue.push([r, c]);
    while (queue.length) {
        const [r, c] = queue.shift();
        for (const [dr, dc] of dirs) {
            const nr = r+dr, nc = c+dc;
            if (nr>=0&&nr<R&&nc>=0&&nc<C&&rooms[nr][nc]===INF) {
                rooms[nr][nc] = rooms[r][c] + 1; queue.push([nr, nc]);
            }
        }
    }
}

Time: O(R × C) | Space: O(R × C)

---

Q9 — Redundant Connection

🧠 How to Approach This

Step 1 — Recognize the pattern: Find the edge that creates a cycle — Union-Find.

Step 2 — Brute force (what NOT to do): Remove each edge and check connectivity — O(E·(V+E)).

Step 3 — Optimal insight: Union-Find: when union returns false (same component), that edge is redundant.

Step 4 — Algorithm:

1. Process edges in order

2. union(u, v): if already connected → return [u,v]

Step 5 — Edge cases: Multiple valid answers → return last one.

function findRedundantConnection(edges) {
    const n  = edges.length;
    const uf = new UnionFind(n + 1);
    for (const [u, v] of edges) {
        if (!uf.union(u, v)) return [u, v];
    }
    return [];
}

Time: O(n · α(n)) | Space: O(n)

---

Q10 — Number of Connected Components

🧠 How to Approach This

Step 1 — Recognize the pattern: Union-Find component count.

Step 2 — Brute force (what NOT to do): Adjacency matrix DFS — O(V²).

Step 3 — Optimal insight: Start with n components; each successful union reduces by 1.

Step 4 — Algorithm:

1. Init count = n

2. For each edge: if union succeeds → count--

3. Return count

Step 5 — Edge cases: No edges → n; all connected → 1.

function countComponents(n, edges) {
    const uf = new UnionFind(n);
    let count = n;
    for (const [u, v] of edges) if (uf.union(u, v)) count--;
    return count;
}

Time: O(E · α(n)) | Space: O(n)

---

Q11 — Graph Valid Tree

🧠 How to Approach This

Step 1 — Recognize the pattern: Valid tree = n-1 edges + no cycle + connected.

Step 2 — Brute force (what NOT to do): Check every pair — O(V²).

Step 3 — Optimal insight: Union-Find: n-1 edges + all unions succeed.

Step 4 — Algorithm:

1. If edges.length !== n-1 → false

2. Union all; if any fails → false

Step 5 — Edge cases: n=1, edges=[] → true.

function validTree(n, edges) {
    if (edges.length !== n - 1) return false;
    const uf = new UnionFind(n);
    for (const [u, v] of edges) if (!uf.union(u, v)) return false;
    return true;
}

Time: O(E · α(n)) | Space: O(n)

---

Q12 — Word Ladder

🧠 How to Approach This

Step 1 — Recognize the pattern: BFS on implicit graph; words differing by 1 char are connected.

Step 2 — Brute force (what NOT to do): Try all combinations at each step — exponential.

Step 3 — Optimal insight: BFS; at each word try replacing each char with a-z.

Step 4 — Algorithm:

1. BFS queue with [word, length]

2. For each word: try all char substitutions; if in wordSet and unvisited → enqueue

3. Return length when endWord reached

Step 5 — Edge cases: endWord not in wordList → 0.

function ladderLength(beginWord, endWord, wordList) {
    const wordSet = new Set(wordList);
    if (!wordSet.has(endWord)) return 0;
    const queue = [[beginWord, 1]];
    while (queue.length) {
        const [word, len] = queue.shift();
        for (let i = 0; i < word.length; i++) {
            for (let c = 0; c < 26; c++) {
                const next = word.slice(0, i) + String.fromCharCode(97 + c) + word.slice(i + 1);
                if (next === endWord) return len + 1;
                if (wordSet.has(next)) { wordSet.delete(next); queue.push([next, len + 1]); }
            }
        }
    }
    return 0;
}

Time: O(M² × N) | Space: O(M × N)

---

Q13 — Shortest Path in Binary Matrix

🧠 How to Approach This

Step 1 — Recognize the pattern: BFS in grid from (0,0) to (n-1,n-1) with 8-directional moves.

Step 2 — Brute force (what NOT to do): DFS — doesn't guarantee shortest.

Step 3 — Optimal insight: BFS; level count = path length.

Step 4 — Algorithm:

1. If start or end blocked → -1

2. BFS [r, c, dist]; explore 8 directions

Step 5 — Edge cases: 1×1 grid with 0 → 1.

function shortestPathBinaryMatrix(grid) {
    const n = grid.length;
    if (grid[0][0] === 1 || grid[n-1][n-1] === 1) return -1;
    const queue = [[0, 0, 1]]; grid[0][0] = 1;
    const dirs  = [[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]];
    while (queue.length) {
        const [r, c, d] = queue.shift();
        if (r === n-1 && c === n-1) return d;
        for (const [dr, dc] of dirs) {
            const nr = r+dr, nc = c+dc;
            if (nr>=0&&nr<n&&nc>=0&&nc<n&&grid[nr][nc]===0) {
                grid[nr][nc] = 1; queue.push([nr, nc, d+1]);
            }
        }
    }
    return -1;
}

Time: O(n²) | Space: O(n²)

---

Q14 — Flood Fill

🧠 How to Approach This

Step 1 — Recognize the pattern: DFS from source pixel; recolor all connected same-color pixels.

Step 2 — Brute force (what NOT to do): Scan entire image repeatedly.

Step 3 — Optimal insight: DFS recursively recolors; early exit if new color equals old.

Step 4 — Algorithm:

1. If color === new color → return

2. DFS: recolor; recurse 4 directions for same old color

Step 5 — Edge cases: Source already has new color.

function floodFill(image, sr, sc, color) {
    const old = image[sr][sc];
    if (old === color) return image;
    function dfs(r, c) {
        if (r<0||r>=image.length||c<0||c>=image[0].length||image[r][c]!==old) return;
        image[r][c] = color;
        dfs(r+1,c); dfs(r-1,c); dfs(r,c+1); dfs(r,c-1);
    }
    dfs(sr, sc);
    return image;
}

Time: O(R × C) | Space: O(R × C)

---

Q15 — 01 Matrix (Distance to Nearest 0)

🧠 How to Approach This

Step 1 — Recognize the pattern: Multi-source BFS from all 0s outward.

Step 2 — Brute force (what NOT to do): BFS from each 1 to find nearest 0 — O(R²C²).

Step 3 — Optimal insight: Enqueue all 0s at distance 0; BFS expands distances for 1s.

Step 4 — Algorithm:

1. Init dist matrix; enqueue all 0s

2. BFS: dist[nr][nc] = dist[r][c] + 1 if smaller

Step 5 — Edge cases: Entire matrix is 0s.

function updateMatrix(mat) {
    const R = mat.length, C = mat[0].length;
    const dist = Array.from({ length: R }, () => new Array(C).fill(Infinity));
    const queue = [], dirs = [[1,0],[-1,0],[0,1],[0,-1]];
    for (let r = 0; r < R; r++) for (let c = 0; c < C; c++)
        if (mat[r][c] === 0) { dist[r][c] = 0; queue.push([r, c]); }
    while (queue.length) {
        const [r, c] = queue.shift();
        for (const [dr, dc] of dirs) {
            const nr = r+dr, nc = c+dc;
            if (nr>=0&&nr<R&&nc>=0&&nc<C&&dist[nr][nc]>dist[r][c]+1) {
                dist[nr][nc] = dist[r][c] + 1; queue.push([nr, nc]);
            }
        }
    }
    return dist;
}

Time: O(R × C) | Space: O(R × C)

---

Q16 — Network Delay Time

🧠 How to Approach This

Step 1 — Recognize the pattern: Shortest path from source to all nodes — Dijkstra's.

Step 2 — Brute force (what NOT to do): Bellman-Ford — O(VE), slower.

Step 3 — Optimal insight: Dijkstra with min-heap; return max distance.

Step 4 — Algorithm:

1. Build weighted adjacency list

2. Dijkstra from k; track dist array

3. Return Math.max(...dist) if all reachable, else -1

Step 5 — Edge cases: Disconnected graph; single node.

function networkDelayTime(times, n, k) {
    const graph = Array.from({ length: n + 1 }, () => []);
    for (const [u, v, w] of times) graph[u].push([v, w]);
    const dist = new Array(n + 1).fill(Infinity); dist[k] = 0;
    const pq = [[0, k]]; // [dist, node] — simulated min-heap
    while (pq.length) {
        pq.sort((a, b) => a[0] - b[0]);
        const [d, u] = pq.shift();
        if (d > dist[u]) continue;
        for (const [v, w] of graph[u]) {
            if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; pq.push([dist[v], v]); }
        }
    }
    const max = Math.max(...dist.slice(1));
    return max === Infinity ? -1 : max;
}

Time: O((V + E) log V) | Space: O(V + E)

---

Q17 — Swim in Rising Water

🧠 How to Approach This

Step 1 — Recognize the pattern: Find path minimizing maximum elevation — Dijkstra.

Step 2 — Brute force (what NOT to do): BFS for each possible time t — O(n⁴).

Step 3 — Optimal insight: Dijkstra treating cell value as cost; always expand min-cost cell.

Step 4 — Algorithm:

1. Priority queue [max_so_far, r, c]

2. Pop min; if destination → return

3. Push neighbors with max(current_max, neighbor_val)

Step 5 — Edge cases: 1×1 → grid[0][0].

function swimInWater(grid) {
    const n = grid.length, visited = new Set();
    const pq = [[grid[0][0], 0, 0]];
    const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
    while (pq.length) {
        pq.sort((a, b) => a[0] - b[0]);
        const [t, r, c] = pq.shift();
        if (r === n-1 && c === n-1) return t;
        const key = `${r},${c}`;
        if (visited.has(key)) continue;
        visited.add(key);
        for (const [dr, dc] of dirs) {
            const nr = r+dr, nc = c+dc;
            if (nr>=0&&nr<n&&nc>=0&&nc<n&&!visited.has(`${nr},${nc}`))
                pq.push([Math.max(t, grid[nr][nc]), nr, nc]);
        }
    }
    return -1;
}

Time: O(n² log n) | Space: O(n²)

---

Q18 — Alien Dictionary

🧠 How to Approach This

Step 1 — Recognize the pattern: Build ordering constraints from adjacent words; topological sort.

Step 2 — Brute force (what NOT to do): Compare all pairs — O(N²L).

Step 3 — Optimal insight: Adjacent words first mismatch → directed edge; Kahn's topological sort.

Step 4 — Algorithm:

1. Compare adjacent words; first mismatch gives edge c1 → c2

2. Topological sort on character graph

Step 5 — Edge cases: Cycle → ""; prefix violation → "".

function alienOrder(words) {
    const graph = new Map(), indeg = new Map();
    for (const w of words) for (const c of w) { if (!graph.has(c)) { graph.set(c, []); indeg.set(c, 0); } }
    for (let i = 0; i < words.length - 1; i++) {
        const [w1, w2] = [words[i], words[i+1]];
        if (w1.length > w2.length && w1.startsWith(w2)) return '';
        for (let j = 0; j < Math.min(w1.length, w2.length); j++) {
            if (w1[j] !== w2[j]) { graph.get(w1[j]).push(w2[j]); indeg.set(w2[j], indeg.get(w2[j]) + 1); break; }
        }
    }
    const queue = [...indeg.entries()].filter(([,d]) => d === 0).map(([c]) => c);
    let order = '';
    while (queue.length) {
        const c = queue.shift(); order += c;
        for (const nb of graph.get(c)) { indeg.set(nb, indeg.get(nb) - 1); if (indeg.get(nb) === 0) queue.push(nb); }
    }
    return order.length === graph.size ? order : '';
}

Time: O(C) | Space: O(1) (≤26 chars)

---

Q19 — Minimum Height Trees

🧠 How to Approach This

Step 1 — Recognize the pattern: Centroid(s) of tree; prune leaves iteratively.

Step 2 — Brute force (what NOT to do): BFS from every node — O(n²).

Step 3 — Optimal insight: Iteratively remove leaf nodes (degree=1); last 1-2 nodes are centroids.

Step 4 — Algorithm:

1. Build adjacency set + degree array; enqueue all leaves

2. Remove leaves; enqueue new leaves; repeat until ≤ 2 nodes

Step 5 — Edge cases: n=1 → [0]; n=2 → [0,1].

function findMinHeightTrees(n, edges) {
    if (n === 1) return [0];
    const graph  = Array.from({ length: n }, () => new Set());
    for (const [u, v] of edges) { graph[u].add(v); graph[v].add(u); }
    let leaves = [];
    for (let i = 0; i < n; i++) if (graph[i].size === 1) leaves.push(i);
    let rem = n;
    while (rem > 2) {
        rem -= leaves.length;
        const next = [];
        for (const l of leaves) {
            const nb = [...graph[l]][0];
            graph[nb].delete(l);
            if (graph[nb].size === 1) next.push(nb);
        }
        leaves = next;
    }
    return leaves;
}

Time: O(n) | Space: O(n)

---

Q20 — Is Graph Bipartite?

🧠 How to Approach This

Step 1 — Recognize the pattern: 2-coloring via BFS; conflict = not bipartite.

Step 2 — Brute force (what NOT to do): Try all 2^n colorings.

Step 3 — Optimal insight: BFS 2-coloring; neighbor with same color → not bipartite.

Step 4 — Algorithm:

1. Color array init -1; BFS: neighbors get 1-current color

2. Conflict → return false; handle disconnected components

Step 5 — Edge cases: Disconnected graph.

function isBipartite(graph) {
    const n = graph.length, color = new Array(n).fill(-1);
    for (let i = 0; i < n; i++) {
        if (color[i] !== -1) continue;
        const queue = [i]; color[i] = 0;
        while (queue.length) {
            const u = queue.shift();
            for (const v of graph[u]) {
                if (color[v] === -1) { color[v] = 1 - color[u]; queue.push(v); }
                else if (color[v] === color[u]) return false;
            }
        }
    }
    return true;
}

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

---

Q21 — Find Eventual Safe States

🧠 How to Approach This

Step 1 — Recognize the pattern: Safe node = does NOT lead to cycle; reverse graph + topological sort.

Step 2 — Brute force (what NOT to do): DFS cycle check from every node — O(V²).

Step 3 — Optimal insight: Reverse graph + Kahn's from terminal nodes.

Step 4 — Algorithm:

1. Build reverse graph; track outdegree of original

2. Kahn's from terminal nodes (outdegree=0); collected = safe

Step 5 — Edge cases: No cycles → all safe.

function eventualSafeNodes(graph) {
    const n = graph.length;
    const rev = Array.from({ length: n }, () => []);
    const outdeg = new Array(n).fill(0);
    for (let u = 0; u < n; u++) for (const v of graph[u]) { rev[v].push(u); outdeg[u]++; }
    const queue = [], safe = [];
    for (let i = 0; i < n; i++) if (outdeg[i] === 0) queue.push(i);
    while (queue.length) {
        const u = queue.shift(); safe.push(u);
        for (const v of rev[u]) if (--outdeg[v] === 0) queue.push(v);
    }
    return safe.sort((a, b) => a - b);
}

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

---

Q22 — Jump Game III

🧠 How to Approach This

Step 1 — Recognize the pattern: BFS reachability; can we reach any index with value 0?

Step 2 — Brute force (what NOT to do): Recursion without memoization — exponential.

Step 3 — Optimal insight: BFS from start; at index i jump to i±arr[i]; track visited.

Step 4 — Algorithm:

1. BFS queue starting at start

2. From index i: check i+arr[i] and i-arr[i]

3. If arr[index] === 0 → return true

Step 5 — Edge cases: arr[start] === 0 immediately true.

function canReach(arr, start) {
    const n = arr.length, visited = new Set(), queue = [start];
    while (queue.length) {
        const i = queue.shift();
        if (arr[i] === 0) return true;
        if (visited.has(i)) continue;
        visited.add(i);
        for (const next of [i + arr[i], i - arr[i]])
            if (next >= 0 && next < n && !visited.has(next)) queue.push(next);
    }
    return false;
}

Time: O(n) | Space: O(n)

---

Q23 — Evaluate Division

🧠 How to Approach This

Step 1 — Recognize the pattern: Weighted directed graph; BFS multiplying edge weights.

Step 2 — Brute force (what NOT to do): Precompute all pairs with Floyd-Warshall — O(V³).

Step 3 — Optimal insight: Build graph with a/b = value and b/a = 1/value; BFS for each query.

Step 4 — Algorithm:

1. Build weighted adjacency map

2. For each query: BFS from numerator to denominator multiplying edge weights

Step 5 — Edge cases: Unknown variables → -1; a/a → 1.

function calcEquation(equations, values, queries) {
    const graph = new Map();
    for (let i = 0; i < equations.length; i++) {
        const [a, b] = equations[i], v = values[i];
        if (!graph.has(a)) graph.set(a, new Map());
        if (!graph.has(b)) graph.set(b, new Map());
        graph.get(a).set(b, v);
        graph.get(b).set(a, 1 / v);
    }
    function bfs(src, dst) {
        if (!graph.has(src) || !graph.has(dst)) return -1;
        if (src === dst) return 1;
        const visited = new Set([src]), queue = [[src, 1]];
        while (queue.length) {
            const [node, prod] = queue.shift();
            for (const [nb, w] of graph.get(node)) {
                if (nb === dst) return prod * w;
                if (!visited.has(nb)) { visited.add(nb); queue.push([nb, prod * w]); }
            }
        }
        return -1;
    }
    return queries.map(([a, b]) => bfs(a, b));
}

Time: O(Q · (V + E)) | Space: O(V + E)

---

Q24 — Sequence Reconstruction

🧠 How to Approach This

Step 1 — Recognize the pattern: Topological sort; queue must always have exactly 1 node for unique ordering.

Step 2 — Brute force (what NOT to do): Generate all topological orderings — exponential.

Step 3 — Optimal insight: Kahn's; if queue size > 1 at any point → not unique.

Step 4 — Algorithm:

1. Build graph from sequences; track indegree

2. Kahn's: if queue size > 1 → return false

3. If order matches org → true

Step 5 — Edge cases: org has elements not in seqs → false.

function sequenceReconstruction(org, seqs) {
    const graph = new Map(), indeg = new Map();
    for (const seq of seqs) for (const v of seq) { if (!graph.has(v)) { graph.set(v, []); indeg.set(v, 0); } }
    for (const seq of seqs) for (let i = 0; i < seq.length - 1; i++) {
        const [u, v] = [seq[i], seq[i+1]];
        if (!graph.get(u).includes(v)) { graph.get(u).push(v); indeg.set(v, indeg.get(v) + 1); }
    }
    const queue = [...indeg.entries()].filter(([,d]) => d === 0).map(([v]) => v);
    let idx = 0;
    while (queue.length === 1) {
        const u = queue.shift();
        if (org[idx++] !== u) return false;
        for (const v of graph.get(u)) { indeg.set(v, indeg.get(v) - 1); if (indeg.get(v) === 0) queue.push(v); }
    }
    return idx === org.length && queue.length === 0;
}

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

---

Q25 — Minimum Cost to Connect All Points

🧠 How to Approach This

Step 1 — Recognize the pattern: Minimum Spanning Tree (MST) on complete graph with Manhattan distance.

Step 2 — Brute force (what NOT to do): Try all spanning trees — exponential.

Step 3 — Optimal insight: Prim's MST: greedily add nearest unvisited point.

Step 4 — Algorithm:

1. Init dist[] = Infinity; dist[0] = 0

2. Greedily pick min-dist unvisited node; add to MST

3. Update distances of remaining nodes

Step 5 — Edge cases: Single point → 0.

function minCostConnectPoints(points) {
    const n = points.length;
    const dist = new Array(n).fill(Infinity);
    const visited = new Array(n).fill(false);
    dist[0] = 0; let total = 0;
    for (let i = 0; i < n; i++) {
        let u = -1;
        for (let j = 0; j < n; j++) if (!visited[j] && (u === -1 || dist[j] < dist[u])) u = j;
        visited[u] = true; total += dist[u];
        for (let v = 0; v < n; v++) {
            if (!visited[v]) {
                const d = Math.abs(points[u][0]-points[v][0]) + Math.abs(points[u][1]-points[v][1]);
                if (d < dist[v]) dist[v] = d;
            }
        }
    }
    return total;
}

Time: O(n²) | Space: O(n)