Find Minimum Time to Reach Last Room II - Video Solutions

Problem Overview: You are given a grid where each cell represents a room and the value indicates the earliest time you are allowed to enter it. Starting from the top‑left room, the goal is to reach the bottom‑right room in the minimum possible time while respecting each room’s time constraint.

Approach 1: Dijkstra's Algorithm (Time: O(mn log(mn)), Space: O(mn))

This problem behaves like a weighted shortest path problem on a grid. Each room is a node, and moving to a neighbor takes time while also respecting the earliest entry time of that room. Use a graph model where edges connect adjacent cells. A priority queue always expands the room with the smallest arrival time. When moving to a neighbor, compute the earliest valid arrival time: if the room is locked until a later time, you must wait before entering. This approach guarantees the optimal path because Dijkstra always processes the smallest known distance first.

Approach 2: Dijkstra's Algorithm for Grid (Time: O(mn log(mn)), Space: O(mn))

This is a grid‑optimized version of the previous idea. Instead of explicitly building a graph, treat each cell directly as a node and explore the four directions (up, down, left, right). Maintain a distance matrix storing the earliest time each cell can be reached. Push states into a min‑heap and relax neighbors just like standard shortest path problems. The key step is adjusting arrival time to satisfy the room’s opening constraint before pushing it to the heap.

Approach 3: Dynamic Programming (Time: O(mn), Space: O(mn))

A dynamic programming approach attempts to propagate the earliest reachable time through the grid. For each cell, compute the minimum arrival time based on previously processed neighbors while respecting the cell’s availability constraint. This works best when transitions follow a predictable order, but because movement can occur in multiple directions, updates may need to be revisited. In practice, DP alone becomes tricky for general shortest path scenarios but still provides intuition about how time constraints propagate across the grid.

Approach 4: Dynamic Programming with Breadth‑First Search (Time: O(mn), Space: O(mn))

This hybrid approach combines BFS traversal with DP‑style state updates. BFS explores reachable cells layer by layer while maintaining the earliest arrival time for each room. If reaching a neighbor requires waiting due to its time constraint, the algorithm updates the state and reprocesses it when a better arrival time appears. This reduces redundant exploration compared to naive BFS but still tracks time states carefully.

Recommended for interviews: Dijkstra’s algorithm is the expected solution. The grid naturally forms a weighted graph where each transition may include waiting time, making a priority queue approach the most reliable. Explaining the brute reasoning first and then modeling the grid as a shortest path problem demonstrates strong problem‑solving and graph fundamentals.