778. Swim in Rising Water (Hard)

Problem

On an n × n grid, grid[r][c] is the elevation at (r, c). At time t, any cell with elevation ≤ t is swimmable; you can move to adjacent cells if both current and next have elevation ≤ t. Return the minimum t at which you can travel from (0, 0) to (n - 1, n - 1).

Equivalently: find the path from top-left to bottom-right that minimizes the maximum cell value along it.

Example

grid = [[0,2],[1,3]] → 3
grid = [[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]] → 16

LeetCode 778 · Link · Hard

Try it yourself

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, binary search on `t` + BFS

Binary-search the answer. For each candidate t, BFS through cells with value ≤ t and check reachability.

from collections import deque

def swim_in_water(grid):
    n = len(grid)                           # L1: O(1)

    def reachable(t):                       # L2: BFS for a fixed threshold t
        if grid[0][0] > t:                  # L3: O(1) early exit
            return False
        visited = {(0, 0)}                  # L4: O(1) init visited set
        q = deque([(0, 0)])                 # L5: O(1) init queue
        while q:                            # L6: BFS loop, up to n² cells
            r, c = q.popleft()              # L7: O(1) dequeue
            if (r, c) == (n - 1, n - 1):   # L8: O(1) goal check
                return True
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nr, nc = r + dr, c + dc     # L9: O(1) per neighbor
                if 0 <= nr < n and 0 <= nc < n and (nr, nc) not in visited and grid[nr][nc] <= t:
                    visited.add((nr, nc))   # L10: O(1) amortized
                    q.append((nr, nc))      # L11: O(1) amortized
        return False

    lo, hi = grid[0][0], n * n - 1         # L12: O(1) search bounds
    while lo < hi:                          # L13: binary search, log(n²) = 2 log n iters
        mid = (lo + hi) // 2               # L14: O(1)
        if reachable(mid):                  # L15: O(n²) BFS call
            hi = mid                        # L16: O(1)
        else:
            lo = mid + 1                    # L17: O(1)
    return lo                              # L18: O(1)

function swimInWater(grid: number[][]): number {
    const n = grid.length;                            // L1: O(1)

    function reachable(t: number): boolean {          // L2: BFS for a fixed threshold t
        if (grid[0][0] > t) return false;             // L3: O(1) early exit
        const visited = new Set<number>();
        visited.add(0);                               // L4: O(1) init visited set
        const q: number[] = [0];                      // L5: O(1) init queue (encode as r*n+c)
        let head = 0;
        while (head < q.length) {                     // L6: BFS loop, up to n² cells
            const key = q[head++];
            const r = Math.floor(key / n), c = key % n;
            if (r === n - 1 && c === n - 1) return true; // L8: O(1) goal check
            for (const [dr, dc] of [[1,0],[-1,0],[0,1],[0,-1]]) {
                const nr = r + dr, nc = c + dc;       // L9: O(1) per neighbor
                const nk = nr * n + nc;
                if (nr >= 0 && nr < n && nc >= 0 && nc < n && !visited.has(nk) && grid[nr][nc] <= t) {
                    visited.add(nk);                  // L10: O(1) amortized
                    q.push(nk);                       // L11: O(1) amortized
                }
            }
        }
        return false;
    }

    let lo = grid[0][0], hi = n * n - 1;             // L12: O(1) search bounds
    while (lo < hi) {                                 // L13: binary search, 2 log n iters
        const mid = (lo + hi) >> 1;                   // L14: O(1)
        if (reachable(mid)) hi = mid;                 // L15: O(n²) BFS call
        else lo = mid + 1;                            // L17: O(1)
    }
    return lo;                                        // L18: O(1)
}

func swimInWater(grid [][]int) int {
    n := len(grid)                                    // L1: O(1)
    reachable := func(t int) bool {                   // L2: BFS for a fixed threshold t
        if grid[0][0] > t { return false }            // L3: O(1) early exit
        visited := make([][]bool, n)
        for i := range visited { visited[i] = make([]bool, n) }
        visited[0][0] = true                          // L4: O(1) init visited
        q := [][2]int{{0, 0}}                         // L5: O(1) init queue
        dirs := [][2]int{{1,0},{-1,0},{0,1},{0,-1}}
        for len(q) > 0 {                              // L6: BFS loop, up to n² cells
            rc := q[0]; q = q[1:]                     // L7: O(1) dequeue
            r, c := rc[0], rc[1]
            if r == n-1 && c == n-1 { return true }  // L8: O(1) goal check
            for _, d := range dirs {
                nr, nc := r+d[0], c+d[1]             // L9: O(1) per neighbor
                if nr >= 0 && nr < n && nc >= 0 && nc < n && !visited[nr][nc] && grid[nr][nc] <= t {
                    visited[nr][nc] = true            // L10: O(1)
                    q = append(q, [2]int{nr, nc})     // L11: O(1) amortized
                }
            }
        }
        return false
    }
    lo, hi := grid[0][0], n*n-1                      // L12: O(1) search bounds
    for lo < hi {                                     // L13: binary search, 2 log n iters
        mid := (lo + hi) / 2                          // L14: O(1)
        if reachable(mid) { hi = mid } else { lo = mid + 1 }  // L15-L17
    }
    return lo                                         // L18: O(1)
}

final class Solution {
    func swimInWater(_ grid: [[Int]]) -> Int {
        let n = grid.count, directions = [(1,0),(-1,0),(0,1),(0,-1)]
        func canReach(_ time: Int) -> Bool { if grid[0][0] > time { return false }; var seen = Array(repeating: Array(repeating: false, count: n), count: n), queue = [(0,0)], index = 0; seen[0][0] = true; while index < queue.count { let (row,col) = queue[index]; index += 1; if row == n - 1 && col == n - 1 { return true }; for (dr,dc) in directions { let r=row+dr,c=col+dc; if r>=0 && r<n && c>=0 && c<n && !seen[r][c] && grid[r][c] <= time { seen[r][c] = true; queue.append((r,c)) } } }; return false }
        var low = max(grid[0][0], grid[n - 1][n - 1]), high = grid.flatMap { $0 }.max()!; while low < high { let middle = low + (high - low) / 2; if canReach(middle) { high = middle } else { low = middle + 1 } }; return low
    }
}

Where the time goes, line by line

Variables: n = grid side length (n×n grid).

Line	Per-call cost	Times executed	Contribution
L1 (init)	$O(1)$	1	$O(1)$
L13 (binary search)	$O(1)$	2 log n iters	$O(log n)$
L15 (BFS call)	$O(n²)$	2 log n	$O(n² log n)$ ← dominates
L6-L11 (BFS body)	$O(1)$ per cell	n² per BFS	$O(n²)$ per call

Each BFS traverses at most n² cells. The binary search calls BFS $O(log(n²)$ ) = $O(log n)$ times. The product gives $O(n² log n)$ . The set membership check inside L9 is $O(1)$ amortized for a hash set.

Complexity

Time: $O(n² log n)$ , driven by L15 (BFS inside binary search).
Space: $O(n²)$ .

Approach 2: Modified Dijkstra, min-max path (optimal)

Think of the path cost as max(cell values on path) instead of sum. Dijkstra still works: at each pop, the priority is the max cell value on the best path to that cell.

import heapq

def swim_in_water(grid):
    n = len(grid)                                               # L1: O(1)
    heap = [(grid[0][0], 0, 0)]                                # L2: O(1) seed heap with top-left
    visited = set()                                            # L3: O(1) init visited
    while heap:                                                # L4: main loop, at most n² pops
        t, r, c = heapq.heappop(heap)                         # L5: O(log n²) = O(log n) pop
        if (r, c) in visited:                                  # L6: O(1) stale check
            continue
        visited.add((r, c))                                    # L7: O(1)
        if (r, c) == (n - 1, n - 1):                          # L8: O(1) goal check
            return t
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc                           # L9: O(1) per neighbor
            if 0 <= nr < n and 0 <= nc < n and (nr, nc) not in visited:
                heapq.heappush(heap, (max(t, grid[nr][nc]), nr, nc))  # L10: O(log n) push
    return -1

function swimInWater(grid: number[][]): number {
    const n = grid.length;                                            // L1: O(1)
    const heap = new MinHeap();
    heap.push([grid[0][0], 0, 0]);                                   // L2: O(1) seed heap with top-left
    const visited = new Set<number>();                                // L3: O(1) init visited

    while (heap.size > 0) {                                          // L4: main loop, at most n² pops
        const [t, r, c] = heap.pop();                                // L5: O(log n) pop
        const key = r * n + c;
        if (visited.has(key)) continue;                              // L6: O(1) stale check
        visited.add(key);                                            // L7: O(1)
        if (r === n - 1 && c === n - 1) return t;                   // L8: O(1) goal check
        for (const [dr, dc] of [[1,0],[-1,0],[0,1],[0,-1]]) {
            const nr = r + dr, nc = c + dc;                         // L9: O(1) per neighbor
            if (nr >= 0 && nr < n && nc >= 0 && nc < n && !visited.has(nr * n + nc)) {
                heap.push([Math.max(t, grid[nr][nc]), nr, nc]);     // L10: O(log n) push
            }
        }
    }
    return -1;
}

// See 778-swim-in-rising-water-approach2.go for the full runnable program.
// Core function uses container/heap with Item778{t, r, c int}.
func swimInWater(grid [][]int) int {
    n := len(grid)                                              // L1: O(1)
    h := &MinHeap778{{t: grid[0][0], r: 0, c: 0}}
    heap.Init(h)                                               // L2: O(1) seed heap with top-left
    visited := make([][]bool, n)
    for i := range visited { visited[i] = make([]bool, n) }   // L3: O(1) init visited
    dirs := [][2]int{{1,0},{-1,0},{0,1},{0,-1}}
    for h.Len() > 0 {                                          // L4: main loop, at most n² pops
        item := heap.Pop(h).(Item778)
        t, r, c := item.t, item.r, item.c                     // L5: O(log n) pop
        if visited[r][c] { continue }                          // L6: O(1) stale check
        visited[r][c] = true                                   // L7: O(1)
        if r == n-1 && c == n-1 { return t }                  // L8: O(1) goal check
        for _, d := range dirs {
            nr, nc := r+d[0], c+d[1]                          // L9: O(1) per neighbor
            if nr >= 0 && nr < n && nc >= 0 && nc < n && !visited[nr][nc] {
                next := grid[nr][nc]
                if t > next { next = t }
                heap.Push(h, Item778{t: next, r: nr, c: nc})  // L10: O(log n) push
            }
        }
    }
    return -1
}

Where the time goes, line by line

Variables: n = grid side length (n×n grid).

Line	Per-call cost	Times executed	Contribution
L1-L3 (init)	$O(1)$	1	$O(1)$
L4 (loop test)	$O(1)$	up to n²	$O(n²)$
L5 (heappop)	$O(log n)$	n²	$O(n² log n)$ ← dominates
L6-L8 (checks)	$O(1)$	n²	$O(n²)$
L9 (neighbors)	$O(1)$	4n² total	$O(n²)$
L10 (heappush)	$O(log n)$	up to 4n²	$O(n² log n)$ ← dominates

The heap holds at most n² entries (one per cell). Each cell is popped exactly once after being visited. Each pop and push costs $O(log(n²)$ ) = $O(log n)$ . With n² cells and 4 neighbors each: $O(n² log n)$ total. The max(t, grid[nr][nc]) at L10 is the key insight: path cost becomes the bottleneck elevation, not the sum.

Complexity

Time: $O(n² log n)$ , driven by L5/L10 (heap pop/push, n² cells, each $O(log n)$ ).
Space: $O(n²)$ .

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

final class Solution {
    func swimInWater(_ grid: [[Int]]) -> Int {
        let n = grid.count, directions = [(1,0),(-1,0),(0,1),(0,-1)]; var best = Array(repeating: Array(repeating: Int.max, count: n), count: n); best[0][0] = grid[0][0]
        var queue = BinaryHeap<(Int,Int,Int)>(hasHigherPriority: { $0.0 < $1.0 }); queue.insert((grid[0][0],0,0))
        while let (time,row,col) = queue.removeRoot() { if row == n-1 && col == n-1 { return time }; if time != best[row][col] { continue }; for (dr,dc) in directions { let r=row+dr,c=col+dc; if r>=0 && r<n && c>=0 && c<n { let candidate=max(time,grid[r][c]); if candidate < best[r][c] { best[r][c]=candidate; queue.insert((candidate,r,c)) } } } }; return -1
    }
}

Approach 3: Union-Find with sorted cell activation

Sort cells by elevation. Activate in order; whenever activating a cell merges the start and end into one component, return its elevation.

def swim_in_water(grid):
    n = len(grid)
    # (value, r, c), sorted ascending by value
    cells = sorted((grid[r][c], r, c) for r in range(n) for c in range(n))  # L1: O(n² log n)
    parent = list(range(n * n))      # L2: O(n²) init union-find
    active = [False] * (n * n)       # L3: O(n²) init active flags

    def find(x):                     # L4: path-compressed find, near O(1) amortized
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    def union(a, b):                 # L5: O(1) union by root reassignment
        ra, rb = find(a), find(b)
        if ra != rb:
            parent[ra] = rb

    for v, r, c in cells:           # L6: iterate n² cells in elevation order
        idx = r * n + c
        active[idx] = True           # L7: O(1) activate cell
        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 active[nr * n + nc]:
                union(idx, nr * n + nc)  # L8: near O(1) amortized
        if find(0) == find(n * n - 1):   # L9: O(1) check if connected
            return v
    return -1

function swimInWater(grid: number[][]): number {
    const n = grid.length;
    const cells: [number, number, number][] = [];
    for (let r = 0; r < n; r++)
        for (let c = 0; c < n; c++)
            cells.push([grid[r][c], r, c]);
    cells.sort((a, b) => a[0] - b[0]);              // L1: O(n² log n)

    const parent = Array.from({ length: n * n }, (_, i) => i);  // L2: O(n²) init union-find
    const active = new Array(n * n).fill(false);                 // L3: O(n²) init active flags

    function find(x: number): number {               // L4: path-compressed find
        while (parent[x] !== x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }

    function union(a: number, b: number): void {     // L5: O(1) union
        const ra = find(a), rb = find(b);
        if (ra !== rb) parent[ra] = rb;
    }

    for (const [v, r, c] of cells) {                // L6: iterate n² cells in elevation order
        const idx = r * n + c;
        active[idx] = true;                          // L7: O(1) activate cell
        for (const [dr, dc] of [[1,0],[-1,0],[0,1],[0,-1]]) {
            const nr = r + dr, nc = c + dc;
            if (nr >= 0 && nr < n && nc >= 0 && nc < n && active[nr * n + nc]) {
                union(idx, nr * n + nc);             // L8: near O(1) amortized
            }
        }
        if (find(0) === find(n * n - 1)) return v;  // L9: O(1) check if connected
    }
    return -1;
}

// See 778-swim-in-rising-water-approach3.go for the full runnable program.
// Core function uses sort + union-find.
func swimInWater(grid [][]int) int {
    n := len(grid)
    type Cell struct{ v, r, c int }
    cells := make([]Cell, 0, n*n)
    for r := 0; r < n; r++ {
        for c := 0; c < n; c++ {
            cells = append(cells, Cell{grid[r][c], r, c})
        }
    }
    sort.Slice(cells, func(i, j int) bool { return cells[i].v < cells[j].v })  // L1: O(n² log n)
    parent := make([]int, n*n)
    for i := range parent { parent[i] = i }                // L2: O(n²) init union-find
    active := make([]bool, n*n)                            // L3: O(n²) init active flags
    var find func(int) int
    find = func(x int) int {                               // L4: path-compressed find
        for parent[x] != x { parent[x] = parent[parent[x]]; x = parent[x] }
        return x
    }
    union := func(a, b int) {                              // L5: O(1) union
        ra, rb := find(a), find(b)
        if ra != rb { parent[ra] = rb }
    }
    dirs := [][2]int{{1,0},{-1,0},{0,1},{0,-1}}
    for _, cell := range cells {                           // L6: iterate n² cells in elevation order
        idx := cell.r*n + cell.c
        active[idx] = true                                 // L7: O(1) activate cell
        for _, d := range dirs {
            nr, nc := cell.r+d[0], cell.c+d[1]
            if nr >= 0 && nr < n && nc >= 0 && nc < n && active[nr*n+nc] {
                union(idx, nr*n+nc)                        // L8: near O(1) amortized
            }
        }
        if find(0) == find(n*n-1) { return cell.v }       // L9: O(1) check if connected
    }
    return -1
}

Where the time goes, line by line

Variables: n = grid side length (n×n grid).

Line	Per-call cost	Times executed	Contribution
L1 (sort cells)	$O(n² log n)$	1	$O(n² log n)$ ← dominates
L2-L3 (init arrays)	$O(1)$	n² each	$O(n²)$
L6 (cell loop)	$O(1)$	n²	$O(n²)$
L7 (activate)	$O(1)$	n²	$O(n²)$
L8 (union)	near $O(1)$ amortized	up to 4n²	$O(n²)$
L9 (connectivity check)	near $O(1)$ amortized	n²	$O(n²)$

L1 dominates: sorting n² cells costs $O(n² log n)$ . The union-find operations (L8/L9) use path compression with halving, giving amortized near- $O(1)$ per operation (technically $O(α(n²)$ ) where α is the inverse Ackermann function, effectively constant for all practical n).

Complexity

Time: $O(n² log n)$ , dominated by L1 (sorting), with near- $O(n²)$ for the union-find passes.
Space: $O(n²)$ .

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

final class Solution {
    func swimInWater(_ grid: [[Int]]) -> Int {
        let n = grid.count, directions = [(1,0),(-1,0),(0,1),(0,-1)], cells = (0..<n).flatMap { row in (0..<n).map { (grid[row][$0], row, $0) } }.sorted { $0.0 < $1.0 }
        var parent = Array(0..<(n*n)), active = Array(repeating:false,count:n*n)
        func find(_ value:Int)->Int { var node=value; while parent[node] != node { node=parent[node] }; return node }
        func unite(_ a:Int,_ b:Int) { let rootA=find(a),rootB=find(b); if rootA != rootB { parent[rootB]=rootA } }
        for (height,row,col) in cells { let id=row*n+col; active[id]=true; for (dr,dc) in directions { let r=row+dr,c=col+dc; if r>=0 && r<n && c>=0 && c<n && active[r*n+c] { unite(id,r*n+c) } }; if active[0] && active[n*n-1] && find(0)==find(n*n-1) { return height } }; return -1
    }
}

Summary

Approach	Time	Space	Notes
Binary search + BFS	$O(n² log n)$	$O(n²)$	Clean, generalizes
Modified Dijkstra (min-max)	$O(n² log n)$	$O(n²)$	Canonical
Union-Find with sorted cells	$O(n² log n)$	$O(n²)$	Neat alternative

All three are $O(n² log n)$ . Dijkstra with min-max edge weights is the most reusable, same template solves problems like “min maximum capacity path.”

Test cases

import heapq

def swim_in_water(grid):
    n = len(grid)
    heap = [(grid[0][0], 0, 0)]
    visited = set()
    while heap:
        t, r, c = heapq.heappop(heap)
        if (r, c) in visited:
            continue
        visited.add((r, c))
        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 visited:
                heapq.heappush(heap, (max(t, grid[nr][nc]), nr, nc))
    return -1

def _run_tests():
    # Example 1: 2x2 grid, must cross elevation 3
    assert swim_in_water([[0,2],[1,3]]) == 3
    # Example 2: 5x5 spiral, answer is 16
    assert swim_in_water([
        [0,1,2,3,4],
        [24,23,22,21,5],
        [12,13,14,15,16],
        [11,17,18,19,20],
        [10,9,8,7,6]
    ]) == 16
    # Single cell: already at destination
    assert swim_in_water([[0]]) == 0
    # 1x1 with nonzero elevation
    assert swim_in_water([[7]]) == 7
    # 2x2, direct path available via low values
    assert swim_in_water([[0,1],[3,2]]) == 2
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

// Uses modified Dijkstra (Approach 2) with inline MinHeap.
class MinHeap {
    private data: [number, number, number][] = [];
    push(item: [number, number, number]): void {
        this.data.push(item);
        let i = this.data.length - 1;
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.data[p][0] <= this.data[i][0]) break;
            [this.data[p], this.data[i]] = [this.data[i], this.data[p]];
            i = p;
        }
    }
    pop(): [number, number, number] {
        const top = this.data[0];
        const last = this.data.pop()!;
        if (this.data.length > 0) {
            this.data[0] = last;
            let i = 0;
            while (true) {
                let s = i;
                const l = 2 * i + 1, r = 2 * i + 2;
                if (l < this.data.length && this.data[l][0] < this.data[s][0]) s = l;
                if (r < this.data.length && this.data[r][0] < this.data[s][0]) s = r;
                if (s === i) break;
                [this.data[s], this.data[i]] = [this.data[i], this.data[s]];
                i = s;
            }
        }
        return top;
    }
    get size(): number { return this.data.length; }
}

function swimInWater(grid: number[][]): number {
    const n = grid.length;
    const heap = new MinHeap();
    heap.push([grid[0][0], 0, 0]);
    const visited = new Set<number>();
    while (heap.size > 0) {
        const [t, r, c] = heap.pop();
        const key = r * n + c;
        if (visited.has(key)) continue;
        visited.add(key);
        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 && nr < n && nc >= 0 && nc < n && !visited.has(nr * n + nc)) {
                heap.push([Math.max(t, grid[nr][nc]), nr, nc]);
            }
        }
    }
    return -1;
}

console.assert(swimInWater([[0,2],[1,3]]) === 3);
console.assert(swimInWater([[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]) === 16);
console.assert(swimInWater([[0]]) === 0);
console.assert(swimInWater([[7]]) === 7);
console.assert(swimInWater([[0,1],[3,2]]) === 2);
console.log("all tests pass");

Graphs, Dijkstra variant; union-find with sorted edges
Heaps / Priority Queues, Dijkstra frontier
Arrays, grid

Binary Search on Answer, feasibility-search tactics for finding the smallest or largest value that satisfies a monotonic condition.
Dijkstra, non-negative weighted shortest-path tactics using a priority queue frontier.
Shortest Paths, path-cost tactics for finding minimum distance, time, risk, or transformation count through a graph.

778. Swim in Rising Water (Hard)

Problem

Try it yourself

Approach 1: Brute force, binary search on t + BFS

Approach 2: Modified Dijkstra, min-max path (optimal)

Approach 3: Union-Find with sorted cell activation

Summary

Test cases

Related data structures

Related concepts

Approach 1: Brute force, binary search on `t` + BFS