Minimum Time to Visit a Cell In a Grid - Practice Coding Problems

Minimum Time to Visit a Cell In a Grid - Problem

Array Breadth-First Search Graph Heap (Priority Queue) Matrix Shortest Path Hard

You are given an m x n matrix grid consisting of non-negative integers where grid[row][col] represents the minimum time required to be able to visit the cell (row, col), which means you can visit the cell (row, col) only when the time you visit it is greater than or equal to grid[row][col].

You are standing in the top-left cell of the matrix in the 0th second, and you must move to any adjacent cell in the four directions: up, down, left, and right. Each move you make takes 1 second.

Return the minimum time required in which you can visit the bottom-right cell of the matrix. If you cannot visit the bottom-right cell, then return -1.

Input & Output

Example 1 — Basic Grid Navigation

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

› Output: 3

💡 Note: Start at (0,0) at time 0, move right to (0,1) at time 1, then down to (1,1) at time 3 (wait until time ≥3), finally right to (1,2) at time 3. Total time: 3.

Example 2 — Impossible Case

$ Input: grid = [[0,2],[2,2]]

› Output: -1

💡 Note: Both adjacent cells (0,1) and (1,0) require time ≥2 to enter, but we can only reach them at time 1. Since we can't move anywhere from start, return -1.

Example 3 — Waiting Strategy

$ Input: grid = [[0,0,0],[0,0,5],[0,0,0]]

› Output: 5

💡 Note: We can reach (1,2) by going around: (0,0) → (0,1) → (0,2) → (1,2), arriving at time 3, but cell requires time ≥5. We can wait by moving back and forth until time 5.

Constraints

m == grid.length
n == grid[i].length
2 ≤ m, n ≤ 1000
0 ≤ grid[i][j] ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input Grid

Each cell shows minimum time required to enter

Path Finding

Find route from top-left to bottom-right

Time Calculation

Account for waiting periods and movement time

Key Takeaway

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

Asked in

G Google 45 A Amazon 38 M Meta 32 M Microsoft 28

The key insight is treating this as a shortest path problem where we can "wait" by moving back and forth between cells. Use Dijkstra's algorithm with a priority queue to find the minimum time path. Time: O(m×n×log(m×n)), Space: O(m×n)

Common Approaches

Approach	Time	Space	Notes
✓ Dijkstra's Algorithm with Priority Queue	O(m×n×log(m×n))	O(m×n)	Use shortest path algorithm with time-based priority queue
DFS with All Paths	O(4^(m×n))	O(m×n)	Try every possible path using depth-first search

Dijkstra's Algorithm with Priority Queue — Algorithm Steps

Start with (0,0) at time 0 in priority queue
Process cells in order of minimum time
For each neighbor, calculate arrival time including wait periods
Use back-and-forth movement to handle time constraints

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Start with (0,0) at time 0 in priority queue

Process Minimum

Always process cell with earliest arrival time

Calculate Wait

For each neighbor, calculate wait time if needed

Code -

solution.c — C

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

typedef struct {
    int time, row, col;
} State;

typedef struct {
    State* heap;
    int size;
    int capacity;
} PriorityQueue;

PriorityQueue* createPQ(int capacity) {
    PriorityQueue* pq = (PriorityQueue*)malloc(sizeof(PriorityQueue));
    pq->heap = (State*)malloc(capacity * sizeof(State));
    pq->size = 0;
    pq->capacity = capacity;
    return pq;
}

void swap(State* a, State* b) {
    State temp = *a;
    *a = *b;
    *b = temp;
}

void minHeapify(PriorityQueue* pq, int idx) {
    int smallest = idx;
    int left = 2 * idx + 1;
    int right = 2 * idx + 2;
    
    if (left < pq->size && pq->heap[left].time < pq->heap[smallest].time)
        smallest = left;
    
    if (right < pq->size && pq->heap[right].time < pq->heap[smallest].time)
        smallest = right;
    
    if (smallest != idx) {
        swap(&pq->heap[idx], &pq->heap[smallest]);
        minHeapify(pq, smallest);
    }
}

void push(PriorityQueue* pq, State state) {
    if (pq->size >= pq->capacity) return;
    
    int i = pq->size++;
    pq->heap[i] = state;
    
    while (i != 0 && pq->heap[(i-1)/2].time > pq->heap[i].time) {
        swap(&pq->heap[i], &pq->heap[(i-1)/2]);
        i = (i-1)/2;
    }
}

State pop(PriorityQueue* pq) {
    if (pq->size <= 0) {
        State empty = {INT_MAX, -1, -1};
        return empty;
    }
    
    State root = pq->heap[0];
    pq->heap[0] = pq->heap[pq->size-1];
    pq->size--;
    minHeapify(pq, 0);
    
    return root;
}

int isEmpty(PriorityQueue* pq) {
    return pq->size == 0;
}

int solution(int** grid, int gridSize, int* gridColSize) {
    int m = gridSize, n = gridColSize[0];
    
    // Check if we can move initially
    if (grid[0][1] > 1 && grid[1][0] > 1) {
        return -1;
    }
    
    int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    PriorityQueue* pq = createPQ(m * n * 4);
    State start = {0, 0, 0};
    push(pq, start);
    
    int visited[100][100] = {0}; // Assuming max grid size 100x100
    
    while (!isEmpty(pq)) {
        State curr = pop(pq);
        
        if (visited[curr.row][curr.col]) {
            continue;
        }
        
        visited[curr.row][curr.col] = 1;
        
        if (curr.row == m - 1 && curr.col == n - 1) {
            free(pq->heap);
            free(pq);
            return curr.time;
        }
        
        for (int i = 0; i < 4; i++) {
            int nr = curr.row + directions[i][0];
            int nc = curr.col + directions[i][1];
            if (nr >= 0 && nr < m && nc >= 0 && nc < n && !visited[nr][nc]) {
                int waitTime = 0;
                if (grid[nr][nc] > curr.time + 1) {
                    waitTime = grid[nr][nc] - curr.time - 1;
                    if (waitTime % 2 == 1) {
                        waitTime += 1;
                    }
                }
                
                State next = {curr.time + 1 + waitTime, nr, nc};
                push(pq, next);
            }
        }
    }
    
    free(pq->heap);
    free(pq);
    return -1;
}

int main() {
    // Simple parsing for small test cases
    int m = 3, n = 3;
    int** grid = (int**)malloc(m * sizeof(int*));
    for (int i = 0; i < m; i++) {
        grid[i] = (int*)malloc(n * sizeof(int));
    }
    
    // Example input: [[0,1,1],[2,3,1],[2,3,1]]
    grid[0][0] = 0; grid[0][1] = 1; grid[0][2] = 1;
    grid[1][0] = 2; grid[1][1] = 3; grid[1][2] = 1;
    grid[2][0] = 2; grid[2][1] = 3; grid[2][2] = 1;
    
    int* gridColSize = (int*)malloc(m * sizeof(int));
    for (int i = 0; i < m; i++) {
        gridColSize[i] = n;
    }
    
    int result = solution(grid, m, gridColSize);
    printf("%d\n", result);
    
    for (int i = 0; i < m; i++) {
        free(grid[i]);
    }
    free(grid);
    free(gridColSize);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m×n×log(m×n))

Each cell processed once with priority queue operations taking O(log(m×n))

⚡ Linearithmic

Space Complexity

O(m×n)

Priority queue and visited array store up to m×n entries

⚡ Linearithmic Space

23.5K Views

Medium Frequency

~35 min Avg. Time

892 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

Dijkstra's Algorithm with Priority Queue — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler