🌱 Keegan's Digital Garden

3342. Find Minimum Time to Reach Last Room II

3 min read

📝 Problem Details

💭What Were My Initial Thoughts?

- Dynamic Programming at first glance
- Upon additional reading, the question quite clearly outlines the need for a "shortest path"
	- Looks like the solution will involve using something like Dijkstras on our grid
- The question constraints also indicate that we need something in logarithmic time, as the length of n or m can be at most 750.

🤔What Did I Struggle With?

- employing dijkstras in a matrix 
- logic for adjacent directional movement

💡 Explanation of Solution

State Representation:
- Use Dijkstra's on a graph where each node corresponds to a state (row,col,parity)
	- (row, col) are the coordinates of the cell
	- parity indicates whether the next steps costs 1 or 2 seconds
		- parity = 0 → next step costs 1 second
		- parity = 1 → next step costs 2 seconds
	- initial state: (0,0,0) at time 0, since the first step will cost 1 second

Transition (from (r,c, parity)):
1. current_time = dist[r][c][parity]
2. determine start_move_time = max(current_time, moveTime[nr][nc]) for a neighbour (nr, nc)
3. calculate step_cost = 1 if parity = 0, else step_cost = 2
4. compute arrival_time = start_move_time + step_cost
5. the next parity will be 1-parity

if arrival_time < dist[nr][nc][1-parity], update dist[nr][nc][1-parity] and push the state into the priority queue

Termination:
- once you pop (n-1, m-1) from the queue, you have found the minimum time to reach the last cell
- alternatively, after all states are processed, take the minimum of `dist[n-1][m-1][0]` and `dist[n-1][m-1][1]`

⌛ Complexity Analysis

O(n*m*log(n*m)) Time Complexity
with regards to the priority queue usage

💻 Implementation of Solution

class Solution {
public:
    int minTimeToReach(vector<vector<int>>& moveTime) {
        int n = (int)moveTime.size();
        int m = (int)moveTime[0].size();
        
        // dist[r][c][parity]: the earliest time to be at cell (r,c) when the next step 
        // will cost (parity == 0 ? 1 second : 2 seconds)
        // Initialize with large value.
        vector<vector<vector<int>>> dist(n, vector<vector<int>>(m, vector<int>(2, INT_MAX)));
        
        // Min-heap for Dijkstra: (time, r, c, parity)
        priority_queue<array<int,4>, vector<array<int,4>>, greater<>> pq;
        
        // Start at (0,0) at time 0 with parity=0 (next step costs 1 second)
        dist[0][0][0] = 0;
        pq.push({0, 0, 0, 0});
        
        // Directions for adjacent moves
        int dr[4] = {1, -1, 0, 0};
        int dc[4] = {0, 0, 1, -1};
        
        while(!pq.empty()) {
            auto [curTime, r, c, p] = pq.top();
            pq.pop();
            
            // If we already found a better time for this state, skip
            if (curTime > dist[r][c][p]) continue;
            
            // If we reached the target cell
            if (r == n-1 && c == m-1) {
                return curTime; 
            }
            
            // Explore neighbors
            for (int i = 0; i < 4; i++) {
                int nr = r + dr[i], nc = c + dc[i];
                if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
                
                // We want to move into (nr, nc)
                // We must start the move at or after moveTime[nr][nc]
                int start_move_time = max(curTime, moveTime[nr][nc]);
                int step_cost = (p == 0) ? 1 : 2;
                int arrival_time = start_move_time + step_cost;
                int new_parity = 1 - p;
                
                if (arrival_time < dist[nr][nc][new_parity]) {
                    dist[nr][nc][new_parity] = arrival_time;
                    pq.push({arrival_time, nr, nc, new_parity});
                }
            }
        }
        
        // If somehow we never returned (should not happen), return the best known
        return min(dist[n-1][m-1][0], dist[n-1][m-1][1]);
    }
};

Graph View