Find Minimum Time Across a Grid
Company: Bytedance
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given an `n x n` grid of non-negative integers. Each value represents the earliest time at which that cell becomes traversable.
You start at the top-left cell `(0, 0)` at time `0` and want to reach the bottom-right cell `(n - 1, n - 1)`. At any time `T`, you may stand on or move into a cell only if its value is less than or equal to `T`. You may move one step at a time in the four cardinal directions: up, down, left, and right.
Return the minimum time `T` such that there exists a valid path from the top-left corner to the bottom-right corner.
Example:
- Input:
```
grid = [
[0, 2],
[1, 3]
]
```
- Output: `3`
Because you cannot enter the bottom-right cell until time `3`, the earliest feasible path is available at `T = 3`.
Discuss possible approaches such as priority queue traversal, binary search with reachability checking, or disjoint set union.
Quick Answer: This question evaluates algorithm design and problem-solving skills related to grid-based reachability with time-dependent constraints, assessing the ability to model traversal feasibility and optimize the earliest feasible arrival time.
Return the minimum time T such that a path exists from top-left to bottom-right through cells with value <= T.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ([[0,2],[1,3]],)
Expected Output: 3
Explanation: Bottom-right is reachable at time 3.
Input: ([[0,1,2],[5,4,3],[6,7,8]],)
Expected Output: 8
Explanation: Priority traversal minimizes the maximum cell value on the path.
Input: ([[7]],)
Expected Output: 7
Explanation: Single-cell answer is its own traversable time.
Hints
- This is a minimax path problem.
- Use Dijkstra where path cost is the maximum cell value seen so far.