3342. Find Minimum Time to Reach Last Room II

Array Graph Heap (Priority Queue)Shortest Path

Problem Overview

Grid shortest-path with Dijkstra.

Intuition

Grid shortest-path with Dijkstra. You can enter cell (x,y) only after time moveTime[x][y]. Moving to a neighbor costs 1 or 2 seconds depending on parity of (i+j). The answer is minimum arrival time at the bottom-right cell.

Algorithm

1Run Dijkstra from (0,0) with dist[0][0] = 0 in a min-heap.
2When relaxing edge to (x,y): newDist = max(moveTime[x][y], currentDist) + ((i+j) % 2 + 1).
3Skip stale heap entries. Return dist at destination when popped.
4Four-directional moves only; bounds check each neighbor.

Example Walkthrough

Input: moveTime grid with blocked early cells

1.Cannot enter a cell before its moveTime — wait is baked into max(...).
2.Parity of current cell toggles step cost between 1 and 2.

Output: Minimum seconds to reach last room

Common Pitfalls

•Use max(moveTime[neighbor], dist[u]) — not just dist[u] + edge.
•Edge weight depends on source cell parity (i+j), not destination.
•Dijkstra, not BFS, because weights vary.

3342.java

Java

import java.util.*;


class Solution {
    public int minTimeToReach(int[][] moveTime) {
        return dijkstra(moveTime, new Pair<>(0, 0),
                new Pair<>(moveTime.length - 1, moveTime[0].length - 1));
    }

    private int dijkstra(int[][] moveTime, Pair<Integer, Integer> src, Pair<Integer, Integer> dst) {
        final int[][] DIRS = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
        final int m = moveTime.length;
        final int n = moveTime[0].length;
        int[][] dist = new int[m][n];
        Arrays.stream(dist).forEach(A -> Arrays.fill(A, Integer.MAX_VALUE));

        dist[0][0] = 0;
        Queue<Pair<Integer, Pair<Integer, Integer>>> minHeap = new PriorityQueue<>(
                Comparator.comparingInt(Pair::getKey)) {
            {
                offer(new Pair<>(dist[0][0], src));
            } // (d, (ux, uy))
        };

        while (!minHeap.isEmpty()) {
            final int d = minHeap.peek().getKey();
            final Pair<Integer, Integer> u = minHeap.poll().getValue();
            if (u.equals(dst))
                return d;
            final int i = u.getKey();
            final int j = u.getValue();
            if (d > dist[i][j])
                continue;
            for (int[] dir : DIRS) {
                final int x = i + dir[0];
                final int y = j + dir[1];
                if (x < 0 || x == m || y < 0 || y == n)
                    continue;
                final int newDist = Math.max(moveTime[x][y], d) + ((i + j) % 2 + 1);
                if (newDist < dist[x][y]) {
                    dist[x][y] = newDist;
                    minHeap.offer(new Pair<>(newDist, new Pair<>(x, y)));
                }
            }
        }

        return -1;
    }
}

Was this solution helpful?