Compute earliest arrival in time-grid
Company: DoorDash
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
##### Question
LeetCode 778. Swim in Rising Water – Given an n x n integer grid where grid[i][j] is the earliest time you can enter the cell, starting from (0,
0) move 4-directionally only when the current time is ≥ the target cell's value; find the minimum time to reach (n-1,n-
1).
https://leetcode.com/problems/swim-in-rising-water/description/
Quick Answer: This question evaluates algorithmic problem-solving and pathfinding skills on grid-based graphs, focusing on modeling time-dependent traversal constraints and reasoning about efficient search and supporting data structures.
You are given an `n x n` integer grid where `grid[i][j]` is the earliest time at which you may enter cell `(i, j)`.
You start at the top-left cell `(0, 0)` at time `0`. At each moment you may move 4-directionally (up, down, left, right) to an adjacent cell, but you may only enter a cell once the current time is at least that cell's value. Moving between cells is instantaneous; the only constraint is the elevation/time threshold of each cell.
Return the minimum time required to reach the bottom-right cell `(n - 1, n - 1)`.
Equivalently: among all paths from `(0, 0)` to `(n - 1, n - 1)`, the cost of a path is the maximum cell value along it (you must wait until time equals the highest threshold on the path). Return the minimum such maximum over all paths.
Example:
- `grid = [[0,2],[1,3]]` -> `3`. The fastest path is `(0,0) -> (1,0) -> (1,1)`; the max cell value along it is `3`, so you reach the end at time 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`.
Constraints
- n == grid.length == grid[i].length
- 1 <= n <= 50
- 0 <= grid[i][j] < n * n
- Each value in the range [0, n*n - 1] appears exactly once in the grid (a permutation), though the algorithm does not rely on this.
- You start at (0, 0) and must reach (n-1, n-1).
Examples
Input: ([[0,2],[1,3]],)
Expected Output: 3
Explanation: Path (0,0)->(1,0)->(1,1) has max value 3; you must wait until time 3 to enter cell (1,1).
Input: ([[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]],)
Expected Output: 16
Explanation: The optimal route snakes through the grid with a bottleneck cell of value 16, so the earliest arrival is time 16.
Hints
- Reframe the problem: the time to traverse a path equals the maximum cell value along that path. You want the path whose maximum value is as small as possible (a minimax / bottleneck path problem).
- A Dijkstra-style search works: maintain a min-heap keyed by 'the largest cell value seen so far on the best route to this cell'. Pop the smallest such key and relax neighbors with max(currentTime, neighborValue).
- Alternatives: binary search on the answer T plus a BFS/DFS checking whether (n-1,n-1) is reachable using only cells <= T; or Union-Find, adding cells in increasing value order until (0,0) and (n-1,n-1) become connected.
- Mark a cell visited when you first push it (its first pop is already optimal under the minimax key), so each cell is processed once.