mediumGraphsPure DSA~25 min
Path Maximizing the Minimum Cell Value
A data transfer route crosses a grid of link capacities. The throughput of a route is its weakest link. Find a route from the top-left to the bottom-right that maximizes that weakest link.
Problem
Given an m x n grid of non-negative integers, consider all 4-directional paths from (0,0) to (m-1,n-1). The score of a path is the minimum value among the cells on it. Return the maximum score over all paths.
Input
An m x n grid of non-negative integers.
Output
An integer: the maximum possible path-minimum (the widest bottleneck).
Constraints
- 1 <= m, n <= 100
- 0 <= grid[i][j] <= 10^9
Examples
Example 1
Input
grid = [[5,4,5],[1,2,6],[7,4,6]]
Output
4
A path keeping every cell >= 4 exists; none keeps a higher minimum.
Example 2
Input
grid = [[2,2,1,2,2,2],[1,2,2,2,1,2]]
Output
2
A path through cells all >= 2 reaches the corner.