3341. Find Minimum Time to Reach Last Room I LeetCode Solution
In this guide, you will get 3341. Find Minimum Time to Reach Last Room I LeetCode Solution with the best time and space complexity. The solution to Find Minimum Time to Reach Last Room I 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 I
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.
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 one second.
Input: moveTime = [[0,0,0],[0,0,0]]
Output: 3
Explanation:
The minimum time required is 3 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 one second.
At time 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 <= 50
2 <= m == moveTime[i].length <= 50
0 <= moveTime[i][j] <= 109
Complexity Analysis
Time Complexity: O(mn\log mn)
Space Complexity: O(mn)
3341. Find Minimum Time to Reach Last Room I LeetCode Solution in C++
class Solution {
public:
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, u)
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) + 1;
if (newDist < dist[x][y]) {
dist[x][y] = newDist;
minHeap.push({newDist, {x, y}});
}
}
}
return -1;
}
}; /* code provided by PROGIEZ */
3341. Find Minimum Time to Reach Last Room I LeetCode Solution in Java
class Solution {
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, u)
};
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) + 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
3341. Find Minimum Time to Reach Last Room I LeetCode Solution in Python
class Solution:
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, u)
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) + 1
if newDist < dist[x][y]:
dist[x][y] = newDist
heapq.heappush(minHeap, (newDist, (x, y)))
return -1 # code by PROGIEZ
