There is a dungeon with n x m rooms arranged as a grid.
You are given a 2D array moveTime of size n x m, where moveTime[i][j] represents the minimum time in seconds when you can start moving to that room. You start from the room (0, 0) at time t = 0 and can move to an adjacent room. Moving between adjacent rooms takes exactly one second.
Return the minimum time to reach the room (n - 1, m - 1).
Two rooms are adjacent if they share a common wall, either horizontally or vertically.
Example 1:
Input: moveTime = [[0,4],[4,4]]
Output: 6
Explanation:
The minimum time required is 6 seconds.
t == 4, move from room (0, 0) to room (1, 0) in one second.t == 5, move from room (1, 0) to room (1, 1) in one second.Example 2:
Input: moveTime = [[0,0,0],[0,0,0]]
Output: 3
Explanation:
The minimum time required is 3 seconds.
t == 0, move from room (0, 0) to room (1, 0) in one second.t == 1, move from room (1, 0) to room (1, 1) in one second.t == 2, move from room (1, 1) to room (1, 2) in one second.Example 3:
Input: moveTime = [[0,1],[1,2]]
Output: 3
Constraints:
2 <= n == moveTime.length <= 502 <= m == moveTime[i].length <= 500 <= moveTime[i][j] <= 109This approach uses BFS to explore the grid starting from the top-left corner (0,0). We utilize a queue to manage current positions and a time tracking mechanism to monitor the minimum time needed to move to each adjacent room. We proceed only if moving is allowed by the given time constraints.
The code uses a deque for BFS traversal of the grid. It starts from the (0,0) room, considering movement directions (right, down, left, up). Each move's time is evaluated against the threshold specified in moveTime. If moving to a cell at any moment is permissible (max(current_time + 1, moveTime[new_x][new_y])), it's added to the queue. The loop exits when the bottom-right corner is reached.
JavaScript
The time complexity is O(n * m) as each room is processed once and can potentially be added to the queue. The space complexity is also O(n * m) due to the data structures (deque and set) used to keep track of explored positions.
We employ a modified Dijkstra's algorithm to find the shortest path. Dijkstra's typically finds the shortest path with minimum weights; here, we adapt it to find the earliest arrival time at each room utilizing a priority queue to guide selections by arrival time. This helps prioritize paths that meet time constraints optimally.
This Java solution deploys Dijkstra's algorithm with a priority queue managing room nodes ordered by time of arrival. This ensures rooms are processed earliest to latest possible visit time derived from their moveTime values. Once the last room is reached, the accumulated time provides the minimum time as defined by the problem.
C#
The time complexity is O(n * m log(n * m)) due to priority queue operations for n*m nodes. The space complexity is O(n * m) because of the data structures (queue, visited array) used.
| Approach | Complexity |
|---|---|
| Breadth-First Search (BFS) Approach | The time complexity is O(n * m) as each room is processed once and can potentially be added to the queue. The space complexity is also O(n * m) due to the data structures (deque and set) used to keep track of explored positions. |
| Dijkstra's Algorithm Approach | The time complexity is O(n * m log(n * m)) due to priority queue operations for n*m nodes. The space complexity is O(n * m) because of the data structures (queue, visited array) used. |
How many LeetCode problems should you solve? #leetcode #techinterview #developer #softwareengineer • CrioDo • 304,699 views views
Watch 9 more video solutions →Practice Find Minimum Time to Reach Last Room I with our built-in code editor and test cases.
Practice on FleetCode