LeetCode 1631. Path With Minimum Effort Solution
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.
Example 1:
Input: heights = [[1,2,2],[3,8,2],[5,3,5]]
Output:
Explanation: The route of [1,3,5,3,5]
has a maximum absolute difference of in consecutive cells.
This is better than the route of [1,2,2,2,5]
, where the maximum absolute difference is .
Example 2:
Input: heights = [[1,2,3],[3,8,4],[5,3,5]]
Output:
Explanation: The route of [1,2,3,4,5]
has a maximum absolute difference of 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:
Explanation: This route does not require any effort.
Constraints:
rows == heights.length
columns == heights[i].length
heights[i][j]
Problem Link: https://leetcode.com/problems/path-with-minimum-effort/
Solution
Brute Force
Our most simple brute force for this problem would be to try all different routes that start from the top-left cell and end in the bottom-right cell. We'll then find the efforts for all these routes and return the smallest.
Full Solution
Instead of thinking of finding the efforts of all possible routes, we should think about finding routes that have some specific effort. Given some effort , how do we check if there exists a route that has an effort smaller or equal to ?
Let's first denote the distance between two adjacent cells as the absolute difference between their heights.
A route will have an effort smaller or equal to if it travels from the top-left cell to the bottom-right cell and all adjacent cells in the route have a distance that doesn't exceed . To check if such routes exist, we can check if there exists a path from the top-left cell to the bottom-right cell such that we never travel between cells with a distance that exceeds . We can accomplish this with a BFS/flood fill algorithm.
We'll denote an effort as good if there exists a route with an effort smaller or equal to .
The minimum effort that's good is the final answer that we return. To find the minimum effort, we can implement a binary search. Why can we binary search this value? Let's say our minimum good effort is . Our binary search condition is satisfied since all values strictly less than are not good and all values greater or equal to are good.
Every binary search iteration, we can check whether or not some effort is good by running the BFS/flood fill algorithm mentioned above.
Time Complexity
Let's denote as number of rows, as number of colmns, and as maximum height in heights
.
Since BFS/flood fill will run in and we have binary search iterations, our final time complexity will be .
Time Complexity:
C++ Solution
1class Solution {
2 const vector<int> deltaRow = {-1, 0, 1, 0};
3 const vector<int> deltaCol = {0, 1, 0, -1};
4 bool isValidEffort(vector<vector<int>>& heights, int mid) {
5 int rows = heights.size();
6 int columns = heights[0].size(); // dimensions for heights
7 vector<vector<bool>> vis(rows, vector<bool>(columns)); // keeps track of whether or not we visited a node
8 queue<int> qRow;
9 queue<int> qCol;
10 qRow.push(0);
11 qCol.push(0); // BFS starts in top-left cell
12 //We can also use queue<pair<int,int>> to store both the row & col in one queue
13 vis[0][0] = true;
14 while (!qRow.empty()) {
15 int curRow = qRow.front();
16 qRow.pop();
17 int curCol = qCol.front();
18 qCol.pop();
19 for (int dir = 0; dir < 4; dir++) {
20 int newRow = curRow + deltaRow[dir];
21 int newCol = curCol + deltaCol[dir];
22 if (newRow < 0 || newRow >= rows || newCol < 0 || newCol >= columns) { // check if cell is in boundary
23 continue;
24 }
25 if (vis[newRow][newCol]) { // check if cell has been visited
26 continue;
27 }
28 if (abs(heights[newRow][newCol] - heights[curRow][curCol]) > mid) { // check if distance exceeds limit
29 continue;
30 }
31 vis[newRow][newCol] = true;
32 qRow.push(newRow);
33 qCol.push(newCol);
34 // process next node
35 }
36 }
37 return vis[rows - 1][columns - 1];
38 }
39
40 public:
41 int minimumEffortPath(vector<vector<int>>& heights) {
42 int low = -1; // every effort less or equal to low will never be good
43 int high = (int)1e6; // every effort greater or equal to high will always be good
44 int mid = (low + high) / 2;
45 while (low + 1 < high) {
46 if (isValidEffort(heights, mid)) {
47 high = mid;
48 } else {
49 low = mid;
50 }
51 mid = (low + high) / 2;
52 }
53 return high;
54 }
55};
Java Solution
1class Solution {
2 final int[] deltaRow = {-1, 0, 1, 0};
3 final int[] deltaCol = {0, 1, 0, -1};
4 private boolean isValidEffort(int[][] heights, int mid){
5 int rows = heights.length;
6 int columns = heights[0].length; // dimensions for heights
7 boolean[][] vis = new boolean[rows][columns]; // keeps track of whether or not we visited a node
8 Queue<Integer> qRow = new LinkedList();
9 Queue<Integer> qCol = new LinkedList();
10 qRow.add(0);
11 qCol.add(0); // BFS starts in top-left cell
12 vis[0][0] = true;
13 while (!qRow.isEmpty()) {
14 int curRow = qRow.poll();
15 int curCol = qCol.poll();
16 for (int dir = 0; dir < 4; dir++) {
17 int newRow = curRow + deltaRow[dir];
18 int newCol = curCol + deltaCol[dir];
19 if (newRow < 0 || newRow >= rows || newCol < 0
20 || newCol >= columns) { // check if cell is in boundary
21 continue;
22 }
23 if (vis[newRow][newCol]) { // check if cell has been visited
24 continue;
25 }
26 if (Math.abs(heights[newRow][newCol] - heights[curRow][curCol]) > mid){
27 // check if distance exceeds limit
28 continue;
29 }
30 vis[newRow][newCol] = true;
31 qRow.add(newRow);
32 qCol.add(newCol);
33 // process next node
34 }
35 }
36 return vis[rows-1][columns-1];
37 }
38 public int minimumEffortPath(int[][] heights) {
39 int rows = heights.length;
40 int columns = heights[0].length; // dimensions for heights
41 int low = -1; // every effort less or equal to low will never be good
42 int high = (int) 1e6; // every effort greater or equal to high will always be good
43 int mid = (low + high) / 2;
44 while (low + 1 < high) {
45 if (isValidEffort(heights,mid)) {
46 high = mid;
47 } else {
48 low = mid;
49 }
50 mid = (low + high) / 2;
51 }
52 return high;
53 }
54}
Python Solution
1import collections 2class Solution: 3 def minimumEffortPath(self, heights: List[List[int]]) -> int: 4 rows = len(heights) 5 columns = len(heights[0]) # dimensions for heights 6 low = -1 # every effort less or equal to low will never be good 7 high = 10 ** 6 # every effort greater or equal to high will always be good 8 mid = (low + high) // 2 9 def isValidEffort(heights, mid): 10 vis = [[False] * columns for a in range(rows)] 11 # keeps track of whether or not we visited a node 12 qRow = collections.deque([0]) 13 qCol = collections.deque([0]) # BFS starts in top-left cell 14 vis[0][0] = True 15 while qRow: 16 curRow = qRow.popleft() 17 curCol = qCol.popleft() 18 for [deltaRow, deltaCol] in [(-1, 0), (0, 1), (1, 0), (0, -1)]: 19 newRow = curRow + deltaRow 20 newCol = curCol + deltaCol 21 if (newRow < 0 or newRow >= rows or newCol < 0 or newCol >= columns): 22 # check if cell is in boundary 23 continue 24 if vis[newRow][newCol] == True: # check if cell has been visited 25 continue 26 if (abs(heights[newRow][newCol] - heights[curRow][curCol]) > mid): 27 # check if distance exceeds limit 28 continue 29 vis[newRow][newCol] = True 30 qRow.append(newRow) 31 qCol.append(newCol) 32 # process next node 33 return vis[rows-1][columns-1] 34 while low + 1 < high: 35 if isValidEffort(heights,mid): 36 high = mid 37 else: 38 low = mid 39 mid = (low + high) // 2 40 return high 41