Ques : 1631 (Path with Minimum Effort)

Ques : 1631
Path with Minimum Effort
Problem Statement : Given is a 2-D matrix we have to find the path which has the least max difference amongst all the paths while moving through it's cells an reaching the target.
Let's look at the follow example :
[1  2  2]
[3  8  2]
[5  3  5]

There are various paths to reach target(2,2) from src(0,0) which are :
1->2->2->2->5    => difference in each step is :{1,0,0,3} => max diff : 3
1->3->5->3->5    => difference in each step is :{2,2,2,2} => max diff : 2
1->3->8->3->5    => difference in each step is :{2,5,5,2} => max diff : 5
1->2->8->3->5    => difference in each step is :{1,6,5,2} => max diff : 6
...
...
...
hence the least difference will be : 2 amongst all the paths so taken which is the expected output.

Observation :
1) The Path has to be traversed which means Djiktra's algo can be applied.
2) We have to reach target cell from src through path which has max difference least as compared to other paths.
3) Which means we have to maintain max difference throughout that path => Math.max(prevdiff,newdiff) for storing in queue while bfs.
4) the max difference will be compared at the end of path , end of path is reaching target if we substitute the max diff so found on target cell and check          for other paths whether that diff is less than the new diff of the path computated using Djiktra's condition
    if(nexdiff < diff at the cell)
       {
          ndiff at the cell=nextdiff;
           add in queue
       }

 

Dry Running our observation :
Queue will contain elements inside with ( row , col , diff as of now on it's cell) : Dist 2d matrix will keep updating
The following matrix is considered : 
[1  2  2]
[3  8  2]
[5  3  5]


i)(0,0,0) 
[0  ∞  ∞]
[∞  ∞  ∞]
[∞  ∞  ∞]

ii)(0,1,1),(1,0,2)
[0  1 ∞]
[2  ∞ ∞]
[∞ ∞ ∞]

iii)(0,2,0),(1,0,2),(1,1,6)
[0  1  2]
[2  6  ∞]
[∞  ∞ ∞]

iv)(1,2,0),(1,0,2),(1,1,6)
[0  1  2]
[2  6  2]
[∞ ∞ ∞]

v)(1,0,2),(2,2,3),(1,1,6)
[0  1  2]
[2  6  2]
[∞  ∞ 3]

vi)(2,0,2),(2,2,3),(1,1,5),(1,1,6)
[0  1  2]
[2  5  2]
[2  ∞ 3]

vii)(2,1,2),(2,2,3),(1,1,5),(1,1,6)
[0  1  2]
[2  5  2]
[2  2  3]

viii)(2,2,2),(2,2,3),(1,1,5),(1,1,6)
[0  1  2]
[2  5  2]
[2  2  2]

next as the r=n-1 and c=n-1
return dist.
So our dry run is providing us with the necessary output 

Approach :
1. Data Structures:
PriorityQueue : A min-heap priority queue is used to always process the cell with the smallest effort(dist) first. Queue is implemented using the Comparable  which compares and sorts .
Distance Array (dist): This keeps track of the minimum effort required to reach each cell from the start.
Visited Array (vis): This boolean array marks cells that have already been processed.

2. Initialization:
Initialize the dist array with Integer.MAX_VALUE to represent initially unknown distances.
Set the distance to the start cell (0, 0) to 0 as no effort is needed to start at the starting cell.
Add the starting cell to the priority queue with an effort of 0.

3. Dijkstra’s Algorithm:
Continuously extract the cell with the smallest effort from the priority queue.
For the current cell, explore its neighboring cells (up, down, left, right).
For each neighbor:
Compute the effort to reach this neighbor, which is the maximum of the current effort and the absolute height difference between the current cell and the neighbor.
If this new effort is less than the recorded effort in the dist array for the neighbor, update the dist array and add the neighbor to the priority queue.

4. Termination:
The algorithm stops when the target cell (row-1, col-1) is reached, returning the minimum effort required to get there.
Detailed Steps:

Code analysis :
1)Define Truple Class:

Represents a cell with row, column, and effort.
Implements Comparable to ensure cells are ordered by effort in the priority queue.

2)Initialize Data Structures:

Create dist array and set all values to Integer.MAX_VALUE.
Create vis array and initialize all values to false.
Set the starting cell's effort to 0 in the dist array and add it to the priority queue.

3)Process the Priority Queue:

Extract the cell with the smallest effort.
Skip the cell if it has been visited already.
Mark the cell as visited.
Check if the target cell is reached; if so, return the current effort.

4)Explore all valid neighbors:
Compute the effort to reach each neighbor.
Update the dist array if the new effort is smaller than the recorded effort.
Add the neighbor to the priority queue with the updated effort.

5)Return the Result:

If the target cell is reached, return the recorded effort in the dist array for the target cell.
Otherwise, if the loop ends without reaching the target, return the effort value stored in dist for the target cell (though this would typically mean the target is unreachable).

Code : 
import java.util.PriorityQueue;

class Solution {
    class Truple implements Comparable<Truple>{
        int r;
        int c;
        int d;

        Truple(int row, int col, int diff) {
            this.r = row;
            this.c = col;
            this.d = diff;
        }

        @Override
        public int compareTo(Truple o) {
            return this.d - o.d;
        }
    }

    public int minimumEffortPath(int[][] heights) {
        int row = heights.length;
        int col = heights[0].length;
        int[][] dist = new int[row][col];
        boolean[][] vis = new boolean[row][col];
        PriorityQueue<Truple> pq = new PriorityQueue<>();

       
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                dist[i][j] = Integer.MAX_VALUE;
            }
        }
        dist[0][0] = 0;

        pq.add(new Truple(0, 0, 0));
        int[] dr = {-1, 0, 1, 0};
        int[] dc = {0, 1, 0, -1};

        while (!pq.isEmpty()) {
            Truple curr = pq.poll();
            int currrow = curr.r;
            int currcol = curr.c;
            int currdist = curr.d;

            if (vis[currrow][currcol]) continue;
            vis[currrow][currcol] = true;

          
            if (currrow == row - 1 && currcol == col - 1) {
                return currdist;
            }

            for (int i = 0; i < 4; i++) {
                int nextrow = currrow + dr[i];
                int nextcol = currcol + dc[i];
                if (nextrow >= 0 && nextcol >= 0 && nextrow < row && nextcol < col && !vis[nextrow][nextcol]) 
                {
                    int nextEffort = Math.max(currdist, Math.abs(heights[nextrow][nextcol] - heights[currrow][currcol]));
                    if (nextEffort < dist[nextrow][nextcol]) 
                    {
                        dist[nextrow][nextcol] = nextEffort;
                        pq.add(new Truple(nextrow, nextcol, nextEffort));
                    }
                }
            }
        }
        return dist[row - 1][col - 1];
    }
}

~ Time Complexity (TC)
The time complexity is 𝑂(𝑁log⁡𝑁), where N is the total number of cells in the grid, because each cell is processed once.

~ Space Complexity (SC)
The space complexity is O(N) due to the storage required for the dist, vis, and priority queue, which all have space proportional to the number of cells.