Find Minimum Time to Reach Last Room I - Solution & Explanation

Problem Overview: You are given a grid where each cell represents a room and contains the earliest time you are allowed to enter it. Starting from the top-left room, you can move up, down, left, or right. The goal is to compute the minimum time required to reach the bottom-right room while respecting each room’s time constraint.

Approach 1: Breadth-First Search (BFS) with Time Adjustment (Time: O(m * n), Space: O(m * n))

This approach models the grid as a graph and explores rooms using graph traversal. A queue processes cells level by level while tracking the current time needed to reach each position. When moving to a neighbor, you check whether the arrival time is earlier than the room’s allowed time. If it is, you wait until the room becomes available before continuing. Each room is visited with the earliest feasible arrival time, and a visited or distance matrix prevents redundant processing.

This BFS-style traversal works because movement cost between rooms is uniform (one time unit per move). The main adjustment is handling waiting time when the next room is locked until a certain timestamp. The algorithm iterates through four directions for each cell and updates the earliest reachable time. Space is used for the queue and a matrix storing the minimum time discovered so far.

Approach 2: Dijkstra's Algorithm with Min Heap (Time: O(m * n log(m * n)), Space: O(m * n))

A more robust solution treats the grid as a weighted graph and applies shortest path computation using Dijkstra’s algorithm. Each cell is a node, and the cost of moving depends on both the travel step (1 unit) and any waiting time required by the destination cell. A min heap (priority queue) always processes the cell with the smallest current time first.

When expanding a node, you compute the tentative arrival time for each neighbor. If the neighbor requires a later entry time, the algorithm waits until that timestamp before pushing it into the heap. The distance matrix stores the best known arrival time for every cell, preventing worse paths from being processed again. This method naturally handles varying arrival constraints and guarantees the optimal path.

The use of a priority queue from heap-based data structures ensures the next explored state always has the minimum time cost. This pattern appears frequently in grid-based shortest path problems and is reliable even when waiting times or dynamic costs exist.

Recommended for interviews: Dijkstra’s algorithm is the expected solution. It demonstrates understanding of shortest path problems on weighted graphs and proper use of a priority queue. Implementing the BFS-style exploration first can help clarify the traversal logic, but the heap-based Dijkstra approach is the most general and interview-ready solution.