Path With Maximum Minimum Value

Path With Maximum Minimum Value

What is this problem about?

The Path With Maximum Minimum Value problem asks you to find a path from the top-left to bottom-right of a grid such that the minimum value along the path is maximized. This coding problem uses binary search on the answer, modified Dijkstra (max-min path), or Union-Find with sorted edges. The array, matrix, union find, BFS, DFS, binary search, and heap interview pattern is comprehensively tested.

Why is this asked in interviews?

Amazon, DoorDash, and Google ask this because it's a "maximize the minimum" problem — a pattern that appears frequently in network design, bottleneck paths, and resource allocation. The key insight is that this is the inverse of the classic shortest path: maximize the bottleneck.

Algorithmic pattern used

Modified Dijkstra (max bottleneck). Use a max-heap of (min_value_so_far, row, col). Initialize with (grid[0][0], 0, 0). Greedily expand to the neighbor that maximizes the minimum. Track visited cells. When reaching bottom-right, return the accumulated minimum value. This gives O(mn log mn) time.

Example explanation

Grid:

5  4  5
1  2  6
7  4  6

From (0,0)=5: explore neighbors. Path (0,0)→(0,1)→(0,2)→(1,2)→(2,2): min=min(5,4,5,6,6)=4. Path through 7 and 4 gives lower min. Maximum minimum = 4.

Common mistakes candidates make

• Using standard BFS (doesn't optimize for max-min, only finds any path).
• Applying Dijkstra with sum instead of min (wrong objective).
• Not using a max-heap (min-heap would give wrong priority).
• Not tracking visited cells (revisiting causes infinite loops).

Interview preparation tip

"Maximize the minimum" path problems use a max-heap where the priority is the minimum value seen along the path. This is the "widest path" or "bottleneck path" variant of Dijkstra. Binary search on the minimum value + BFS feasibility check is an alternative O(mn log(max_val)) approach. Practice both for breadth. Similar problems: "maximize bandwidth in a network," "safe passage with maximum floor."