Leet code problem 1631: – Path with Minimum Effort

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., 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.

Flow Diagram: –

Solution: –

private int[] d = {0, 1, 0, -1, 0};
    public int minimumEffortPath(int[][] heights) {
        int m = heights.length, n = heights[0].length;
        int[][] efforts = new int[m][n];
        for (int[] e : efforts) {
            Arrays.fill(e, Integer.MAX_VALUE);
        }
        efforts[0][0] = 0;
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[3]);
        while (!q.isEmpty()) {
            int[] cur = q.poll();




            int effort = cur[0], x = cur[1], y = cur[2];
            for (int k = 0; k < 4; ++k) {
                int r = x + d[k], c = y + d[k + 1];
                if (0 <= r && r < m && 0 <= c && c < n && efforts[r][c] > Math.max(effort, Math.abs(heights[r][c] - heights[x][y]))) {
                    int nextEffort = Math.max(effort, Math.abs(heights[r][c] - heights[x][y]));
                    efforts[r][c] = nextEffort;
                    q.offer(new int[]{nextEffort, r, c});
                }
            }
        }
        return efforts[m - 1][n - 1];
    }