1631. Path With Minimum Effort

Python

Backtracking (Timelimit Exceed)

• Time: O(3^(m*n))
• Space: O(3^(m*n))

import math


class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        m, n = len(heights), len(heights[0])
        min_effort = math.inf

        def backtrack(row: int, col: int, effort: int):
            nonlocal min_effort
            nonlocal heights

            if row == m-1 and col == n-1:
                min_effort = min(min_effort, effort)
                return

            current_height = heights[row][col]
            heights[row][col] = 0

            # up
            if row-1 >= 0 and heights[row-1][col] != 0:
                current_effort = abs(current_height - heights[row-1][col])
                current_diff = max(current_effort, effort)
                if current_diff < min_effort:
                    backtrack(row-1, col, current_diff)
            # down
            if row+1 < m and heights[row+1][col] != 0:
                current_effort = abs(current_height - heights[row+1][col])
                current_diff = max(current_effort, effort)
                if current_diff < min_effort:
                    backtrack(row+1, col, current_diff)
            # left
            if col-1 >= 0 and heights[row][col-1] != 0:
                current_effort = abs(current_height - heights[row][col-1])
                current_diff = max(current_effort, effort)
                if current_diff < min_effort:
                    backtrack(row, col-1, current_diff)
            # right
            if col+1 < n and heights[row][col+1] != 0:
                current_effort = abs(current_height - heights[row][col+1])
                current_diff = max(current_effort, effort)
                if current_diff < min_effort:
                    backtrack(row, col+1, current_diff)

            heights[row][col] = current_height

        backtrack(0, 0, 0)

        return min_effort

Binary Search on all possible efforts

• Time: O(m*n)
• Space: O(m*n) # the visited hashset

from collections import deque


class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        left, right = 0, 10000000
        while left < right:
            pivot = (left+right) >> 1
            if self.is_dest_reachable(heights, pivot):
                right = pivot
            else:
                left = pivot + 1
        return left

    @staticmethod
    def is_dest_reachable(heights, effort: int):
        ty, tx = len(heights)-1, len(heights[0])-1  # Stand as: Target Y, Target X
        visited = set()
        queue = deque([(0, 0)])

        while queue:
            x, y = queue.popleft()
            if x == tx and y == ty:
                return True

            visited.add((x, y))

            # up
            if y-1 >= 0 and (x, y-1) not in visited:
                current_diff = abs(heights[y][x]-heights[y-1][x])
                if current_diff <= effort:
                    visited.add((x, y-1))
                    queue.append((x, y-1))
            # down
            if y+1 <= ty and (x, y+1) not in visited:
                current_diff = abs(heights[y][x]-heights[y+1][x])
                if current_diff <= effort:
                    visited.add((x, y+1))
                    queue.append((x, y+1))
            # left
            if x-1 >= 0 and (x-1, y) not in visited:
                current_diff = abs(heights[y][x]-heights[y][x-1])
                if current_diff <= effort:
                    visited.add((x-1, y))
                    queue.append((x-1, y))
            # right
            if x+1 <= tx and (x+1, y) not in visited:
                current_diff = abs(heights[y][x]-heights[y][x+1])
                if current_diff <= effort:
                    visited.add((x+1, y))
                    queue.append((x+1, y))