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 Maximum Minimum Value

Number: 1099

Difficulty: Medium

Paid? Yes

Companies: Amazon

Problem Description

Given an m x n grid of integers, the goal is to find a path from the top-left corner (0, 0) to the bottom-right corner (m - 1, n - 1) such that the score of the path, defined as the minimum value encountered along the path, is maximized. Movement is allowed in the 4 cardinal directions.

Key Insights

  • The score of a path is determined by its lowest value. Therefore, the objective is to maximize this minimum value over all possible paths.
  • A greedy strategy that always considers the next step with the highest value works well.
  • Using a max-heap (priority queue) allows for exploring high-value paths first.
  • Once the destination is reached, the minimum value along the chosen path is the answer.
  • Alternative methods include binary search over the possible answer space with a connectivity check (using DFS/BFS) or Union-Find to simulate connectivity with a threshold.

Space and Time Complexity

Time Complexity: O(m * n * log(m * n)) because each cell might be pushed into the heap once and each heap operation costs log(m*n). Space Complexity: O(m * n) for the heap and visited cells tracking.

Solution

The solution uses a greedy algorithm implemented with a max-heap:

  1. Start at cell (0, 0) and initialize the score as the value at the starting cell.
  2. Use a max-heap to store cells with their corresponding values in descending order.
  3. Repeatedly pop the cell with the current highest value. Update the score as the minimum value encountered so far along the path.
  4. If the destination cell is reached, return the current score.
  5. Otherwise, push all valid neighboring cells that have not been visited into the heap. This method ensures that paths that are more promising (i.e., with higher current minimum values) are explored first, thus guaranteeing the maximum possible score upon reaching the destination.

Code Solutions

import heapq

def maximumMinimumPath(grid):
    m, n = len(grid), len(grid[0])
    # Max-heap: use negative values because Python's heapq is a min-heap.
    heap = [(-grid[0][0], 0, 0)]
    visited = [[False] * n for _ in range(m)]
    visited[0][0] = True
    
    # Directions: up, down, left, right.
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    # Current answer is the start value.
    current_min = grid[0][0]
    
    while heap:
        # Get the cell with the maximum value (using negative because of min-heap).
        val, i, j = heapq.heappop(heap)
        # Reverse the sign to get the actual value.
        val = -val
        # Update the current path min.
        current_min = min(current_min, val)
        # If destination is reached, return current path's min value.
        if i == m - 1 and j == n - 1:
            return current_min
        
        for di, dj in directions:
            ni, nj = i + di, j + dj
            if 0 <= ni < m and 0 <= nj < n and not visited[ni][nj]:
                visited[ni][nj] = True
                # Push neighbor cell into heap.
                heapq.heappush(heap, (-grid[ni][nj], ni, nj))
    
    return -1  # Should never reach here if input grid is valid.

# Example test
print(maximumMinimumPath([[5,4,5],[1,2,6],[7,4,6]]))
← Back to All Questions