How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at DoorDash.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at DoorDash during technical interviews.

Compute earliest arrival in time-grid | DoorDash Coding Question

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.

Input: ([[0]],)

Expected Output: 0

Explanation: Single cell: start and end coincide; the answer is the start cell's value 0.

Input: ([[3,2],[0,1]],)

Expected Output: 3

Explanation: Every path from (0,0) to (1,1) must pass through the start cell of value 3, so the bottleneck is 3.

Input: ([[0,1,2,3,4,24,23,22],[21,20,19,18,17,16,15,5],[14,13,12,11,10,9,8,6],[7,1,2,3,4,5,6,7],[8,9,10,11,12,13,14,8],[15,16,17,18,19,20,21,9],[22,23,24,25,26,27,28,10],[29,30,31,32,33,34,35,11]],)

Expected Output: 17

Explanation: Larger grid: the cheapest minimax route to the bottom-right has a maximum cell value of 17.

Input: ([[10,12],[13,11]],)

Expected Output: 12

Explanation: From (0,0)=10, going right to (0,1)=12 then down to (1,1)=11 has max 12; going down via (1,0)=13 has max 13. The better bottleneck is 12.

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.

Quick Overview

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.