Leetcode: Path with Minimum Effort
This question is asked at Google, Houzz, and ByteDance. Think about a hiker perpared for an upcoming hike. I am given heights, a 2D array of sizes rows x columns where the heights[row][col] represents the height at the index [row, col] and I am situated at the top-left cell and hope to travel to the bottom right cell.
A route's effort is the maximum absolute distance in heights between cells. heights[row][col] represents the height of a cell. Routes that are the same level do not require any effort.
We want to find the route with the minimum effort. We can either do Dijkstra's here or Union Find. Here's an example:
There are 3 solutions to this problem, and I will go over each of these solutions.
The first solution is brute for using backtracking, and this approach traverses all possible paths from the source cell to the destination cell, and the first thing is backtracking that incrementally builds the candidates using depth-first search, discarding the candidates that don't satisfy the condition, and has the following steps:
Choose a potential candidate, and there are 4 directions: up, down, left, right.
We define a constraint and this value needs to be within the matrix, and not visited before.
We define the goal once we find the desired solution, and we can see the maxSoFar, and if we found a path with maxSoFar, we only explore other paths that take less effort than the maxSoFar path. }
We start going from the source cell. For a given cell, explore the adjacent cells in all the 4 directions. The maxdifference means the maximum difference between current path and absolute path, and we must backtrack and return the maximum absolute destination of the current path.
We calculate the minimum effort recursively for each cell as a result.
Here's the solution:
class Solution {
public int minimumEffortPath(int[][] heights) {
//return the backtracking function.
return backtrack(0, 0, heights, heights.length; heights[0].length, 0);
}
int directions[][] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int maxSoFar = Integer.MAX_VALUE;
int backtrack(int x, int y, int[][] heights, int row, int col, int maxDifference) {
if(x == row - 1 && y == col - 1){
//check if we have reached the end of the path.
maxSoFar = Math.min(maxSoFar, maxDifference);
return maxDifference;
}
int currentHeight = heights[x][y].
heights[x][y] = 0;
int minEffort = Integer.MAX_VALUE;
for(int i = 0; i < 4; i++) {
//look into adjacent cells
int adjacentX = x + directions[i][0];
int adjacentY = y + directions[i][1];
//if the cell is adjacent
if(isValidCell(adjacentX, adjacentY, row, col) && heights[adjacentX][adjacentY] != 0) {
//see current difference compare it to maximum difference
int currentDifference = Math.abs(heights[adjacentX][adjacentY] - currentHeight);
//find maximum difference
int maxCurrentDifference = Math.max(maxDifference, currentDifference);
if(maxCurrentDifference < maxSoFar) {
//backtrack and return the minimum effort.
int result = backtrack(adjacentX, adjacentY, heights, row, col, maxCurrentDifference);
minEffort = Math.min(minEffort, result);
}
}
}
//return the current height to "mark" as visited.
heights[x][y] = currentHeight;
return minEffort;
}
boolean isValidCell(int x, int y, int row, int col) {
//return whether things are in the correct bonds.
return x >= 0 && x <= row - 1 && y >= 0 && y <= col - 1;
}
}
We find maximum difference path, backtrack until we reach the peak, and then return the minimum of those differences.
The second way we can do this is to use variations of Dijkstra's Algorithm. The previous approach traverses all the paths. But this is inefficient.
We first initialize a matrix, called DifferenceMatrix of size row * col where each cell represents the minimum effort required to reach a certain cell out of all the possible paths. As we start visiting each cell, all the adjacent cells are now reachable. We can figure out the absolute difference, and update it and push all adjacent cells in the priority queue, that holds all the cells sorted by its value in a differenceMatrix. We begin adding the source cell in the queue, and until we visited the destination cell or the queue or the queue is not empty we visit each cell queue in the order of priority.
Here's an example, with difference matrix and the priority queue putting a data structure of a location and difference.
class Solution {
//representative of all 4 directions that are to be traversed.
int directions[][] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public int minimumEffortPath(int[][] heights) {
int row = heights.length;
int col = heights[0].length;
int[][] differenceMatrix = new int[row][col];
//fill the difference matrix with infinite values.
for (int[] eachRow : differenceMatrix)
Arrays.fill(eachRow, Integer.MAX_VALUE);
differenceMatrix[0][0] = 0;
PriorityQueue<Cell> queue = new PriorityQueue<Cell>((a, b) -> (a.difference.compareTo(b.difference)));
boolean[][] visited = new boolean[row][col];
queue.add(new Cell(0, 0, differenceMatrix[0][0]));
//dequeue the cell and perform the algorithm on its neighbors.
while (!queue.isEmpty()) {
//Dijkstra's algorithm, take the minimum value of the queue
Cell curr = queue.poll();
//mark node as visited
visited[curr.x][curr.y] = true;
//minimum difference now,
if (curr.x == row - 1 && curr.y == col - 1)
return curr.difference;
for (int[] direction : directions) {
//the current direction adjactent
int adjacentX = curr.x + direction[0];
int adjacentY = curr.y + direction[1];
//if something is valid and not visited yet
if (isValidCell(adjacentX, adjacentY, row, col) && !visited[adjacentX][adjacentY]) {
//sees the current distance aka difference between the nodes
int currentDifference = Math.abs(heights[adjacentX][adjacentY] - heights[curr.x][curr.y]);
//find the maximum difference in the path.
int maxDifference = Math.max(currentDifference, differenceMatrix[curr.x][curr.y]);
if (differenceMatrix[adjacentX][adjacentY] > maxDifference) {
differenceMatrix[adjacentX][adjacentY] = maxDifference;
//add a cell with the adjacent cell and the difference. use this to pop
queue.add(new Cell(adjacentX, adjacentY, maxDifference));
}
}
}
}
return differenceMatrix[row - 1][col - 1];
}
boolean isValidCell(int x, int y, int row, int col) {
return x >= 0 && x <= row - 1 && y >= 0 && y <= col - 1;
}
}
//cell: data structure to be used in the queue
class Cell {
int x;
int y;
Integer difference;
Cell(int x, int y, Integer difference) {
this.x = x;
this.y = y;
this.difference = difference;
}
}
The last method we want to go over here is the Union Find.
Using a Disjoint set is another intuitive way to solve the problem. Each cell in a matrix is a single component in the graph. Every cell is a disconnected component and we aim to form a single connected cell that connects the source cell to the destination cell. There are 2 operations
Find(x): returns the parent of the operation.
Union(x, y): merges 2 disconnected components.
Initially each cell is disconnected so we initialize each cell as a parent of itself and we flatten a 2D matrix into a 1D matrix. We can also build an edgeList which consists of the absolute difference between every adjacent cell in the matrix, and sort the corresponding edge list. We start iterating through edge list and connect each edge to form connected component using the union find algorithm. We check if the source cell and the destination cell are connected if yes, the absolute difference between the current edge is the result.
Here's the code:
class Solution {
public int minimumEffortPath(int[][] heights) {
int row = heights.length;
int col = heights[0].length;
if (row == 1 && col == 1) return 0;
UnionFind unionFind = new UnionFind(heights);
List<Edge> edgeList = unionFind.edgeList;
//sort by the list by distance
Collections.sort(edgeList, (e1, e2) -> e1.difference - e2.difference);
for (int i = 0; i < edgeList.size(); i++) {
int x = edgeList.get(i).x;
int y = edgeList.get(i).y;
//union both of these together
unionFind.union(x, y);
//we see if the union find parents are the same, and then return max difference
if (unionFind.find(0) == unionFind.find(row * col - 1)) return edgeList.get(i).difference;
}
return -1;
}
}
//Union Find class
class UnionFind {
//parent, rank, and edge list.
int[] parent;
int[] rank;
List<Edge> edgeList;
//spread the cells out into the matrix.
public UnionFind(int[][] heights) {
int row = heights.length;
int col = heights[0].length;
parent = new int[row * col];
edgeList = new ArrayList<>();
rank = new int[row * col];
for (int currentRow = 0; currentRow < row; currentRow++) {
for (int currentCol = 0; currentCol < col; currentCol++) {
if (currentRow > 0) {
edgeList.add(new Edge(currentRow * col + currentCol,
(currentRow - 1) * col + currentCol,
Math.abs(heights[currentRow][currentCol] - heights[currentRow - 1][currentCol]))
);
}
if (currentCol > 0) {
edgeList.add(new Edge(currentRow * col + currentCol,
currentRow * col + currentCol - 1,
Math.abs(heights[currentRow][currentCol] - heights[currentRow][currentCol - 1]))
);
}
parent[currentRow * col + currentCol] = currentRow * col + currentCol;
}
}
}
//find a parent of a certain index.
int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
//union 2 array containers together for ranks
void union(int x, int y) {
int parentX = find(x);
int parentY = find(y);
if (parentX != parentY) {
if (rank[parentX] > rank[parentY]) parent[parentY] = parentX;
else if (rank[parentX] < rank[parentY]) parent[parentX] = parentY;
else {
parent[parentY] = parentX;
rank[parentX] += 1;
}
}
}
}
//have an edge and the difference
class Edge {
int x;
int y;
int difference;
Edge(int x, int y, int difference) {
this.x = x;
this.y = y;
this.difference = difference;
}
}
and the time complexity is n^2 log(n^2) with the space complexity of O(mn). We figure out the absolute difference between each of the cells:
Comments
Post a Comment