Path with minimum effort

XXX. Minimum Effort Path

Dijkstra's Algorithm

Priority Queue

Graph

Problem Statement:

Given a 2D grid heights representing the height of each cell, the effort of a path is defined as the maximum absolute difference between the heights of adjacent cells in the path. The task is to find the minimum effort required to travel from the top-left corner to the bottom-right corner of the grid.

Algorithm:

1. Use Dijkstra's Algorithm:

   Utilize a priority queue to always process the path with the minimum effort first. This ensures we find the shortest path to the destination efficiently.

2. Maintain a Distance Array:

   Use a 2D array dist to track the minimum effort required to reach each cell. Initialize all distances to infinity except for the starting cell.

3. Iterate Over Neighbors:

   For each cell, calculate the effort to its neighbors and update the distance if the new effort is smaller. Push the updated neighbor into the priority queue for further processing.

4. Terminate on Reaching the Target:

   Stop the algorithm as soon as the bottom-right cell is processed, as the shortest path to it has been found.

Complexity:

Time Complexity: O(m * n * log(m * n)), where m is the number of rows and n is the number of columns. The priority queue operations dominate the complexity.
Space Complexity: O(m * n), for the distance array and the priority queue.

Java Implementation:

class Solution {
    int[] DIR = new int[]{0, 1, 0, -1, 0};

    public int minimumEffortPath(int[][] heights) {
        int m = heights.length, n = heights[0].length;

        // Step 1: Initialize the distance array with maximum values
        int[][] dist = new int[m][n];
        for (int i = 0; i < m; i++) 
            Arrays.fill(dist[i], Integer.MAX_VALUE);

        // Step 2: Priority queue to process the minimum effort path first
        PriorityQueue minHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        minHeap.offer(new int[]{0, 0, 0}); // {effort, row, col}
        dist[0][0] = 0;

        // Step 3: Process the grid using Dijkstra's algorithm
        while (!minHeap.isEmpty()) {
            int[] top = minHeap.poll();
            int d = top[0], i = top[1], j = top[2];

            // If the effort is outdated, skip this iteration
            if (d > dist[i][j]) continue;

            // If we've reached the target cell, return the effort
            if (i == m - 1 && j == n - 1) return d;

            // Step 4: Iterate over all valid neighbors
            for (int k = 0; k < 4; k++) {
                int ni = i + DIR[k], nj = j + DIR[k + 1];
                if (ni >= 0 && ni < m && nj >= 0 && nj < n) {
                    // Calculate the effort to the neighbor
                    int newDist = Math.max(d, Math.abs(heights[ni][nj] - heights[i][j]));
                    // Update distance if a better effort is found
                    if (dist[ni][nj] > newDist) {
                        dist[ni][nj] = newDist;
                        minHeap.offer(new int[]{dist[ni][nj], ni, nj});
                    }
                }
            }
        }

        return 0; // Default return, should not be reached
    }
}