1631. Path with Minimum Effort - Explanation

Description

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,1,1],
    [3,2,4],
    [2,5,4]
]

Output: 2

Explanation: The route of [1,1,2,4,4] has a maximum absolute difference of 2 in consecutive cells.

Example 2:

Input: heights = [
    [1,1,1],
    [1,1,2],
    [6,5,2]
]

Output: 1

Explanation: The route of [1,1,1,1,1,2,2] has a maximum absolute difference of 1 in consecutive cells.

Constraints:

row == heights.length
col == heights[i].length
1 <= row, col <= 100
1 <= heights[i][j].length <= 1,000,000 .

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Dijkstra's Algorithm

class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        ROWS, COLS = len(heights), len(heights[0])
        minHeap = [[0, 0, 0]]  # [diff, row, col]
        visit = set()
        directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]

        while minHeap:
            diff, r, c = heapq.heappop(minHeap)

            if (r, c) in visit:
                continue

            visit.add((r, c))

            if (r, c) == (ROWS - 1, COLS - 1):
                return diff

            for dr, dc in directions:
                newR, newC = r + dr, c + dc
                if (
                    newR < 0 or newC < 0 or
                    newR >= ROWS or newC >= COLS or
                    (newR, newC) in visit
                ):
                    continue

                newDiff = max(diff, abs(heights[r][c] - heights[newR][newC]))
                heapq.heappush(minHeap, [newDiff, newR, newC])

        return 0

Time & Space Complexity

Time complexity: $O(m * n * \log (m * n))$
Space complexity: $O(m * n)$

Where $m$ is the number of rows and $n$ is the number of columns in the given matrix.

2. Binary Search + DFS

class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        ROWS, COLS = len(heights), len(heights[0])
        directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]

        def dfs(r, c, limit, visited):
            if r == ROWS - 1 and c == COLS - 1:
                return True

            visited.add((r, c))
            for dr, dc in directions:
                newR, newC = r + dr, c + dc
                if (newR < 0 or newC < 0 or
                    newR >= ROWS or newC >= COLS or
                    (newR, newC) in visited or
                    abs(heights[newR][newC] - heights[r][c]) > limit):
                    continue

                if dfs(newR, newC, limit, visited):
                    return True
            return False

        l, r = 0, 1000000
        res = r

        while l <= r:
            mid = (l + r) // 2
            if dfs(0, 0, mid, set()):
                res = mid
                r = mid - 1
            else:
                l = mid + 1

        return res

Time & Space Complexity

Time complexity: $O(m * n * \log (m * n))$
Space complexity: $O(m * n)$

Where $m$ is the number of rows and $n$ is the number of columns in the given matrix.

3. Kruskal's Algorithm

class DSU:
    def __init__(self, n):
        self.Parent = list(range(n + 1))
        self.Size = [1] * (n + 1)

    def find(self, node):
        if self.Parent[node] != node:
            self.Parent[node] = self.find(self.Parent[node])
        return self.Parent[node]

    def union(self, u, v):
        pu = self.find(u)
        pv = self.find(v)
        if pu == pv:
            return False
        if self.Size[pu] < self.Size[pv]:
            pu, pv = pv, pu
        self.Size[pu] += self.Size[pv]
        self.Parent[pv] = pu
        return True


class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        ROWS, COLS = len(heights), len(heights[0])
        edges = []
        for r in range(ROWS):
            for c in range(COLS):
                if r + 1 < ROWS:
                    edges.append((abs(heights[r][c] - heights[r + 1][c]), r * COLS + c, (r + 1) * COLS + c))
                if c + 1 < COLS:
                    edges.append((abs(heights[r][c] - heights[r][c + 1]), r * COLS + c, r * COLS + c + 1))

        edges.sort()
        dsu = DSU(ROWS * COLS)
        for weight, u, v in edges:
            dsu.union(u, v)
            if dsu.find(0) == dsu.find(ROWS * COLS - 1):
                return weight
        return 0

Time & Space Complexity

Time complexity: $O(m * n * \log (m * n))$
Space complexity: $O(m * n)$

Where $m$ is the number of rows and $n$ is the number of columns in the given matrix.

4. Shortest Path Faster Algorithm

class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        ROWS, COLS = len(heights), len(heights[0])
        dist = [float('inf')] * (ROWS * COLS)
        dist[0] = 0
        in_queue = [False] * (ROWS * COLS)

        def index(r, c):
            return r * COLS + c

        queue = deque([0])
        in_queue[0] = True
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

        while queue:
            u = queue.popleft()
            in_queue[u] = False
            r, c = divmod(u, COLS)

            for dr, dc in directions:
                newR, newC = r + dr, c + dc
                if 0 <= newR < ROWS and 0 <= newC < COLS:
                    v = index(newR, newC)
                    weight = abs(heights[r][c] - heights[newR][newC])
                    new_dist = max(dist[u], weight)
                    if new_dist < dist[v]:
                        dist[v] = new_dist
                        if not in_queue[v]:
                            queue.append(v)
                            in_queue[v] = True

        return dist[ROWS * COLS - 1]

Time & Space Complexity

Time complexity:
- $O(m * n)$ time in average case.
- $O(m ^ 2 * n ^ 2)$ time in worst case.
Space complexity: $O(m * n)$

Where $m$ is the number of rows and $n$ is the number of columns in the given matrix.