- 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]); }};