Scale Engineer

Find Minimum Time to Reach Last Room II

Med
#2968Time: O(4^(N*M)). In the worst case, the algorithm explores a number of paths that is exponential in the number of cells in the grid.Space: O(N * M) for the recursion stack depth in the worst case, where N and M are the dimensions of the grid.
Algorithms
Shortest Path
Data structures
ArrayHeap (Priority Queue)MatrixGraph

Prompt

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] <= 109

Approaches

2 approaches with complexity analysis and trade-offs.

This approach attempts to solve the problem by exploring all possible paths from the start (0, 0) to the end (n-1, m-1) using a Depth-First Search (DFS). It's a straightforward recursive solution that tries every combination of moves. However, due to the vast number of paths in a grid, this method is computationally infeasible.

Algorithm

  1. Initialize a global variable min_time to a very large value.
  2. Define a recursive function, e.g., dfs(row, col, currentTime, moveCount, visited).
  3. The base case for the recursion is reaching the destination (n-1, m-1). Update min_time with currentTime if it's smaller.
  4. To avoid infinite loops, use a visited array. Mark the current cell as visited before exploring neighbors.
  5. For each valid, unvisited neighbor (nr, nc): a. Calculate the cost of the move based on moveCount + 1. It's 1 for an odd-numbered move and 2 for an even-numbered move. b. Calculate the arrival time at the neighbor: newTime = max(currentTime, moveTime[nr][nc]) + moveCost. c. Make a recursive call: dfs(nr, nc, newTime, moveCount + 1, visited).
  6. Backtrack by unmarking the current cell from visited after exploring all its neighbors.
  7. Start the process by calling dfs(0, 0, 0, 0, new boolean[n][m]).

Walkthrough

The brute-force approach uses a recursive function to explore every possible path. The state of the recursion includes the current coordinates (r, c), the time elapsed t, and the number of moves made m.

Starting from (0, 0) at time 0 with 0 moves, the function explores all four adjacent cells. For each neighbor, it calculates the time of arrival. This depends on the current time, the moveTime of the neighbor cell, and the cost of the current move (1 or 2 seconds, based on the move count). It then recursively calls itself for the neighbor.

This process continues until the destination is reached, at which point the total time is compared against a global minimum. While simple in concept, this method explores a number of paths that grows exponentially with the size of the grid, making it far too slow for the given constraints. Furthermore, correctly handling paths that revisit cells is complicated and adds to the inefficiency.

Complexity

Time

O(4^(N*M)). In the worst case, the algorithm explores a number of paths that is exponential in the number of cells in the grid.

Space

O(N * M) for the recursion stack depth in the worst case, where N and M are the dimensions of the grid.

Trade-offs

Pros

  • Conceptually simple and easy to understand as a first thought.

Cons

  • Extremely inefficient with exponential time complexity, leading to a 'Time Limit Exceeded' error for the given constraints.

  • A simple visited array is insufficient and incorrect. It prevents finding optimal paths that may need to revisit a cell. A correct brute-force would need to handle cycles without a simple visited array, making it even more complex and slower.

Solutions

class Solution {public  int minTimeToReach(int[][] moveTime) {    int n = moveTime.length;    int m = moveTime[0].length;    int[][] dist = new int[n][m];    for (var row : dist) {      Arrays.fill(row, Integer.MAX_VALUE);    }    dist[0][0] = 0;    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b)->a[0] - b[0]);    pq.offer(new int[]{0, 0, 0});    int[] dirs = {-1, 0, 1, 0, -1};    while (true) {      int[] p = pq.poll();      int d = p[0], i = p[1], j = p[2];      if (i == n - 1 && j == m - 1) {        return d;      }      if (d > dist[i][j]) {        continue;      }      for (int k = 0; k < 4; k++) {        int x = i + dirs[k];        int y = j + dirs[k + 1];        if (x >= 0 && x < n && y >= 0 && y < m) {          int t = Math.max(moveTime[x][y], dist[i][j]) + (i + j) % 2 + 1;          if (dist[x][y] > t) {            dist[x][y] = t;            pq.offer(new int[]{t, x, y});          }        }      }    }  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem