Domain 2MediumMEDIUM

Path With Maximum Minimum Value

Navigate from top-left to bottom-right maximizing the minimum value on path using Binary Search on Answer with BFS reachability checks.

Domain: medium•Updated: 2026-09-08
#binary-search#bfs#o(rc-log-max)#o(rc)]

Problem Breakdown

We are given a grid A of size R×CR \times C containing non-negative integers. We must find a path from (0, 0) to (R - 1, C - 1). The “score” of any path is defined as the minimum value among all cells visited in that specific path. Our goal is to maximize this score across all possible paths.

Inputs:

  • A list of lists A representing the grid values.
  • Constraints: R,C≤100R, C \le 100, Values ≥0\ge 0.

Outputs:

  • An integer representing the maximum bottleneck value (minimum cell value on path) achievable from start to end.

Intuition

The problem asks us to maximize a “bottleneck” capacity along a path. This property exhibits monotonicity: if we can reach the destination with all cells having values ≥X\ge X, then it is guaranteed that we can also do so for any value Y<XY < X.

This suggests Binary Search on the Answer. Instead of searching through paths, we search through possible values.

  1. Determine a range [low, high] covering all potential scores (e.g., from min(A) to max(A)).
  2. For each candidate value mid, check if it is feasible to travel from start to end using only cells with values ≥mid\ge mid.
  3. If feasible (can_reach(mid) == True), then this score might be the answer, but we try higher: store result and move low = mid + 1.
  4. If not feasible, the threshold is too high: reduce range by moving high = mid - 1.

The reachability check can be efficiently performed using BFS or DFS, which runs in O(R⋅C)O(R \cdot C) time for each binary search step.

Approach

  1. Initialize Bounds: Set the lower bound to 0 (or minimum grid value) and upper bound to max(A) (or maximum possible integer). Initialize a variable ans to store the highest valid score found so far.
  2. Binary Search Loop: While low <= high:
    • Compute mid = low + (high - low) // 2.
    • Call helper function can_reach(mid) which returns boolean feasibility.
  3. Reachability Check (can_reach):
    • Verify the starting cell (0, 0) meets the threshold immediately; if not, return False.
    • Use a queue for BFS and a visited matrix to prevent cycles/redundant processing.
    • Traverse neighbors (Up, Down, Left, Right). Only enqueue valid cells where A[nr][nc] >= mid.
    • If destination (R-1, C-1) is reached during traversal, return True.
  4. Update Bounds: Based on the boolean result of BFS, adjust binary search pointers and update ans if a feasible path was found for current mid.
  5. Return Result: Return ans, which holds the maximum valid threshold encountered.

Complexity Analysis

  • Time Complexity: O(R⋅Clog⁡(max_val))O(R \cdot C \log(\text{max\_val})). We perform binary search over the value range (up to ≈30\approx 30 iterations for values up to 10910^9, or fewer if bounded by grid min/max). Each iteration runs a BFS/DFS which visits each cell at most once, taking O(R⋅C)O(R \cdot C). Total operations are roughly proportional to number of cells times log factor.
  • Space Complexity: O(R⋅C)O(R \cdot C) for the visited matrix and the queue used in BFS.

Solution

from collections import deque

def path_with_max_min_value(A):
    if not A or not A[0]:
        return 0
    
    R, C = len(A), len(A[0])
    
    # Helper to check reachability with a minimum threshold value
    def can_reach(threshold):
        # If start cell itself is below threshold, impossible immediately
        if A[0][0] < threshold:
            return False
        
        visited = [[False for _ in range(C)] for _ in range(R)]
        queue = deque([(0, 0)])
        visited[0][0] = True
        
        while queue:
            r, c = queue.popleft()
            
            # Check if we reached the destination
            if r == R - 1 and c == C - 1:
                return True
            
            # Explore neighbors (Up, Down, Left, Right)
            for dr, dc in [(-1,0), (1,0), (0,-1), (0,1)]:
                nr, nc = r + dr, c + dc
                
                if 0 <= nr < R and 0 <= nc < C:
                    # Only move to valid neighbors that meet threshold condition
                    if not visited[nr][nc] and A[nr][nc] >= threshold:
                        visited[nr][nc] = True
                        queue.append((nr, nc))
        
        return False

    low, high = 0, max(max(row) for row in A) # Optimization: bound by actual min/max present
    
    ans = -1
    
    while low <= high:
        mid = (low + high) // 2
        
        if can_reach(mid):
            ans = mid      # This is a valid score, try higher
            low = mid + 1
        else:
            high = mid - 1
            
    return ans

# Example usage matching LeetCode signature style implicitly
if __name__ == "__main__":
    print(path_with_max_min_value([[5,4,5],[1,2,6],[7,4,6]])) # Output: 4

Edge Cases Handled

  • Start equals End (1x1 Grid): The logic initializes low and high. If the single cell is VV, BFS immediately sees start==end. Binary search converges to VV. Correctly returns grid value.
  • Blocked Path: If all paths require stepping below a certain low number, binary search will converge on that bottleneck limit or return -1 (though problem guarantees path exists implicitly by constraints usually). My code initializes ans = -1 but given valid inputs where start/end are reachable via at least one value, it returns the max.
  • Large Values: Python handles large integers automatically; logic relies only on comparison operators which work for 10910^9.
  • Start Value Constraint: The BFS check explicitly verifies A[0][0] >= threshold before starting queue to avoid invalid initialization states in binary search steps where the start node itself is too low.