I have been busy with work, reading and experimenting. So far it has been an interesting and rewarding workweek. That said, I am glad that tomorrow is Friday. Due to the COVID-19 pandemic my wife and I do not have big plans for the weekend with the exception of going out for groceries. I assume that you might be in a similar situation.
I decided to tackle LeetCode problem 1631 Path With Minimum Effort. Sometimes I go for the best approach I can came up with. In this case I kind of stopped before implementing it. My first approach timed out as expected. We will discuss the details. My second approach was accepted with a reasonable time. I still want to get one more pass on it but I just do not have time to get that done now.
I decided to solve the problem in Java on a Windows 10 machine using the VSCode IDE. I also developed test scaffolding code in order to work (I should rather say have fun and learn) on my computer. As usual the test scaffolding is not part of the solution.
If interested in the problem I suggest you to read the requirements on LeetCode. Then give it a try. If you get stuck, after spending a reasonable amount of time, start reading about my approach. As soon as you get inspired, stop reading and complete your solution. That is the only way to learn.
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. Constraints: rows == heights.length columns == heights[i].length 1 <= rows, columns <= 100 1 <= heights[i][j] <= 1000000
I like the description of the problem. The example is pretty good. In a nutshell you are in a location and want to get to a specific point. You wish to travel the route that demands the least amount of effort. That seems to describe a 
problem traversing a graph, tree or in this case two dimensional array evaluating costs expressed as effort (climbing or descending).
Take note on the range for heights. Addressing that aspect seems to be important for solving the problem with a short runtime.
This reminds me about descending. Last year my wife and I were vacationing in Lisbon, Portugal. We woke up early because we wanted to get some 
sightseeing done before having lunch at a very well known restaurant Cervejaria Ramiro (Seafood) made popular by Anthony Bourdain. On our way back from a highly recommended lunch, we got off the subway around Bairro Alto and got lost walking up and down until we made it to Praca do Comercio which is a 4 square block area. We were so tired that we decided to spend the next two hours outside a restaurant drinking beer and watching people. Not sure if it was the beer or sitting down a couple hours, but we managed to eventually get to our hotel. Sorry about going out on a tangent, but since COVID-19 we, like most people, have not been traveling at all.
Without further ado let’s get down to it and discuss the approach and code.
class Solution {
public int minimumEffortPath(int[][] heights) {
}
}
We need to fill in the specified function. The function seems to take a single object which is an array of heights. Note that the heights are in the range [1 : 1,000,000].
main <<< targetGate: 445188 main <<< gate: 445188 2,2 1,2 4,3 main <<< heights: [1, 2] [4, 3] main <<< output: 1 main <<< targetGate: 823337 main <<< gate: 823337 1,1 9 main <<< heights: [9] main <<< output: 0 main <<< targetGate: 786651 main <<< gate: 786651 2,2 1,1 1000000,1000000 main <<< heights: [1, 1] [1000000, 1000000] main <<< output: 999999 main <<< targetGate: 391963 main <<< gate: 391963 2,2 1,1000000 1000000,1 main <<< heights: [1, 1000000] [1000000, 1] main <<< output: 999999 main <<< targetGate: 645514 main <<< gate: 645514 3,3 1,2,2 3,8,2 5,3,5 main <<< rows: 3 cols: 3 main <<< heights: [1, 2, 2] [3, 8, 2] [5, 3, 5] main <<< output: 2 main <<< targetGate: 183893 main <<< gate: 183893 3,3 1,2,3 3,8,4 5,3,5 main <<< rows: 3 cols: 3 main <<< heights: [1, 2, 3] [3, 8, 4] [5, 3, 5] main <<< output: 1 main <<< targetGate: 852844 main <<< gate: 852844 5,5 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 main <<< 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] main <<< output: 0 main <<< targetGate: 724071 main <<< gate: 724071 5,5 1,2,1,1,1 1,2,1,2,1 1,2,1,2,1 1,2,1,2,1000000 1,1,1,1000000,1 main <<< heights: [1, 2, 1, 1, 1] [1, 2, 1, 2, 1] [1, 2, 1, 2, 1] [1, 2, 1, 2, 1000000] [1, 1, 1, 1000000, 1] main <<< output: 999999 main <<< targetGate: 94915 main <<< gate: 94915 3,3 1,2,3 3,8,4 5,3,5 main <<< heights: [1, 2, 3] [3, 8, 4] [5, 3, 5] main <<< output: 1
Some of the test cases are from LeetCode while others were generated by me.
For each pass the test scaffolding displays two values which seem to match. The first one is a target value and the second represents the results of something. We will cover this as part of the second approach.
The software then expects user input. The first line of the input should contain the number of rows and columns for the heights grid. The following lines hold the values for each of the rows.
The value of the grid is then displayed. The purpose is to verify that the input data was properly read.
The last line contains the answer. The answer represents the effort for each example.
// **** global variable(s) ****
static boolean vis[][] = null;
static boolean arrived = false;
static int effort = Integer.MIN_VALUE;
static final int[][] dirs = { {0,1}, {1,0}, {0,-1}, {-1,0} };
// **** global variables to generate gate ****
static int left = 0;
static int right = 1000000;
The vis[][] array of boolean is used to track visited cells. Our algorithm should not visit the same cell more than once. Doing so can cause an endless loop.
The arrived boolean flag indicates if our Depth First Search (DFS) traversal of the heights grid reaches the lower-right cell. If we are not able to reach it, 
then we will learn that is the case after the grid has been traversed. This will become clear when we see the code. Instead we could have directly check on cell heights[rows – 1][cols – 1].
The effort integer variable indicates the maximum effort of traversing the grid. We initialize it with the lowest possible integer.
The dirs array is used to specify the directions in which the next step will be taken at each reachable step. The entries specify: RIGHT, DOWN, LEFT and UP respectively.
The left and right integer variables are used to generate a gate value. We use a gate to specify the maximum height of a cell during a DFS traversal. This will become clear when we look at the code.
/**
* Test scaffolding.
*/
public static void main(String[] args) {
// **** initialize random number generator ****
Random rand = new Random();
// **** target gate ****
int targetGate = rand.nextInt(1000000) + 1;
// **** display target gate value ****
System.out.println("main <<< targetGate: " + targetGate);
// **** loop until target gate is found ****
boolean done = false;
int gate = genGate(-1);
do {
// **** save for comparison ****
int prevGate = gate;
// **** update arrived as needed ****
arrived = (gate >= targetGate) ? true : false;
// **** new gate ****
gate = genGate(gate);
// **** matching values ****
if (gate == prevGate)
done = true;
} while (!done);
// **** display gate ****
System.out.println("main <<< gate: " + gate);
// **** open scanner ****
Scanner sc = new Scanner(System.in);
// **** read number of rows and columns ****
String[] rcStr = sc.nextLine().trim().split(",");
// **** extract number of rows and columns ****
int rows = Integer.parseInt(rcStr[0]);
int cols = Integer.parseInt(rcStr[1]);
// **** declare the array ****
int[][] heights = new int[rows][cols];
// **** loop populating the heights array ****
for (int r = 0; r < rows; r++) {
// **** ****
String[] colsStr = sc.nextLine().trim().split(",");
// **** ****
for (int c = 0; c < cols; c++) {
heights[r] = Integer.parseInt(colsStr);
}
}
// ???? ????
System.out.println("main <<< heights:");
for (int[] rr : heights) {
System.out.println(Arrays.toString(rr));
}
// **** close scanner ****
sc.close();
// **** find and display minimum effort for path ****
System.out.println("main <<< output: " + minimumEffortPath(heights));
}
The code is split into two sections. The first section starts with the first line and ends with the display of the gate value. The second section deals with collecting the data for a test, populating the heights array, invoking the function that computes the result, and then displaying it.
We start the first section initializing a Random number generator. That is used to get a random number between 1 and 1,000,000. That represents a possible value of a cell in the heights grid. The targetGate is assigned such value.
After a couple initialization steps, we enter a loop. We start by saving the current gate value. The genGate() function implements a binary search algorithm. We initialize the process when the function is called with a gate = -1. That starts a binary search in the middle of the specified range [1 : 1,000,000] so the first returned gate should be set to 500,000. The arrived flag is set to true if the gate is larger than the targetGate; otherwise it is set to false. This will be used to mimic if the bottom-right cell has been reached after a DFS traversal.
We then generate a new gate value. If the gate value is the same in two consecutive passes then we set the done flag to exit the loop. Note that we could have implemented a forever loop and just break out of it when the gate and targetGate values match. It is important to strike a balance between short code hard to follow and debug and longer / more explicit code which is easier to understand.
After the loop we just display the value of the gate. If our code behaves as expected, both values should match. At least in all the examples it appears to do so.
Now we enter the second section of the test scaffolding. I believe that at this point we should be able to easily follow the logic flow.
/**
* Entry point for recursive procedure.
*
* Runtime: 124 ms, faster than 33.18% of Java online submissions.
* Memory Usage: 40.2 MB, less than 5.71% of Java online submissions.
*/
static int minimumEffortPath(int[][] heights) {
// **** get number of rows and columns ****
int rows = heights.length;
int cols = heights[0].length;
// **** sanity checks ****
if (rows <= 1 && cols <= 1)
return 0;
// **** loop incrementing the gate ****
// for (int gate = 0; gate < 1000000; gate++) {
// // **** loop pass initialization ****
// arrived = false;
// effort = Integer.MIN_VALUE;
// vis = new boolean[rows][cols];
// // **** start recursion ****
// dfs(heights, 0, 0, gate);
// // **** if reached bottom-right cell; we are done ****
// if (arrived)
// break;
// }
// **** initial gate ****
int gate = genGate(-1);
// **** ****
boolean done = false;
do {
// **** loop pass initialization ****
arrived = false;
effort = Integer.MIN_VALUE;
vis = new boolean[rows][cols];
// **** save for comparison ****
int prevGate = gate;
// **** start recursion ****
dfs(heights, 0, 0, gate);
// **** generate new gate ****
gate = genGate(gate);
// **** matching values ****
if (gate == prevGate)
done = true;
} while (!done);
// **** return effort ****
return effort;
}
The minimumEffortPath() function has some initialization steps and a sanity check. From this point we have a loop that has been commented out. There is a second loop that makes use of the genGate() function. The first loop represents my first approach while the second loop the second approach. We will talk more about the non-existing third approach towards the end of the post.
Note that for both loops the function returns the value of the global effort variable.
If we comment out the second and use the first loop we would loop up to 1,000,000 (worse case) in order to find the minimum effort path. On each cell we need to decide if we can move in up to four directions. If the next cell is too tall, we should not proceed in that direction because the resulting total effort would be larger. Note that in s DFS traversal we may encounter cells with values in the range [1 : 1,000,000].
In the loop we first initialize variables. Then we perform a DFS traversal and decide if we reached the lower-right cell in the heights grid. If we do not, we need to increase the gate by 1 and repeat the process. Sooner or later we will get to a gate value that will allow us to reach the lower-right cell. The third example in the screen capture illustrates a simple grid with 4 cells which will cause our algorithm to loop 1,000,000 times. Imagine if the grid contains thousands of cells.
This code implements a brute force approach. When submitted the code times out.
If we leave the first loop out, and use the second one things change for the better. We start by initializing the gate value. As we know the first gate will be set to 500,000. We then enter a loop. We initialize variables. We save the current gate value to be tested against the new gate value towards the end of the loop. The dfs() recursive function performs a traversal of the grid. We will check the implementation shortly, but it should take care of the effort and arrived variables.
We generate a new gate value and compare it against the saved one in prevGate. If there is a match we exit the loop. The effort variable holds the effort we are required to determine.
/**
* Generate the next value of a binary search.
* Set gate == -1 to initialize.
*/
static int genGate(int gate) {
// **** initialization ****
if (gate == -1) {
left = 0;
right = 1000000;
return right / 2;
}
// **** done ****
if (left > right) {
return gate;
}
// **** compute mid value ****
int mid = left + (right - left) / 2;
// **** go left ****
if (arrived) {
right = mid - 1;
}
// **** go right ****
else {
left = mid + 1;
}
// **** update gate ****
gate = left + (right - left) / 2;
// **** return gate ****
return gate;
}
Look at the code in the genGate() function. It should look somewhat familiar. It implements a binary search in an ordered array. The ordered array is a virtual array of sorted values in the range [1: 1,000,000]. Note we do not need to declare the array (no memory needed).
If the function is called with a value of -1 we initialize variables and return 500,000. We should use a definition to be able to generalize the function for other values, but in this problem, such value will not vary.
We check if we are done and return the same grid value. This allows us to check for two consecutive equal values.
We compute the midpoint in the current range.
We then decide if we have arrived (greater than) or we have not (less than) arrived to the lower-right cell. We update the range and compute the value for the gate to be returned.
/**
* Search for minimum effort.
* Recursive procedure.
*/
static int dfs(int[][] heights, int row, int col, int gate) {
// **** get the number of rows and columns ****
int rows = heights.length;
int cols = heights[0].length;
// **** base case (lower-right cell) ****
if (row == rows - 1 && col == cols - 1) {
arrived = true;
return heights[row][col];
}
// **** flag that this cell as been visited ****
vis[row][col] = true;
// **** recurse in all possible directions ****
for (int i = 0; i < dirs.length; i++) {
// **** next cell ****
int r = row + dirs[i][0];
int c = col + dirs[i][1];
// **** ****
if (r >= 0 && r < rows && c >= 0 && c < cols &&
!vis[r] &&
Math.abs(heights[row][col] - heights[r]) <= gate) {
// **** recursive call ****
int ph = dfs(heights, r, c, gate);
// **** current effort between cells ****
int ce = Math.abs(heights[row][col] - ph);
// **** update effort ****
effort = Math.max(effort, ce);
}
}
// **** return height of current cell ****
return heights[row][col];
}
The dfs() function performs a DFS traversal on the heights grid. It is a recursive function. We pass the heights array, the row and column for the current cell and the current gate value which is constant for each complete DFS traversal of the grid.
We compute the number of rows and columns. For performance we could just use global variables.
The base case is implemented when we reach the lower-right cell of the grid. If we are not there yet, we flag the current cell as visited.
We now make recursive calls in each of the 4 directions is possible. We also check if the next cell has already been visited and if the height is under the value specified by the gate.
If we make a recursive call in the specified direction, the value returned by the dfs() function contains the maximum value of the path it explored. We then compute the difference (effort) between the returned height and the height of the current cell. The global effort value is updated to the maximum value of the current effort and the effort computed for the current cell.
After we check and if needed compute the effort in the 4 directions, we return the height of the current cell.
As you can see the second approach O(log(n)) is much faster than the original one which had to test values from 0 up to 999,999.
The execution time for the second approach is listed in the description of the minimumEffortPath() function.
The third pass that I was going to implement is a simultaneous traversal from the start and end points. If such approach does not get closer to the best time, at this point I have no other ideas. If interested give it a try and let me know your findings. I hope to implement the third approach in the next few days. If you need some direction, the article Bidirectional Search should be of help.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to help out with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private e-mail message. I will reply as soon as possible.
Keep on reading and experimenting. It is the best way to learn, become proficient, refresh your knowledge and enhance your developer toolset!
One last thing, many thanks to all 3,576 subscribers to this blog!!!
Keep safe during the COVID-19 pandemic and help restart the world economy.
John
E-mail: john.canessa@gmail.com