DSA problem
Find Minimum Time to Reach Last Room I
You are given an n × m integer grid moveTime. Cell (r, c) cannot be entered before time moveTime[r][c], and moving from any cell to an orthogonal neighbour takes exactly one unit of time. You start at (0, 0) at time 0 and must reach (n - 1, m - 1). Return the minimum time at which you can be standing in the last cell.
The wrinkle that separates this from a plain BFS is that some cells are "locked" until a future moment. If you arrive at a neighbour earlier than its moveTime you must wait, which makes the cost of stepping into (r, c) depend on the current time. Specifically, if you are at time t in some adjacent cell, then entering (r, c) costs max(t, moveTime[r][c]) + 1: you wait until the room unlocks (if needed), then spend one unit to step in.
That formulation matches Dijkstra perfectly: the "distance" you track is the earliest arrival time, and each transition is a non-negative weight that depends on the current distance — but only by being a non-decreasing function of it. Dijkstra is still correct in this setting because if you pop a cell with time t, any later relaxation could only land you there at t' >= t, which is no better.
So run Dijkstra with a min-heap keyed by arrival time. The grid has n * m cells and four edges per cell, so the complexity is O(nm log(nm)) time and O(nm) space — fast enough for the constraint n, m <= 50.
Examples
moveTime = [[0,4],[4,4]]6moveTime = [[0,0,0],[0,0,0]]3moveTime = [[0,1],[1,2]]3Constraints
- 2 <= n == moveTime.length <= 50
- 2 <= m == moveTime[i].length <= 50
- 0 <= moveTime[i][j] <= 10^9
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.