Problem Breakdown
We are given a grid A of size 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
Arepresenting the grid values. - Constraints: , Values .
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 , then it is guaranteed that we can also do so for any value .
This suggests Binary Search on the Answer. Instead of searching through paths, we search through possible values.
- Determine a range
[low, high]covering all potential scores (e.g., frommin(A)tomax(A)). - For each candidate value
mid, check if it is feasible to travel from start to end using only cells with values . - If feasible (
can_reach(mid) == True), then this score might be the answer, but we try higher: store result and movelow = mid + 1. - 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 time for each binary search step.
Approach
- Initialize Bounds: Set the lower bound to
0(or minimum grid value) and upper bound tomax(A)(or maximum possible integer). Initialize a variableansto store the highest valid score found so far. - Binary Search Loop: While
low <= high:- Compute
mid = low + (high - low) // 2. - Call helper function
can_reach(mid)which returns boolean feasibility.
- Compute
- 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.
- Verify the starting cell
- Update Bounds: Based on the boolean result of BFS, adjust binary search pointers and update
ansif a feasible path was found for currentmid. - Return Result: Return
ans, which holds the maximum valid threshold encountered.
Complexity Analysis
- Time Complexity: . We perform binary search over the value range (up to iterations for values up to , or fewer if bounded by grid min/max). Each iteration runs a BFS/DFS which visits each cell at most once, taking . Total operations are roughly proportional to number of cells times log factor.
- Space Complexity: for the
visitedmatrix 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
lowandhigh. If the single cell is , BFS immediately sees start==end. Binary search converges to . 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 = -1but 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 .
- Start Value Constraint: The BFS check explicitly verifies
A[0][0] >= thresholdbefore starting queue to avoid invalid initialization states in binary search steps where the start node itself is too low.