Find Minimum Time To Reach Last Room
01 · Problem
A dungeon is an n x m grid of rooms. You stand in room (0, 0) at time t = 0 and want to reach room (n - 1, m - 1). You may move to an edge-adjacent room (up, down, left, right), and each move takes exactly one second.
You are given moveTime, where moveTime[i][j] is the earliest time at which you may start moving into room (i, j). If you are next to that room earlier, you must wait. So if you are in a neighbouring room at time t, you arrive in (i, j) at time max(t, moveTime[i][j]) + 1.
Return the minimum time at which you can arrive in room (n - 1, m - 1). The value moveTime[0][0] does not matter because you start there.
02 · Examples
moveTime = [[0,4],[4,4]]
6
Every move out of (0,0) must wait until t = 4, arriving at 5. One more move into (1,1) arrives at 6.
moveTime = [[0,0,0],[0,0,0]]
3
No waiting is required, so the shortest path of 3 moves arrives at time 3.
moveTime = [[0,1],[1,2]]
3
Move to (0,1) starting at t = 1, arriving at 2. Room (1,1) opens at 2, so the next move starts immediately and arrives at 3.
03 · Constraints
- 012 <= n == moveTime.length <= 50
- 022 <= m == moveTime[i].length <= 50
- 030 <= moveTime[i][j] <= 109
04 · Optimal complexity
- Time
- O(nm log(nm))
- Space
- O(nm)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.