We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Path With Minimum Effort

Difficulty: Medium

Problem Description

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.

Key Insights

  • The problem can be viewed as a pathfinding problem in a 2D grid where the cost of moving from one cell to another is determined by the height difference.
  • The goal is to minimize the maximum height difference encountered on the path.
  • A binary search can be employed on the possible values of the maximum effort to find the minimum effort required to reach the destination.
  • A breadth-first search (BFS) or depth-first search (DFS) can be used to verify if a certain maximum effort allows reaching the destination.

Space and Time Complexity

Time Complexity: O(rows * columns * log(max_height_difference)), where max_height_difference is the difference between the maximum and minimum height in the grid.
Space Complexity: O(rows * columns) due to the storage needed for the visited nodes or the queue in BFS.

Solution

To solve the problem, we will apply a binary search on the effort values. The key steps in the solution are:

  1. Binary Search: We will search for the minimum possible maximum effort. The low bound will be 0 (minimum possible effort), and the high bound will be the maximum height difference in the grid.
  2. BFS/DFS for Path Validation: For each midpoint effort in the binary search, we will use BFS or DFS to check if we can reach the bottom-right cell from the top-left cell such that no edge (height difference) exceeds the current effort.
  3. If a path exists for the current effort, we try for a smaller effort; if not, we increase the effort.

Code Solutions

from collections import deque

def minimumEffortPath(heights):
    rows, cols = len(heights), len(heights[0])
    
    def canReachDestination(maxEffort):
        # BFS to check if we can reach (rows-1, cols-1)
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        queue = deque([(0, 0)])
        visited = set((0, 0))

        while queue:
            x, y = queue.popleft()
            if x == rows - 1 and y == cols - 1:
                return True
            
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < rows and 0 <= ny < cols and (nx, ny) not in visited:
                    if abs(heights[nx][ny] - heights[x][y]) <= maxEffort:
                        visited.add((nx, ny))
                        queue.append((nx, ny))
        return False

    left, right = 0, max(max(row) for row in heights) - min(min(row) for row in heights)
    
    while left < right:
        mid = (left + right) // 2
        if canReachDestination(mid):
            right = mid
        else:
            left = mid + 1
            
    return left
← Back to All Questions