3342. Find Minimum Time to Reach Last Room II LeetCode Solution
In this guide, you will get 3342. Find Minimum Time to Reach Last Room II LeetCode Solution with the best time and space complexity. The solution to Find Minimum Time to Reach Last Room II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Find Minimum Time to Reach Last Room II
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 one second for one move and two seconds for the next, alternating between the two.
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: 7
Explanation:
The minimum time required is 7 seconds.
At time t == 4, move from room (0, 0) to room (1, 0) in one second.
At time t == 5, move from room (1, 0) to room (1, 1) in two seconds.
Input: moveTime = [[0,0,0,0],[0,0,0,0]]
Output: 6
Explanation:
The minimum time required is 6 seconds.
At time t == 0, move from room (0, 0) to room (1, 0) in one second.
At time t == 1, move from room (1, 0) to room (1, 1) in two seconds.
At time t == 3, move from room (1, 1) to room (1, 2) in one second.
At time t == 4, move from room (1, 2) to room (1, 3) in two seconds.
Example 3:
Input: moveTime = [[0,1],[1,2]]
Output: 4
Constraints:
2 <= n == moveTime.length <= 750
2 <= m == moveTime[i].length <= 750
0 <= moveTime[i][j] <= 109
Complexity Analysis
Time Complexity: O(mn\log mn)
Space Complexity: O(mn)
3342. Find Minimum Time to Reach Last Room II LeetCode Solution in C++
class Solution {
public:
// Similar to 3341. Find Minimum Time to Reach Last Room I
int minTimeToReach(vector<vector<int>>& moveTime) {
return dijkstra(moveTime, {0, 0},
{moveTime.size() - 1, moveTime[0].size() - 1});
}
private:
int dijkstra(const vector<vector<int>>& moveTime, const pair<int, int>& src,
const pair<int, int>& dst) {
constexpr int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
const int m = moveTime.size();
const int n = moveTime[0].size();
vector<vector<int>> dist(m, vector<int>(n, INT_MAX));
dist[0][0] = 0;
using T = pair<int, pair<int, int>>; // (d, (ux, uy))
priority_queue<T, vector<T>, greater<>> minHeap;
minHeap.push({dist[0][0], src});
while (!minHeap.empty()) {
const auto [d, u] = minHeap.top();
minHeap.pop();
if (u == dst)
return d;
const auto [i, j] = u;
if (d > dist[i][j])
continue;
for (const auto& [dx, dy] : dirs) {
const int x = i + dx;
const int y = j + dy;
if (x < 0 || x == m || y < 0 || y == n)
continue;
const int newDist = max(moveTime[x][y], d) + ((i + j) % 2 + 1);
if (newDist < dist[x][y]) {
dist[x][y] = newDist;
minHeap.push({newDist, {x, y}});
}
}
}
return -1;
}
}; /* code provided by PROGIEZ */
3342. Find Minimum Time to Reach Last Room II LeetCode Solution in Java
class Solution {
// Similar to 3341. Find Minimum Time to Reach Last Room I
public int minTimeToReach(int[][] moveTime) {
return dijkstra(moveTime, new Pair<>(0, 0),
new Pair<>(moveTime.length - 1, moveTime[0].length - 1));
}
private int dijkstra(int[][] moveTime, Pair<Integer, Integer> src, Pair<Integer, Integer> dst) {
final int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
final int m = moveTime.length;
final int n = moveTime[0].length;
int[][] dist = new int[m][n];
Arrays.stream(dist).forEach(A -> Arrays.fill(A, Integer.MAX_VALUE));
dist[0][0] = 0;
Queue<Pair<Integer, Pair<Integer, Integer>>> minHeap =
new PriorityQueue<>(Comparator.comparing(Pair::getKey)) {
{ offer(new Pair<>(dist[0][0], src)); } // (d, (ux, uy))
};
while (!minHeap.isEmpty()) {
final int d = minHeap.peek().getKey();
final Pair<Integer, Integer> u = minHeap.poll().getValue();
if (u.equals(dst))
return d;
final int i = u.getKey();
final int j = u.getValue();
if (d > dist[i][j])
continue;
for (int[] dir : dirs) {
final int x = i + dir[0];
final int y = j + dir[1];
if (x < 0 || x == m || y < 0 || y == n)
continue;
final int newDist = Math.max(moveTime[x][y], d) + ((i + j) % 2 + 1);
if (newDist < dist[x][y]) {
dist[x][y] = newDist;
minHeap.offer(new Pair<>(newDist, new Pair<>(x, y)));
}
}
}
return -1;
}
} // code provided by PROGIEZ
3342. Find Minimum Time to Reach Last Room II LeetCode Solution in Python
class Solution:
# Similar to 3341. Find Minimum Time to Reach Last Room I
def minTimeToReach(self, moveTime: list[list[int]]) -> int:
return self._dijkstra(moveTime,
(0, 0),
(len(moveTime) - 1, len(moveTime[0]) - 1))
def _dijkstra(
self,
moveTime: list[list[int]],
src: tuple[int, int],
dst: tuple[int, int]
) -> int:
dirs = ((0, 1), (1, 0), (0, -1), (-1, 0))
m = len(moveTime)
n = len(moveTime[0])
dist = [[math.inf] * n for _ in range(m)]
dist[0][0] = 0
minHeap = [(0, src)] # (d, (ux, uy))
while minHeap:
d, u = heapq.heappop(minHeap)
if u == dst:
return d
i, j = u
if d > dist[i][j]:
continue
for dx, dy in dirs:
x = i + dx
y = j + dy
if x < 0 or x == m or y < 0 or y == n:
continue
newDist = max(moveTime[x][y], d) + (i + j) % 2 + 1
if newDist < dist[x][y]:
dist[x][y] = newDist
heapq.heappush(minHeap, (newDist, (x, y)))
return -1 # code by PROGIEZ
