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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Path With Minimum Effort

Number: 1753

Difficulty: Medium

Paid? No

Companies: Google, Meta, Microsoft, TikTok, Uber, Amazon, Cohesity

Problem Description

You are given a 2D grid of integers representing heights. Starting from the top-left cell, your goal is to reach the bottom-right cell while minimizing the "effort". The effort of a path is defined as the maximum absolute difference between the heights of two consecutive cells along the path. You can move up, down, left, or right, and the task is to determine the minimum effort required to travel from the start to the destination.

Key Insights

  • The problem asks for a path minimizing the maximum step difference instead of the sum of weights.
  • This can be modeled as a graph problem where each cell is a node connected to its neighbors with edge weights equal to the absolute difference in heights.
  • A modified Dijkstra’s algorithm fits well since the "cost" of a path is determined by the maximum weight along the path rather than the sum.
  • Alternatively, binary search combined with a flood-fill (BFS/DFS) or Union-Find could determine the smallest threshold that connects the start and end.

Space and Time Complexity

Time Complexity: O(m * n * log(m * n)) where m and n are the dimensions of the grid (each cell processed and maintained in a priority queue).
Space Complexity: O(m * n) for the distance matrix and priority queue.

Solution

The solution uses a modified Dijkstra’s algorithm. The grid is treated as a graph where each cell is a node. The cost to move from one cell to an adjacent cell is the absolute difference in their heights. However, instead of summing up costs, the cost associated with a path is determined by the maximum single-step cost encountered along that path. Using a min-heap (priority queue), we always expand the least costly (in terms of maximum step encountered so far) path. We update the cost for neighboring cells if a path with a smaller maximum difference is found. The process continues until the destination cell is reached.

Code Solutions

import heapq

def minimumEffortPath(heights):
    rows, cols = len(heights), len(heights[0])
    # Directions: up, down, left, right
    directions = [(1,0), (-1,0), (0,1), (0,-1)]
    
    # Distance matrix to track minimum effort found for each cell.
    effort = [[float('inf')] * cols for _ in range(rows)]
    effort[0][0] = 0

    # Priority queue containing (current effort, row, col)
    minHeap = [(0, 0, 0)]
    
    while minHeap:
        currentEffort, row, col = heapq.heappop(minHeap)
        if row == rows - 1 and col == cols - 1:
            return currentEffort
        
        for dr, dc in directions:
            newRow, newCol = row + dr, col + dc
            if 0 <= newRow < rows and 0 <= newCol < cols:
                # The cost to move to the neighbor is the absolute difference in heights
                stepEffort = abs(heights[newRow][newCol] - heights[row][col])
                # The effort for the new cell is the maximum effort so far along the path.
                newEffort = max(currentEffort, stepEffort)
                if newEffort < effort[newRow][newCol]:
                    effort[newRow][newCol] = newEffort
                    heapq.heappush(minHeap, (newEffort, newRow, newCol))
    return 0

# Example usage:
heights = [[1,2,2],[3,8,2],[5,3,5]]
print(minimumEffortPath(heights))
← Back to All Questions