Find Minimum Time to Reach Last Room I - Practice Coding Problems

Find Minimum Time to Reach Last Room I - Problem

Array Graph Heap (Priority Queue) Matrix Shortest Path Medium

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 after which the room opens and can be moved to.

You start from the room (0, 0) at time t = 0 and can move to an adjacent room. Moving between adjacent rooms takes exactly one second.

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.

Input & Output

Example 1 — Basic Grid

$ Input: moveTime = [[0,1,1],[1,1,1]]

› Output: 3

💡 Note: Start at (0,0) at time 0 → move to (0,1) at time 1 → move to (1,1) at time 3 (wait until room opens). Total time: 3 seconds.

Example 2 — Blocked Path

$ Input: moveTime = [[0,2,99],[1,1,1]]

› Output: 5

💡 Note: Path: (0,0) t=0 → (1,0) t=1 → (1,1) t=2 → (0,1) t=3 (wait) → (1,1) t=5. Need to alternate to reach time 2 for (0,1).

Example 3 — Simple Path

$ Input: moveTime = [[0,1],[2,3]]

› Output: 3

💡 Note: Direct path: (0,0) t=0 → (0,1) t=1 → (1,1) t=3 (wait for room to open at time 3). Total: 3 seconds.

Constraints

2 ≤ n, m ≤ 750
n == moveTime.length
m == moveTime[i].length
0 ≤ moveTime[i][j] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input Grid

2D array where each cell has minimum opening time

Path Finding

Find shortest time path considering wait periods

Output Time

Minimum time to reach bottom-right corner

Key Takeaway

🎯 Key Insight: Use Dijkstra's algorithm to handle time constraints and waiting periods efficiently

Asked in

G Google 15 a Amazon 12 f Meta 8 Apple 6

The key insight is that this is a shortest path problem where we may need to wait at cells. If we arrive early, we must wait until the room opens, and if the wait time has wrong parity, we need one extra second. Dijkstra's algorithm efficiently finds the minimum time path. Time: O(n×m×log(n×m)), Space: O(n×m).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force DFS	O(4^(n×m))	O(n×m)	Explore all possible paths using depth-first search
Dijkstra's Algorithm	O(n×m×log(n×m))	O(n×m)	Use priority queue to explore shortest time path first

Brute Force DFS — Algorithm Steps

Start DFS from (0,0) with time = 0
For each adjacent room, calculate arrival time
If arrival time < moveTime[i][j], wait until room opens
Recursively explore all paths and track minimum

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Begin DFS from (0,0) at time 0

Explore

Try all 4 directions, wait if room not open

Backtrack

Return and try other paths, track minimum

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int minTime = INT_MAX;
int n, m;

void dfs(int** moveTime, int x, int y, int time, int** visited) {
    if (x == n - 1 && y == m - 1) {
        if (time < minTime) minTime = time;
        return;
    }
    
    int dx[] = {0, 1, 0, -1};
    int dy[] = {1, 0, -1, 0};
    
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny]) {
            int waitTime = (time + 1 > moveTime[nx][ny]) ? time + 1 : moveTime[nx][ny];
            if ((moveTime[nx][ny] - time - 1) % 2 == 1) {
                waitTime++;
            }
            visited[nx][ny] = 1;
            dfs(moveTime, nx, ny, waitTime, visited);
            visited[nx][ny] = 0;
        }
    }
}

int solution(int** moveTime, int rows, int cols) {
    n = rows; m = cols;
    minTime = INT_MAX;
    int** visited = (int**)calloc(n, sizeof(int*));
    for (int i = 0; i < n; i++) {
        visited[i] = (int*)calloc(m, sizeof(int));
    }
    visited[0][0] = 1;
    dfs(moveTime, 0, 0, 0, visited);
    for (int i = 0; i < n; i++) {
        free(visited[i]);
    }
    free(visited);
    return minTime;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    int** moveTime = (int**)malloc(100 * sizeof(int*));
    int rows = 0, cols = 0;
    printf("%d\n", solution(moveTime, rows, cols));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(4^(n×m))

Each cell has up to 4 directions, creating exponential branching

✓ Linear Growth

Space Complexity

O(n×m)

Recursion stack depth limited by grid size

⚡ Linearithmic Space

12.5K Views

Medium Frequency

~25 min Avg. Time

234 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force DFS — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler