🎯 PHP 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/BFS 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 visited.

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(array $grid): int {
    $rows = count($grid); $cols = count($grid[0]); $count = 0;
    $dfs = function(int $r, int $c) use (&$dfs, &$grid, $rows, $cols): void {
        if ($r < 0 || $r >= $rows || $c < 0 || $c >= $cols || $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 ($r = 0; $r < $rows; $r++)
        for ($c = 0; $c < $cols; $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/DFS 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: HashMap maps 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.

class Node { public int $val; public array $neighbors; public function __construct(int $v){ $this->val=$v; $this->neighbors=[]; } }

function cloneGraph(?Node $node): ?Node {
    if ($node === null) return null;
    $map   = [];
    $queue = [$node];
    $map[$node->val] = new Node($node->val);
    while (!empty($queue)) {
        $curr = array_shift($queue);
        foreach ($curr->neighbors as $neighbor) {
            if (!isset($map[$neighbor->val])) {
                $map[$neighbor->val] = new Node($neighbor->val);
                $queue[] = $neighbor;
            }
            $map[$curr->val]->neighbors[] = $map[$neighbor->val];
        }
    }
    return $map[$node->val];
}

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 — if cycle exists, 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

3. Process queue: decrement neighbors' indegree; enqueue when 0

4. If processed count === n → true

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

function canFinish(int $n, array $prereqs): bool {
    $graph = array_fill(0, $n, []);
    $indeg = array_fill(0, $n, 0);
    foreach ($prereqs as [$a, $b]) { $graph[$b][] = $a; $indeg[$a]++; }
    $queue = array_keys(array_filter($indeg, fn($d) => $d === 0));
    $count = 0;
    while (!empty($queue)) {
        $node = array_shift($queue); $count++;
        foreach ($graph[$node] as $nb) { if (--$indeg[$nb] === 0) $queue[] = $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 topological 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 I

2. Append each dequeued node to order

3. Return order if complete, else []

Step 5 — Edge cases: Multiple valid orderings exist.

function findOrder(int $n, array $prereqs): array {
    $graph = array_fill(0, $n, []);
    $indeg = array_fill(0, $n, 0);
    foreach ($prereqs as [$a, $b]) { $graph[$b][] = $a; $indeg[$a]++; }
    $queue = array_keys(array_filter($indeg, fn($d) => $d === 0));
    $order = [];
    while (!empty($queue)) {
        $node = array_shift($queue); $order[] = $node;
        foreach ($graph[$node] as $nb) { if (--$indeg[$nb] === 0) $queue[] = $nb; }
    }
    return count($order) === $n ? $order : [];
}

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

---

Q5 — Pacific Atlantic Water Flow

🧠 How to Approach This

Step 1 — Recognize the pattern: Reverse flow — 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: Multi-source BFS from Pacific border cells and Atlantic border cells separately.

Step 4 — Algorithm:

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

2. Return cells in both reachable sets

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

function pacificAtlantic(array $heights): array {
    $R = count($heights); $C = count($heights[0]);
    $bfs = function(array $starts) use ($heights, $R, $C): array {
        $visited = []; $queue = $starts;
        foreach ($starts as [$r,$c]) $visited["$r,$c"] = true;
        $dirs = [[1,0],[-1,0],[0,1],[0,-1]];
        while (!empty($queue)) {
            [$r,$c] = array_shift($queue);
            foreach ($dirs as [$dr,$dc]) {
                $nr=$r+$dr; $nc=$c+$dc;
                if ($nr>=0&&$nr<$R&&$nc>=0&&$nc<$C&&!isset($visited["$nr,$nc"])
                    &&$heights[$nr][$nc]>=$heights[$r][$c]) {
                    $visited["$nr,$nc"]=true; $queue[]=[$nr,$nc];
                }
            }
        }
        return $visited;
    };
    $pac=[]; $atl=[];
    for($r=0;$r<$R;$r++){ $pac[]=[$r,0]; $atl[]=[$r,$C-1]; }
    for($c=0;$c<$C;$c++){ $pac[]=[0,$c]; $atl[]=[$R-1,$c]; }
    $pv=$bfs($pac); $av=$bfs($atl);
    $res=[];
    for($r=0;$r<$R;$r++) for($c=0;$c<$C;$c++)
        if(isset($pv["$r,$c"])&&isset($av["$r,$c"])) $res[]=[$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; 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 all border 'O' → mark as 'S'

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

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

function solve(array &$board): void {
    $R=count($board); $C=count($board[0]);
    $dfs=function(int $r,int $c) use(&$dfs,&$board,$R,$C):void{
        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($r=0;$r<$R;$r++){ $dfs($r,0); $dfs($r,$C-1); }
    for($c=0;$c<$C;$c++){ $dfs(0,$c); $dfs($R-1,$c); }
    for($r=0;$r<$R;$r++) for($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 then take max — O(R²C²).

Step 3 — Optimal insight: Add all rotten oranges to queue 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 oranges → 0; isolated fresh → -1.

function orangesRotting(array $grid): int {
    $R=count($grid); $C=count($grid[0]); $fresh=0; $queue=[];
    for($r=0;$r<$R;$r++) for($c=0;$c<$C;$c++){
        if($grid[$r][$c]===2) $queue[]=[$r,$c,0];
        if($grid[$r][$c]===1) $fresh++;
    }
    $dirs=[[1,0],[-1,0],[0,1],[0,-1]]; $mins=0;
    while(!empty($queue)){
        [$r,$c,$t]=array_shift($queue); $mins=max($mins,$t);
        foreach($dirs as[$dr,$dc]){
            $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[]=[$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 (0); fill rooms with shortest distance.

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

Step 3 — Optimal insight: Multi-source BFS from all gates simultaneously; 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(array &$rooms): void {
    $INF=PHP_INT_MAX; $R=count($rooms); $C=count($rooms[0]); $queue=[];
    for($r=0;$r<$R;$r++) for($c=0;$c<$C;$c++)
        if($rooms[$r][$c]===0) $queue[]=[$r,$c];
    $dirs=[[1,0],[-1,0],[0,1],[0,-1]];
    while(!empty($queue)){
        [$r,$c]=array_shift($queue);
        foreach($dirs as[$dr,$dc]){
            $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[]=[$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 in an undirected graph — 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 redundant edges → return the last one.

function findRedundantConnection(array $edges): array {
    $n  = count($edges);
    $uf = new UnionFind($n + 1);
    foreach ($edges as [$u, $v]) {
        if (!$uf->union($u, $v)) return [$u, $v];
    }
    return [];
}

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

---

Q10 — Number of Connected Components

🧠 How to Approach This

Step 1 — Recognize the pattern: Union-Find or DFS count of components.

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

Step 3 — Optimal insight: Union-Find: 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 components; all connected → 1.

function countComponents(int $n, array $edges): int {
    $uf    = new UnionFind($n);
    $count = $n;
    foreach ($edges as [$u, $v]) {
        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 for connectivity — O(V²).

Step 3 — Optimal insight: Union-Find: n-1 edges exactly + all unions succeed (no cycle).

Step 4 — Algorithm:

1. If edges != n-1 → false

2. Union all edges; if any union returns false → false (cycle)

3. Return true

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

function validTree(int $n, array $edges): bool {
    if (count($edges) !== $n - 1) return false;
    $uf = new UnionFind($n);
    foreach ($edges as [$u, $v]) {
        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 differ by 1 char = edge); find shortest path.

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

Step 3 — Optimal insight: BFS level by level; 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 replacements; if in wordList and unvisited → enqueue

3. Return length when endWord reached

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

function ladderLength(string $begin, string $end, array $wordList): int {
    $set   = array_flip($wordList);
    if (!isset($set[$end])) return 0;
    $queue = [[$begin, 1]];
    while (!empty($queue)) {
        [$word, $len] = array_shift($queue);
        for ($i = 0; $i < strlen($word); $i++) {
            for ($c = ord('a'); $c <= ord('z'); $c++) {
                $next = substr($word, 0, $i) . chr($c) . substr($word, $i+1);
                if ($next === $end) return $len + 1;
                if (isset($set[$next])) {
                    unset($set[$next]);
                    $queue[] = [$next, $len + 1];
                }
            }
        }
    }
    return 0;
}

Time: O(M² × N) where M=word length, N=wordList size | 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 path.

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

Step 4 — Algorithm:

1. If start or end is 1 → return -1

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

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

function shortestPathBinaryMatrix(array $grid): int {
    $n = count($grid);
    if ($grid[0][0] === 1 || $grid[$n-1][$n-1] === 1) return -1;
    $queue = [[0, 0, 1]]; $grid[0][0] = 1;
    $dirs  = [[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]];
    while (!empty($queue)) {
        [$r,$c,$d] = array_shift($queue);
        if ($r===$n-1 && $c===$n-1) return $d;
        foreach ($dirs as [$dr,$dc]) {
            $nr=$r+$dr; $nc=$c+$dc;
            if ($nr>=0&&$nr<$n&&$nc>=0&&$nc<$n&&$grid[$nr][$nc]===0) {
                $grid[$nr][$nc]=1; $queue[]=[$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/BFS from source pixel; change all connected same-colored pixels.

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

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

Step 4 — Algorithm:

1. If color already equals new color → return image unchanged

2. DFS from (sr, sc): change color; recurse 4 directions for same old color

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

function floodFill(array $image, int $sr, int $sc, int $color): array {
    $old = $image[$sr][$sc];
    if ($old === $color) return $image;
    $dfs = function(int $r, int $c) use (&$dfs, &$image, $old, $color): void {
        if ($r<0||$r>=count($image)||$c<0||$c>=count($image[0])||$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 separately — O(R²C²).

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

Step 4 — Algorithm:

1. Init dist matrix: 0 for zeros, INF for ones

2. Enqueue all 0s; BFS — dist[nr][nc] = dist[r][c] + 1 if smaller

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

function updateMatrix(array $mat): array {
    $R=count($mat);$C=count($mat[0]);$INF=PHP_INT_MAX;
    $dist=array_fill(0,$R,array_fill(0,$C,$INF)); $queue=[];
    for($r=0;$r<$R;$r++) for($c=0;$c<$C;$c++)
        if($mat[$r][$c]===0){ $dist[$r][$c]=0; $queue[]=[$r,$c]; }
    $dirs=[[1,0],[-1,0],[0,1],[0,-1]];
    while(!empty($queue)){
        [$r,$c]=array_shift($queue);
        foreach($dirs as[$dr,$dc]){
            $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[]=[$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 algorithm.

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

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

Step 4 — Algorithm:

1. Build adjacency list with weights

2. Dijkstra from k; track dist[] array

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

Step 5 — Edge cases: Single node; disconnected graph.

function networkDelayTime(array $times, int $n, int $k): int {
    $graph = array_fill(1, $n, []);
    foreach ($times as [$u,$v,$w]) $graph[$u][] = [$v,$w];
    $dist = array_fill(1, $n, PHP_INT_MAX); $dist[$k]=0;
    $pq   = [[0,$k]]; // [dist, node]
    while (!empty($pq)) {
        usort($pq, fn($a,$b)=>$a[0]-$b[0]);
        [$d,$u] = array_shift($pq);
        if ($d > $dist[$u]) continue;
        foreach ($graph[$u] as [$v,$w]) {
            if ($dist[$u]+$w < $dist[$v]) { $dist[$v]=$dist[$u]+$w; $pq[]=[$dist[$v],$v]; }
        }
    }
    $max = max($dist);
    return $max === PHP_INT_MAX ? -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 from (0,0) to (n-1,n-1) minimizing the maximum elevation — Dijkstra/binary search.

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 of [max_so_far, r, c]

2. Pop min; if destination → return max_so_far

3. Push neighbors with max(current_max, neighbor_val)

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

function swimInWater(array $grid): int {
    $n=count($grid); $visited=[];
    $pq=[[($grid[0][0]),0,0]]; $dirs=[[1,0],[-1,0],[0,1],[0,-1]];
    while(!empty($pq)){
        usort($pq,fn($a,$b)=>$a[0]-$b[0]);
        [$t,$r,$c]=array_shift($pq);
        if($r===$n-1&&$c===$n-1) return $t;
        if(isset($visited["$r,$c"])) continue;
        $visited["$r,$c"]=true;
        foreach($dirs as[$dr,$dc]){
            $nr=$r+$dr;$nc=$c+$dc;
            if($nr>=0&&$nr<$n&&$nc>=0&&$nc<$n&&!isset($visited["$nr,$nc"]))
                $pq[]=[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 of words — O(N²L).

Step 3 — Optimal insight: Adjacent words differ at first mismatch → that gives a directed edge; topological sort.

Step 4 — Algorithm:

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

2. Topological sort on character graph

3. Invalid if prefix word comes after longer word

Step 5 — Edge cases: Single character; cycle in constraints.

function alienOrder(array $words): string {
    $graph=[]; $indeg=[];
    foreach($words as $w) foreach(str_split($w) as $c){ if(!isset($graph[$c])){ $graph[$c]=[]; $indeg[$c]=0; } }
    for($i=0;$i<count($words)-1;$i++){
        $w1=$words[$i]; $w2=$words[$i+1]; $len=min(strlen($w1),strlen($w2));
        if(strlen($w1)>strlen($w2)&&str_starts_with($w1,$w2)) return '';
        for($j=0;$j<$len;$j++){
            if($w1[$j]!==$w2[$j]){ $graph[$w1[$j]][]=$w2[$j]; $indeg[$w2[$j]]++; break; }
        }
    }
    $queue=array_keys(array_filter($indeg,fn($d)=>$d===0)); $order='';
    while(!empty($queue)){
        $c=array_shift($queue); $order.=$c;
        foreach($graph[$c] as $nb){ if(--$indeg[$nb]===0) $queue[]=$nb; }
    }
    return strlen($order)===count($graph) ? $order : '';
}

Time: O(C) where C = total characters | Space: O(1) since ≤26 chars

---

Q19 — Minimum Height Trees

🧠 How to Approach This

Step 1 — Recognize the pattern: Root that minimizes height = centroid(s) of tree; prune leaves iteratively.

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

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

Step 4 — Algorithm:

1. Build adjacency list + degree array

2. Enqueue all leaves (degree=1)

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

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

function findMinHeightTrees(int $n, array $edges): array {
    if($n===1) return [0];
    $graph=array_fill(0,$n,[]); $degree=array_fill(0,$n,0);
    foreach($edges as[$u,$v]){ $graph[$u][]=$v; $graph[$v][]=$u; $degree[$u]++; $degree[$v]++; }
    $leaves=array_keys(array_filter($degree,fn($d)=>$d===1));
    $rem=$n;
    while($rem>2){
        $rem-=count($leaves); $next=[];
        foreach($leaves as $l) foreach($graph[$l] as $nb){ if(--$degree[$nb]===1) $next[]=$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 — alternate colors on BFS/DFS; conflict = not bipartite.

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

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

Step 4 — Algorithm:

1. Color array init -1

2. BFS: color node 0; neighbors get color 1-current

3. Conflict → return false

Step 5 — Edge cases: Disconnected graph — must check all components.

function isBipartite(array $graph): bool {
    $n=count($graph); $color=array_fill(0,$n,-1);
    for($i=0;$i<$n;$i++){
        if($color[$i]!==-1) continue;
        $queue=[$i]; $color[$i]=0;
        while(!empty($queue)){
            $u=array_shift($queue);
            foreach($graph[$u] as $v){
                if($color[$v]===-1){ $color[$v]=1-$color[$u]; $queue[]=$v; }
                elseif($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 = node that does NOT lead to a cycle; reverse graph topological sort.

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

Step 3 — Optimal insight: Reverse graph + Kahn's; nodes with 0 outdegree in reverse = safe.

Step 4 — Algorithm:

1. Build reverse graph; compute outdegree of original

2. Kahn's on reverse graph starting from terminal nodes (outdegree=0 in original)

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

function eventualSafeNodes(array $graph): array {
    $n=count($graph); $rev=array_fill(0,$n,[]); $outdeg=array_fill(0,$n,0);
    foreach($graph as $u=>$neighbors) foreach($neighbors as $v){ $rev[$v][]=$u; $outdeg[$u]++; }
    $queue=array_keys(array_filter($outdeg,fn($d)=>$d===0)); $safe=[];
    while(!empty($queue)){
        $u=array_shift($queue); $safe[]=$u;
        foreach($rev[$u] as $v){ if(--$outdeg[$v]===0) $queue[]=$v; }
    }
    sort($safe);
    return $safe;
}

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

---

Q22 — Jump Game III

🧠 How to Approach This

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

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

Step 3 — Optimal insight: BFS from start index; at each index jump ±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(array $arr, int $start): bool {
    $n=count($arr); $visited=[]; $queue=[$start];
    while(!empty($queue)){
        $i=array_shift($queue);
        if($arr[$i]===0) return true;
        if(isset($visited[$i])) continue;
        $visited[$i]=true;
        foreach([$i+$arr[$i], $i-$arr[$i]] as $next)
            if($next>=0&&$next<$n&&!isset($visited[$next])) $queue[]=$next;
    }
    return false;
}

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

---

Q23 — Evaluate Division

🧠 How to Approach This

Step 1 — Recognize the pattern: Build weighted directed graph; BFS to find path product between nodes.

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

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

Step 4 — Algorithm:

1. Build weighted adjacency list from equations

2. For each query: BFS from numerator to denominator; multiply weights along path

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

function calcEquation(array $equations, array $values, array $queries): array {
    $graph=[];
    foreach($equations as $i=>[$a,$b]){ $graph[$a][$b]=$values[$i]; $graph[$b][$a]=1/$values[$i]; }
    $bfs=function(string $src, string $dst) use(&$graph): float {
        if(!isset($graph[$src])||!isset($graph[$dst])) return -1.0;
        if($src===$dst) return 1.0;
        $visited=[$src=>true]; $queue=[[$src,1.0]];
        while(!empty($queue)){
            [$node,$prod]=array_shift($queue);
            foreach(($graph[$node]??[]) as $nb=>$w){
                if($nb===$dst) return $prod*$w;
                if(!isset($visited[$nb])){ $visited[$nb]=true; $queue[]=[$nb,$prod*$w]; }
            }
        }
        return -1.0;
    };
    return array_map(fn($q)=>$bfs($q[0],$q[1]), $queries);
}

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

---

Q24 — Sequence Reconstruction

🧠 How to Approach This

Step 1 — Recognize the pattern: Topological sort; check if only ONE unique ordering exists.

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

Step 3 — Optimal insight: Kahn's; at each step the queue must have exactly 1 node (unique ordering).

Step 4 — Algorithm:

1. Build graph from sequences; track indegree

2. Kahn's: if queue size > 1 at any point → false

3. If resulting order matches org → true

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

function sequenceReconstruction(array $org, array $seqs): bool {
    $graph=[]; $indeg=[];
    foreach($seqs as $seq) foreach($seq as $v){ if(!isset($graph[$v])){ $graph[$v]=[]; $indeg[$v]=0; } }
    foreach($seqs as $seq) for($i=0;$i<count($seq)-1;$i++){
        [$u,$v]=[$seq[$i],$seq[$i+1]];
        if(!in_array($v,$graph[$u])){ $graph[$u][]=$v; $indeg[$v]++; }
    }
    $queue=array_keys(array_filter($indeg,fn($d)=>$d===0)); $idx=0;
    while(count($queue)===1){
        $u=array_shift($queue);
        if($org[$idx++]!==$u) return false;
        foreach($graph[$u] as $v){ if(--$indeg[$v]===0) $queue[]=$v; }
    }
    return $idx===count($org)&&empty($queue);
}

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 edges.

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[] = INF; dist[0] = 0

2. Greedily pick min-dist unvisited node; mark visited

3. Update dist[] of neighbors with manhattan distance

Step 5 — Edge cases: Single point → 0.

function minCostConnectPoints(array $points): int {
    $n=count($points); $dist=array_fill(0,$n,PHP_INT_MAX); $dist[0]=0;
    $visited=array_fill(0,$n,false); $total=0;
    for($i=0;$i<$n;$i++){
        $u=-1;
        for($j=0;$j<$n;$j++) if(!$visited[$j]&&($u===-1||$dist[$j]<$dist[$u])) $u=$j;
        $visited[$u]=true; $total+=$dist[$u];
        for($v=0;$v<$n;$v++){
            if(!$visited[$v]){
                $d=abs($points[$u][0]-$points[$v][0])+abs($points[$u][1]-$points[$v][1]);
                if($d<$dist[$v]) $dist[$v]=$d;
            }
        }
    }
    return $total;
}

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