You are a hiker preparing for an upcoming hike. You are given heights, a 2D array of size rows x columns, where heights[row][col] represents the height of cell (row, col). You are situated in the top-left cell, (0, 0), and you hope to travel to the bottom-right cell, (rows-1, columns-1) (i.e.,&nbsp;0-indexed). You can move up, down, left, or right, and you wish to find a route that requires the minimum effort.

A route's effort is the maximum absolute difference in heights between two consecutive cells of the route.

Return the minimum effort required to travel from the top-left cell to the bottom-right cell.

&nbsp;
Example 1:



Input: heights = [[1,2,2],[3,8,2],[5,3,5]]
Output: 2
Explanation: The route of [1,3,5,3,5] has a maximum absolute difference of 2 in consecutive cells.
This is better than the route of [1,2,2,2,5], where the maximum absolute difference is 3.


Example 2:



Input: heights = [[1,2,3],[3,8,4],[5,3,5]]
Output: 1
Explanation: The route of [1,2,3,4,5] has a maximum absolute difference of 1 in consecutive cells, which is better than route [1,3,5,3,5].


Example 3:

Input: heights = [[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]]
Output: 0
Explanation: This route does not require any effort.


&nbsp;
Constraints:


	rows == heights.length
	columns == heights[i].length
	1 &lt;= rows, columns &lt;= 100
	1 &lt;= heights[i][j] &lt;= 106

class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        di = (0, 1, 0, -1)
        dj = (1, 0, -1, 0)
        m, n = len(heights), len(heights[0])
        visited = [[False] * n for _ in range(m)]
        h = [(0, 0, 0)]
        while h:
            effort, i, j = heappop(h)
            if visited[i][j]:
                continue
            visited[i][j] = True
            if i + 1 == m and j + 1 == n:
                return effort ## have reached the (m-1, n-1) cell
            for k in range(4):
                ii, jj = i + di[k], j + dj[k]
                if 0 <= ii < m and 0 <= jj < n and not visited[ii][jj]:
                    neffort = max(effort, abs(heights[i][j] - heights[ii][jj]))
                    heappush(h, (neffort, ii, jj))
        return ## cell (m-1, n-1) not reachable, should never happen
class Tuple {

    int distance;

    int row;

    int col;

    

    Tuple(int distance, int row, int col) {

        this.distance = distance;

        this.row = row;

        this.col = col;

    }

}



class Solution {

    public int minimumEffortPath(int[][] heights) {

        // Create a min heap based on the distance

        PriorityQueue<Tuple> minHeap = new PriorityQueue<>((x, y) -> x.distance - y.distance);

        

        int rows = heights.length;

        int cols = heights[0].length;

        

        // Create a 2D array to store the minimum effort to reach each cell

        int effort[][] = new int[rows][cols];

        

        // Initialize all efforts to maximum initially

        for (int i = 0; i < rows; i++) {

            Arrays.fill(effort[i], Integer.MAX_VALUE);

        }

        

        effort[0][0] = 0; // Initial effort at the starting cell

        

        // Add the starting cell to the min heap

        minHeap.add(new Tuple(0, 0, 0));

        

        // Arrays to represent row and column changes for 4 directions

        int dr[] = {-1, 0, 1, 0}; // Up, Right, Down, Left

        int dc[] = {0, 1, 0, -1};

        

        while (!minHeap.isEmpty()) {

            Tuple current = minHeap.poll(); // Get the cell with the minimum effort

            int distance = current.distance;

            int row = current.row;

            int col = current.col;

            

            if (row == rows - 1 && col == cols - 1) {

                return distance; // If reached the destination, return the effort

            }

            

            // Explore each of the 4 possible directions

            for (int i = 0; i < 4; i++) {

                int newRow = row + dr[i]; // Calculate new row index

                int newCol = col + dc[i]; // Calculate new column index

                

                // Check if the new cell is within bounds

                if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols) {

                    

                    // Calculate the new effort based on the maximum of height difference and current effort

                    int newEffort = Math.max(Math.abs(heights[row][col] - heights[newRow][newCol]), distance);

                    

                    // If the new effort is less than the stored effort for the cell, update and add to heap

                    if (newEffort < effort[newRow][newCol]) {

                        effort[newRow][newCol] = newEffort;

                        minHeap.add(new Tuple(newEffort, newRow, newCol)); // Add to heap for further exploration

                    }

                }

            }

        }

        return 0; // This value should be replaced with the actual minimum effort

    }

}
#define pii pair<int, pair<int,int>>

class Solution {
public:
    //Directions (top, right, bottom, left)
    const int d4x[4] = {-1,0,1,0}, d4y[4] = {0,1,0,-1};
    
    int minimumEffortPath(vector<vector<int>>& h) {
        int n = h.size(), m = h[0].size();
        //min-heap
        priority_queue <pii, vector<pii>, greater<pii>> pq;
        //to store distances from (0,0)
        vector<vector<int>> dis(n, vector<int>(m, INT_MAX));
        dis[0][0] = 0;
        pq.push({0, {0, 0}});
        
        //Dijstra algorithm
        while(!pq.empty()) {
            pii curr = pq.top(); pq.pop();
            int d = curr.first, r = curr.second.first, c = curr.second.second;
            // bottom right position
            if(r==n-1 && c==m-1) return d;
            for(int i=0; i<4; ++i) {
                int nx = r + d4x[i], ny = c + d4y[i];
                //check if new position is invalid
                if(nx < 0 || nx >= n || ny < 0 || ny >= m)continue;
				//nd => new distance: which is max of distance till now(d) and curr distance (difference between heights of current cells)
                int nd = max(d, abs(h[nx][ny] - h[r][c]));
                if (nd < dis[nx][ny]) {
                    dis[nx][ny] = nd;
                    pq.push({nd, {nx, ny}});
                }
            }
        }
        return 0;
        //please upvote
    }
};
/**
 * @param {number[][]} heights
 * @return {number}
 * T: O((M*N)log(M*N))
 * S: O(M*N)
 */
var minimumEffortPath = function(heights) {
    const directions = [
        [1, 0],
        [0, 1],
        [-1, 0],
        [0, -1],
    ];
    const row = heights.length;
    const col = heights[0].length;
    const differences = [];
    for (let i = 0; i < row; i++) {
        for (let j = 0; j < col; j++) {
            if (!differences[i]) {
                differences[i] = [Infinity];
            } else {
                differences[i].push(Infinity);
            }
        }
    }
    differences[0][0] = 0;
    const pq = new PriorityQueue();
    pq.push([0, 0], 0);
    while (pq.data.length > 0) {
        const node = pq.shift();
        const difference = node.priority;
        const [x, y] = node.val;
        directions.forEach(([dx, dy]) => {
            const newX = x + dx;
            const newY = y + dy;
            if (newX >= 0 && newX < row && newY >= 0 && newY < col) {
                const currentDiff = Math.abs(heights[newX][newY] - heights[x][y]);
                const maxDiff = Math.max(currentDiff, differences[x][y]);
                if (differences[newX][newY] > maxDiff) {
                    differences[newX][newY] = maxDiff;
                    pq.push([newX, newY], maxDiff);
                }
            }
        });
    }
    return differences[row - 1][col - 1];
};

const swap = (arr, i, j) => {
    const temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
};

function Node(val, priority) {
    this.val = val;
    this.priority = priority;
}

function PriorityQueue() {
    this.data = [];
}

PriorityQueue.prototype.push = function push(val, priority) {
    const node = new Node(val, priority);
    this.data.push(node);
    let index = this.data.length - 1;
    while (index > 0) {
        const parentIndex = Math.floor((index - 1) / 2);
        const parent = this.data[parentIndex];
        if (parent.priority > node.priority) {
            swap(this.data, parentIndex, index);
            index = parentIndex;
        } else {
            break;
        }
    }
};

PriorityQueue.prototype.shift = function shift() {
    const minNode = this.data[0] || {};
    const lastNode = this.data.pop();
    if (this.data.length < 1) {
        return minNode;
    }
    this.data[0] = lastNode;
    let index = 0;
    while (index < this.data.length) {
        const leftIndex = 2 * index + 1;
        const rightIndex = 2 * index + 2;
        const leftNode = this.data[leftIndex] || {};
        const rightNode = this.data[rightIndex] || {};
        let smallerIndex;
        if (leftNode.priority < lastNode.priority) {
            smallerIndex = leftIndex;
        }
        if (!smallerIndex && rightNode.priority < lastNode.priority) {
            smallerIndex = rightIndex;
        }
        if (smallerIndex && rightNode.priority < leftNode.priority) {
            smallerIndex = rightIndex;
        }
        if (!smallerIndex) {
            break;
        }
        swap(this.data, index, smallerIndex);
        index = smallerIndex;
    }
    return minNode;
};
Path With Minimum Effort