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:

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

Example 2:

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

Constraints:

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

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

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

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

The minimum effort $a$ 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 $b$. Our binary search condition is satisfied since all values strictly less than $b$ are not good and all values greater or equal to $b$ 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 $R$ as number of rows, $C$ as number of colmns, and $M$ as maximum height in heights.

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

Time Complexity: $\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

Solution Implementation