Is Find Minimum Time to Reach Last Room II easy or hard?

The problem is rated Medium because it requires recognizing the grid as a shortest path graph with time constraints. Implementing Dijkstra’s algorithm with correct waiting logic can be tricky, but the overall concept is standard for candidates familiar with graph traversal.

Find Minimum Time to Reach Last Room II Python/Java solution

Python solutions typically implement Dijkstra’s algorithm using heapq to maintain the priority queue. Java implementations use PriorityQueue with a custom comparator and a 2D distance array. Both versions follow the same shortest path logic with O(mn log(mn)) complexity.

How to solve Find Minimum Time to Reach Last Room II in O(mn log mn)?

Model the grid as a shortest path problem. Use a min‑heap to store states as (time, row, column). From each cell, explore four directions and compute the earliest valid time to enter the neighbor by considering its constraint value. Update the distance matrix and push the new state into the heap if the arrival time improves.

What is the best approach for Find Minimum Time to Reach Last Room II?

The best approach is Dijkstra's algorithm using a priority queue. Each grid cell is treated as a node, and the algorithm always processes the cell with the smallest arrival time. When moving to a neighbor, the arrival time must respect that room’s earliest available time, which may require waiting. This results in a time complexity of O(mn log(mn)).

Is Find Minimum Time to Reach Last Room II asked at Google/Amazon/Meta?

Grid shortest path problems with constraints frequently appear in interviews at companies like Google, Amazon, and Meta. Variants involving Dijkstra’s algorithm, priority queues, and matrix traversal are especially common because they test graph modeling and optimization skills.

What data structure is used in Find Minimum Time to Reach Last Room II?

The key data structure is a min‑heap (priority queue) used in Dijkstra’s algorithm. It ensures the next cell processed always has the smallest known arrival time. A distance matrix is also used to track the earliest time each room can be reached.

What is the time complexity of Find Minimum Time to Reach Last Room II?

The optimal solution using Dijkstra’s algorithm runs in O(mn log(mn)) time, where m and n are the grid dimensions. Each cell may be pushed into a priority queue, and heap operations cost log(mn). Space complexity is O(mn) for the distance matrix and heap storage.

Description Hints 1 Solution Video 20:02

3342. Find Minimum Time to Reach Last Room II

Medium67.3% acceptance3 companies

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.

Example 2:

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] <= 10⁹

Asked at 3 companies

Uber

Google Amazon

Topics

Array Graph Heap (Priority Queue)Matrix Shortest Path

Hints open one at a time

Hint 1

Use shortest path algorithms with a state for the last move being odd or even indexed.

20:02

Still stuck?Read 5 approaches, or watch a walkthrough.

Open solution