# Shortest Paths — Part 2: Interview Problems

Six problems, each needing a different shortest-path tool: Dijkstra, minimax Dijkstra, Bellman-Ford with a stop limit, grid BFS, and Floyd–Warshall.

## 1. Network Delay Time (LeetCode 743)

**🟠 Medium.** `times[i] = (u, v, w)`: a signal takes w time from node u to v (nodes 1..n). Send a signal from k; return the time for all nodes to receive it, or −1.

```text
times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2 → 2
```

**Approach.** Single-source shortest paths with non-negative weights: Dijkstra from k. The answer is the maximum finite distance (−1 if any node is unreachable).

**Complexity.** O((V + E) log V).

```typescript
class MinHeap<T> {
  private a: T[] = [];
  private less: (x: T, y: T) => boolean;
  constructor(less: (x: T, y: T) => boolean = (x: any, y: any) => x < y) { this.less = less; }
  get size(): number { return this.a.length; }
  peek(): T | undefined { return this.a[0]; }
  push(x: T): void {
    const a = this.a; a.push(x);
    let i = a.length - 1;
    while (i > 0) {                                   // sift up
      const p = (i - 1) >> 1;
      if (!this.less(a[i], a[p])) break;
      [a[i], a[p]] = [a[p], a[i]]; i = p;
    }
  }
  pop(): T | undefined {
    const a = this.a; if (!a.length) return undefined;
    const top = a[0], last = a.pop()!;
    if (a.length) {
      a[0] = last; let i = 0;
      while (true) {                                  // sift down
        const l = 2 * i + 1, r = l + 1; let m = i;
        if (l < a.length && this.less(a[l], a[m])) m = l;
        if (r < a.length && this.less(a[r], a[m])) m = r;
        if (m === i) break;
        [a[i], a[m]] = [a[m], a[i]]; i = m;
      }
    }
    return top;
  }
}

function networkDelayTime(times: number[][], n: number, k: number): number {
  const adj: [number, number][][] = Array.from({ length: n + 1 }, () => []);
  for (const [u, v, w] of times) adj[u].push([v, w]);
  const dist = new Array(n + 1).fill(Infinity);
  dist[k] = 0;
  const heap = new MinHeap<[number, number]>((a, b) => a[0] < b[0]);
  heap.push([0, k]);
  while (heap.size) {
    const [d, u] = heap.pop()!;
    if (d > dist[u]) continue;
    for (const [v, w] of adj[u]) if (d + w < dist[v]) { dist[v] = d + w; heap.push([dist[v], v]); }
  }
  const best = Math.max(...dist.slice(1));
  return best === Infinity ? -1 : best;
}
```

```python
import heapq

def network_delay_time(times, n, k):
    adj = [[] for _ in range(n + 1)]
    for u, v, w in times:
        adj[u].append((v, w))
    dist = {k: 0}
    heap = [(0, k)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue
        for v, w in adj[u]:
            if d + w < dist.get(v, float("inf")):
                dist[v] = d + w
                heapq.heappush(heap, (d + w, v))
    return max(dist.values()) if len(dist) == n else -1
```

## 2. Path With Minimum Effort (LeetCode 1631)

**🟠 Medium.** Move through a height grid from top-left to bottom-right. A route's effort is its **maximum** absolute height difference between consecutive cells. Return the minimum effort.

```text
[[1,2,2],[3,8,2],[5,3,5]] → 2
```

**Approach.** Dijkstra where the path cost is the max edge so far instead of a sum: `cost(v) = max(cost(u), |h[u] − h[v]|)`. The heap still pops cells in non-decreasing cost order, so the first time the target is popped, its cost is optimal.

**Complexity.** O(R · C · log(R · C)).

```typescript
class MinHeap<T> {
  private a: T[] = [];
  private less: (x: T, y: T) => boolean;
  constructor(less: (x: T, y: T) => boolean = (x: any, y: any) => x < y) { this.less = less; }
  get size(): number { return this.a.length; }
  peek(): T | undefined { return this.a[0]; }
  push(x: T): void {
    const a = this.a; a.push(x);
    let i = a.length - 1;
    while (i > 0) {                                   // sift up
      const p = (i - 1) >> 1;
      if (!this.less(a[i], a[p])) break;
      [a[i], a[p]] = [a[p], a[i]]; i = p;
    }
  }
  pop(): T | undefined {
    const a = this.a; if (!a.length) return undefined;
    const top = a[0], last = a.pop()!;
    if (a.length) {
      a[0] = last; let i = 0;
      while (true) {                                  // sift down
        const l = 2 * i + 1, r = l + 1; let m = i;
        if (l < a.length && this.less(a[l], a[m])) m = l;
        if (r < a.length && this.less(a[r], a[m])) m = r;
        if (m === i) break;
        [a[i], a[m]] = [a[m], a[i]]; i = m;
      }
    }
    return top;
  }
}

function minimumEffortPath(heights: number[][]): number {
  const R = heights.length, C = heights[0].length;
  const best = Array.from({ length: R }, () => new Array(C).fill(Infinity));
  best[0][0] = 0;
  const heap = new MinHeap<[number, number, number]>((a, b) => a[0] < b[0]);
  heap.push([0, 0, 0]);
  while (heap.size) {
    const [e, r, c] = heap.pop()!;
    if (r === R - 1 && c === C - 1) return e;
    if (e > best[r][c]) continue;
    for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
      const nr = r + dr, nc = c + dc;
      if (nr < 0 || nc < 0 || nr >= R || nc >= C) continue;
      const ne = Math.max(e, Math.abs(heights[nr][nc] - heights[r][c]));
      if (ne < best[nr][nc]) { best[nr][nc] = ne; heap.push([ne, nr, nc]); }
    }
  }
  return 0;
}
```

```python
import heapq

def minimum_effort_path(heights):
    R, C = len(heights), len(heights[0])
    best = [[float("inf")] * C for _ in range(R)]
    best[0][0] = 0
    heap = [(0, 0, 0)]
    while heap:
        e, r, c = heapq.heappop(heap)
        if (r, c) == (R - 1, C - 1):
            return e
        if e > best[r][c]:
            continue
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < R and 0 <= nc < C:
                ne = max(e, abs(heights[nr][nc] - heights[r][c]))
                if ne < best[nr][nc]:
                    best[nr][nc] = ne
                    heapq.heappush(heap, (ne, nr, nc))
    return 0
```

## 3. Cheapest Flights Within K Stops (LeetCode 787)

**🟠 Medium.** `flights[i] = (from, to, price)`. Return the cheapest price from `src` to `dst` with at most `k` stops (k + 1 flights), or −1.

```text
0→1→3 costs 700 with k = 1 (0→1→2→3 = 400 needs 2 stops)
```

**Approach.** Bellman-Ford limited to k + 1 rounds. Each round relaxes every flight using a **copy** of the previous round's prices, so a round extends routes by exactly one flight.

**Complexity.** O(k · E) time, O(V) space.

```typescript
function findCheapestPrice(n: number, flights: number[][], src: number, dst: number, k: number): number {
  let price = new Array(n).fill(Infinity);
  price[src] = 0;
  for (let round = 0; round <= k; round++) {
    const next = [...price];
    for (const [u, v, w] of flights) if (price[u] + w < next[v]) next[v] = price[u] + w;
    price = next;
  }
  return price[dst] === Infinity ? -1 : price[dst];
}
```

```python
def find_cheapest_price(n, flights, src, dst, k):
    INF = float("inf")
    price = [INF] * n
    price[src] = 0
    for _ in range(k + 1):
        nxt = price[:]                         # read from the previous round only
        for u, v, w in flights:
            if price[u] + w < nxt[v]:
                nxt[v] = price[u] + w
        price = nxt
    return price[dst] if price[dst] != INF else -1
```

## 4. Shortest Path in Binary Matrix (LeetCode 1091)

**🟠 Medium.** Return the length (in cells) of the shortest clear path (0s) from top-left to bottom-right moving in 8 directions, or −1.

```text
[[0,0,0],[1,1,0],[1,1,0]] → 4
```

**Approach.** Unweighted grid → BFS. Start at (0,0) if it's clear; each BFS level adds one cell to the path length.

**Complexity.** O(n²) time and space.

```typescript
function shortestPathBinaryMatrix(grid: number[][]): number {
  const n = grid.length;
  if (grid[0][0] || grid[n - 1][n - 1]) return -1;
  const q: [number, number, number][] = [[0, 0, 1]];
  grid[0][0] = 1;
  for (let head = 0; head < q.length; head++) {
    const [r, c, d] = q[head];
    if (r === n - 1 && c === n - 1) return d;
    for (let dr = -1; dr <= 1; dr++) for (let dc = -1; dc <= 1; dc++) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nc >= 0 && nr < n && nc < n && grid[nr][nc] === 0) { grid[nr][nc] = 1; q.push([nr, nc, d + 1]); }
    }
  }
  return -1;
}
```

```python
from collections import deque

def shortest_path_binary_matrix(grid):
    n = len(grid)
    if grid[0][0] or grid[n - 1][n - 1]:
        return -1
    q = deque([(0, 0, 1)])
    grid[0][0] = 1                                  # visited
    while q:
        r, c, d = q.popleft()
        if (r, c) == (n - 1, n - 1):
            return d
        for dr in (-1, 0, 1):
            for dc in (-1, 0, 1):
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:
                    grid[nr][nc] = 1
                    q.append((nr, nc, d + 1))
    return -1
```

## 5. Swim in Rising Water (LeetCode 778)

**🔴 Hard.** At time t you can swim through cells with elevation ≤ t. Return the least time to go from top-left to bottom-right.

```text
[[0,2],[1,3]] → 3
```

**Approach.** Minimax path: the cost of a path is its maximum elevation. Dijkstra with `max` (like Path With Minimum Effort), popping the lowest reachable elevation first; the max seen when reaching the target is the answer.

**Complexity.** O(n² log n).

```typescript
class MinHeap<T> {
  private a: T[] = [];
  private less: (x: T, y: T) => boolean;
  constructor(less: (x: T, y: T) => boolean = (x: any, y: any) => x < y) { this.less = less; }
  get size(): number { return this.a.length; }
  peek(): T | undefined { return this.a[0]; }
  push(x: T): void {
    const a = this.a; a.push(x);
    let i = a.length - 1;
    while (i > 0) {                                   // sift up
      const p = (i - 1) >> 1;
      if (!this.less(a[i], a[p])) break;
      [a[i], a[p]] = [a[p], a[i]]; i = p;
    }
  }
  pop(): T | undefined {
    const a = this.a; if (!a.length) return undefined;
    const top = a[0], last = a.pop()!;
    if (a.length) {
      a[0] = last; let i = 0;
      while (true) {                                  // sift down
        const l = 2 * i + 1, r = l + 1; let m = i;
        if (l < a.length && this.less(a[l], a[m])) m = l;
        if (r < a.length && this.less(a[r], a[m])) m = r;
        if (m === i) break;
        [a[i], a[m]] = [a[m], a[i]]; i = m;
      }
    }
    return top;
  }
}

function swimInWater(grid: number[][]): number {
  const n = grid.length;
  const seen = Array.from({ length: n }, () => new Array(n).fill(false));
  seen[0][0] = true;
  const heap = new MinHeap<[number, number, number]>((a, b) => a[0] < b[0]);
  heap.push([grid[0][0], 0, 0]);
  while (heap.size) {
    const [t, r, c] = heap.pop()!;
    if (r === n - 1 && c === n - 1) return t;
    for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nc >= 0 && nr < n && nc < n && !seen[nr][nc]) {
        seen[nr][nc] = true;
        heap.push([Math.max(t, grid[nr][nc]), nr, nc]);
      }
    }
  }
  return -1;
}
```

```python
import heapq

def swim_in_water(grid):
    n = len(grid)
    seen = {(0, 0)}
    heap = [(grid[0][0], 0, 0)]
    while heap:
        t, r, c = heapq.heappop(heap)
        if (r, c) == (n - 1, n - 1):
            return t
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < n and (nr, nc) not in seen:
                seen.add((nr, nc))
                heapq.heappush(heap, (max(t, grid[nr][nc]), nr, nc))
    return -1
```

## 6. Find the City With the Smallest Number of Neighbors at a Threshold Distance (LeetCode 1334)

**🟠 Medium.** Return the city with the fewest other cities reachable within `distanceThreshold` (ties: the largest index).

```text
n = 4, threshold 4 → city 3
```

**Approach.** All-pairs shortest paths with Floyd–Warshall (n ≤ 100): `d[i][j] = min(d[i][j], d[i][k] + d[k][j])` for every intermediate k. Then count neighbours within the threshold for each city.

**Complexity.** O(n³) time, O(n²) space.

```typescript
function findTheCity(n: number, edges: number[][], threshold: number): number {
  const d = Array.from({ length: n }, (_, i) => Array.from({ length: n }, (_, j) => (i === j ? 0 : Infinity)));
  for (const [u, v, w] of edges) d[u][v] = d[v][u] = Math.min(d[u][v], w);
  for (let k = 0; k < n; k++)
    for (let i = 0; i < n; i++)
      for (let j = 0; j < n; j++)
        if (d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];
  let bestCity = -1, bestCount = Infinity;
  for (let i = 0; i < n; i++) {
    const cnt = d[i].filter((x, j) => j !== i && x <= threshold).length;
    if (cnt <= bestCount) { bestCity = i; bestCount = cnt; }
  }
  return bestCity;
}
```

```python
def find_the_city(n, edges, threshold):
    INF = float("inf")
    d = [[0 if i == j else INF for j in range(n)] for i in range(n)]
    for u, v, w in edges:
        d[u][v] = d[v][u] = min(d[u][v], w)
    for k in range(n):                        # allow k as an intermediate stop
        for i in range(n):
            for j in range(n):
                if d[i][k] + d[k][j] < d[i][j]:
                    d[i][j] = d[i][k] + d[k][j]
    best_city, best_count = -1, INF
    for i in range(n):
        cnt = sum(1 for j in range(n) if j != i and d[i][j] <= threshold)
        if cnt <= best_count:
            best_city, best_count = i, cnt
    return best_city
```