#1631

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Path With Minimum Effort

Find the minimum effort required to travel from the top-left to the bottom-right of a grid, considering height differences.

array binary search depth first search breadth first search union find

Problem Statement

You are given a 2D array heights where each element represents the height of a grid cell. Starting from the top-left cell at (0, 0), your goal is to travel to the bottom-right cell at (rows-1, columns-1). You can only move up, down, left, or right between adjacent cells.

The objective is to minimize the maximum effort required to traverse the grid. The effort between two consecutive cells is the absolute difference in their heights. Return the minimum maximum effort to reach the destination.

Examples

Example 1

Input: heights = [[1,2,2],[3,8,2],[5,3,5]]

Output: 2

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

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

This route does not require any effort.

Constraints

rows == heights.length
columns == heights[i].length
1 <= rows, columns <= 100
1 <= heights[i][j] <= 106

Solution Approach

Binary Search for Minimum Effort

To find the minimum maximum effort, apply binary search on possible effort values. The search space is the range from 0 to the maximum height difference in the grid. For each middle value in the search, verify if there is a valid path from start to end with that maximum effort using BFS or DFS.

Graph Traversal (BFS/DFS)

Once a candidate effort is chosen via binary search, treat the grid as a graph where each cell is a node, and edges between adjacent cells have weights equal to the height difference. Use BFS or DFS to check if a path exists between the start and end that respects the current maximum effort.

Edge Case Handling

Ensure to handle cases with minimal grid size (e.g., 1x1) and grids with no height differences (i.e., all cells are equal). In such cases, the answer is straightforward as no effort is required.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the binary search over the effort values and the graph traversal for each candidate effort. In the worst case, this results in a time complexity of O(log(maxHeight) * (rows * columns)) where maxHeight is the maximum possible difference in heights.

What Interviewers Usually Probe

Candidates should be able to identify the binary search pattern and the use of BFS/DFS for pathfinding.
Look for clarity in the explanation of the binary search strategy and its connection to grid traversal.
Watch for edge cases such as no height differences or minimal grid sizes.

Common Pitfalls or Variants

Common pitfalls

Failing to recognize that the problem requires binary search over possible efforts rather than simply trying to traverse the grid directly.
Not treating the grid as a graph and mistakenly thinking about each cell as an independent entity rather than part of a graph structure.
Overlooking edge cases where no effort is required (e.g., all cells have the same height).

Follow-up variants

Consider applying the same approach to find the path with the minimum total effort rather than maximum effort.
Modify the problem to allow diagonal moves between cells and evaluate how it affects the approach.
Change the constraints, such as increasing the grid size or allowing negative heights, and analyze the impact on the algorithm.

FAQ

What is the primary pattern used to solve the Path With Minimum Effort problem?

The problem uses binary search over the possible effort values to find the minimum maximum difference between consecutive cells.

How does binary search apply to this problem?

Binary search is applied to determine the smallest possible 'maximum effort' by narrowing down the range and validating each effort using BFS/DFS.

What role does BFS/DFS play in solving this problem?

BFS/DFS is used to verify if a valid path exists from the top-left to the bottom-right cell for a given maximum effort, which is tested iteratively during binary search.

What happens if the grid has no height differences?

If all cells have the same height, no effort is required to traverse, and the answer is 0.

Are there any edge cases to consider in this problem?

Yes, edge cases include minimal grid sizes (e.g., 1x1) and grids with no height differences, where the solution is straightforward.

terminal

Solution

Solution 1: Union-Find

For this problem, we can treat each cell as a node in a graph, and the absolute difference in height between two adjacent cells as the weight of the edge. Therefore, this problem is to solve the connectivity problem from the top-left node to the bottom-right node.

class UnionFind:
    def __init__(self, n):
        self.p = list(range(n))
        self.size = [1] * n

    def find(self, x):
        if self.p[x] != x:
            self.p[x] = self.find(self.p[x])
        return self.p[x]

    def union(self, a, b):
        pa, pb = self.find(a), self.find(b)
        if pa == pb:
            return False
        if self.size[pa] > self.size[pb]:
            self.p[pb] = pa
            self.size[pa] += self.size[pb]
        else:
            self.p[pa] = pb
            self.size[pb] += self.size[pa]
        return True

    def connected(self, a, b):
        return self.find(a) == self.find(b)


class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        m, n = len(heights), len(heights[0])
        uf = UnionFind(m * n)
        e = []
        dirs = (0, 1, 0)
        for i in range(m):
            for j in range(n):
                for a, b in pairwise(dirs):
                    x, y = i + a, j + b
                    if 0 <= x < m and 0 <= y < n:
                        e.append(
                            (abs(heights[i][j] - heights[x][y]), i * n + j, x * n + y)
                        )
        e.sort()
        for h, a, b in e:
            uf.union(a, b)
            if uf.connected(0, m * n - 1):
                return h
        return 0

Solution 2: Binary Search + BFS

We notice that if the maximum physical consumption value of a path is $x$, then for any $y > x$, this path also meets the conditions. This shows monotonicity, so we can use the binary search method to find the minimum physical consumption value that meets the conditions.

class UnionFind:
    def __init__(self, n):
        self.p = list(range(n))
        self.size = [1] * n

    def find(self, x):
        if self.p[x] != x:
            self.p[x] = self.find(self.p[x])
        return self.p[x]

    def union(self, a, b):
        pa, pb = self.find(a), self.find(b)
        if pa == pb:
            return False
        if self.size[pa] > self.size[pb]:
            self.p[pb] = pa
            self.size[pa] += self.size[pb]
        else:
            self.p[pa] = pb
            self.size[pb] += self.size[pa]
        return True

    def connected(self, a, b):
        return self.find(a) == self.find(b)


class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        m, n = len(heights), len(heights[0])
        uf = UnionFind(m * n)
        e = []
        dirs = (0, 1, 0)
        for i in range(m):
            for j in range(n):
                for a, b in pairwise(dirs):
                    x, y = i + a, j + b
                    if 0 <= x < m and 0 <= y < n:
                        e.append(
                            (abs(heights[i][j] - heights[x][y]), i * n + j, x * n + y)
                        )
        e.sort()
        for h, a, b in e:
            uf.union(a, b)
            if uf.connected(0, m * n - 1):
                return h
        return 0

Solution 3: Heap-optimized Dijkstra Algorithm

We can treat each cell as a node in a graph, and the absolute difference in height between two adjacent cells as the weight of the edge. Therefore, this problem is to solve the shortest path problem from the top-left node to the bottom-right node.

class UnionFind:
    def __init__(self, n):
        self.p = list(range(n))
        self.size = [1] * n

    def find(self, x):
        if self.p[x] != x:
            self.p[x] = self.find(self.p[x])
        return self.p[x]

    def union(self, a, b):
        pa, pb = self.find(a), self.find(b)
        if pa == pb:
            return False
        if self.size[pa] > self.size[pb]:
            self.p[pb] = pa
            self.size[pa] += self.size[pb]
        else:
            self.p[pa] = pb
            self.size[pb] += self.size[pa]
        return True

    def connected(self, a, b):
        return self.find(a) == self.find(b)


class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        m, n = len(heights), len(heights[0])
        uf = UnionFind(m * n)
        e = []
        dirs = (0, 1, 0)
        for i in range(m):
            for j in range(n):
                for a, b in pairwise(dirs):
                    x, y = i + a, j + b
                    if 0 <= x < m and 0 <= y < n:
                        e.append(
                            (abs(heights[i][j] - heights[x][y]), i * n + j, x * n + y)
                        )
        e.sort()
        for h, a, b in e:
            uf.union(a, b)
            if uf.connected(0, m * n - 1):
                return h
        return 0

Continue Practicing

#778 swim in rising water #1970 last day where you can still cross #1559 detect cycles in 2d grid