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.

Example 1:

Example

Input: heights = [[1,2,2],[3,8,2],[5,3,5]]
Output: 22
Explanation: The route of [1,3,5,3,5] has a maximum absolute difference of 22 in consecutive cells. This is better than the route of [1,2,2,2,5], where the maximum absolute difference is 33.

Example 2:

Example

Input: heights = [[1,2,3],[3,8,4],[5,3,5]]
Output: 11
Explanation: The route of [1,2,3,4,5] has a maximum absolute difference of 11 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: 00
Explanation: This route does not require any effort.

Constraints:

rows == heights.length
columns == heights[i].length
1rows,columns1001 \leq \text{rows}, \text{columns} \leq 100
11 \leq heights[i][j] 106\leq 10^6


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 aa, how do we check if there exists a route that has an effort smaller or equal to aa?

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 aa 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 aa. 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 aa. We can accomplish this with a BFS/flood fill algorithm.

We'll denote an effort aa as good if there exists a route with an effort smaller or equal to aa.

The minimum effort aa 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 bb. Our binary search condition is satisfied since all values strictly less than bb are not good and all values greater or equal to bb 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 RR as number of rows, CC as number of colmns, and MM as maximum height in heights.

Since BFS/flood fill will run in O(RC)\mathcal{O}(RC) and we have O(logM)\mathcal{O}(\log{M}) binary search iterations, our final time complexity will be O(RClogM)\mathcal{O}(RC\log{M}).

Time Complexity: O(RClogM)\mathcal{O}(RC\log{M})

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
Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

Given an array of 1,000,000 integers that is almost sorted, except for 2 pairs of integers. Which algorithm is fastest for sorting the array?

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

Not Sure What to Study? Take the 2-min Quiz:

In a binary min heap, the minimum element can be found in:

Fast Track Your Learning with Our Quick Skills Quiz:

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫