AlgoMaster Logo

Path With Maximum Minimum Value

mediumFrequencyUpdated September 21, 2026

Understanding the Problem

We need to find a path from the top-left corner to the bottom-right corner of a grid. The path can move in all four directions (not just right and down), and can visit each cell at most once. The "score" of a path is the smallest cell value along that path, and we want to maximize this score.

One way to picture the structure: treat each cell value as the width of a corridor. The bottleneck on any route is its narrowest corridor, and the goal is the route whose narrowest corridor is as wide as possible. This is a maximin path problem.

The distinguishing feature is that we are not minimizing or maximizing a sum. We care about the minimum value along the path, and we want the path that makes that minimum as large as possible. That reframes the problem around thresholds rather than shortest paths: "Is there a path where every cell is at least X?"

Key Constraints:

  • 1 <= m, n <= 100 → Up to 10,000 cells, so an O(m n log(m * n)) solution is comfortably within limits.
  • 0 <= grid[i][j] <= 10^9 → Values fit in a 32-bit signed integer (max ~2.1 * 10^9), so int is safe everywhere and no overflow handling is needed. The large range only affects the binary search bounds.

Approach 1: Binary Search + BFS

Intuition

Fix a candidate answer X, meaning we claim there is a path on which every cell has value at least X. Verifying that claim is straightforward: delete every cell with value below X, then check whether (0,0) and (m-1,n-1) are still connected with a BFS or DFS.

The problem then reduces to finding the largest X for which a path of cells with value >= X connects start to end. This is a binary search on the answer, with the search space being the range of cell values. The feasibility test is monotonic: if a path exists for threshold X, it also exists for every threshold Y < X, because lowering the threshold only adds cells and never removes one. That monotonicity is what lets binary search converge on the boundary.

Algorithm

  1. Find the minimum and maximum values in the grid. These define the binary search range. Note: the answer cannot exceed min(grid[0][0], grid[m-1][n-1]) since the path must include both endpoints.
  2. Binary search on the threshold value mid.
  3. For each mid, run BFS from (0,0) using only cells with value >= mid.
  4. If BFS reaches (m-1,n-1), then mid is feasible. Try a larger threshold (search right half).
  5. If BFS does not reach (m-1,n-1), then mid is too large. Search left half.
  6. Return the largest feasible threshold.

Example Walkthrough

1Initial grid. Binary search range: lo=0, hi=min(5,6)=5
0
1
2
0
start
5
4
5
1
1
2
6
2
7
4
end
6
1/7

Code

This runs a full BFS up to 30 times. The next approach finds the optimal path in a single traversal by processing cells in order of value.

Approach 2: Max-Heap BFS (Modified Dijkstra's)

Intuition

Grow the explored region outward from (0,0), and whenever there is a choice of which cell to expand into next, expand into the unvisited neighbor with the largest value. Reaching a high-valued cell cannot lower the path's minimum, while a low-valued cell might become the bottleneck, so postponing the low values keeps the running minimum as high as possible.

This is a modified Dijkstra's algorithm. Standard Dijkstra's uses a min-heap to always process the closest node next; here a max-heap always processes the highest-value cell next. Instead of tracking shortest distances, we track the maximum achievable minimum value on the path to each cell. The first time the destination (m-1,n-1) is popped, the running minimum on the path that reached it is the answer.

Algorithm

  1. Initialize a max-heap with the starting cell (0,0) and its value.
  2. Create a visited array to track processed cells. Mark (0,0) as visited.
  3. Initialize score to grid[0][0] (the running minimum along the current best path).
  4. Pop the cell with the largest value from the heap.
  5. Update score = min(score, value of popped cell).
  6. If the popped cell is (m-1,n-1), return score.
  7. For each unvisited neighbor, add it to the heap and mark it as visited.
  8. Repeat from step 4.

Example Walkthrough

1Start: Push (0,0)=5 to max-heap. score=5
0
1
2
0
pop 5
5
4
5
1
1
2
6
2
7
4
6
1/6

Code

The log factor here comes from the heap operations. The next approach replaces the heap with a one-time sort and a Union-Find structure that tracks connectivity as cells are added.

Approach 3: Sort + Union-Find (Optimal)

Intuition

This approach builds the grid up instead of searching it. Add cells one at a time in decreasing order of value, starting with the highest. At some point an added cell connects (0,0) to (m-1,n-1) for the first time, and the value of that cell is the answer.

The reason that value is the answer: when cells are added in decreasing order, every cell added so far has value >= the current one. So the moment start and end become connected, the connecting path consists entirely of cells with value >= the current cell's value, and the current cell is the smallest among them. No path could have a higher minimum, since any earlier connection would have been detected at a higher value.

Union-Find (Disjoint Set Union) tracks the connectivity as cells are added. Each added cell is unioned with its already-added neighbors, and after each step we check whether (0,0) and (m-1,n-1) share a component. The first step where they do gives the answer.

Algorithm

  1. Collect all cells as (value, row, col) tuples and sort them in decreasing order of value.
  2. Initialize a Union-Find structure with m * n elements.
  3. Create a boolean grid added to track which cells have been added so far.
  4. Iterate through the sorted cells. For each cell:
    • Mark it as added.
    • For each of its four neighbors, if the neighbor has already been added, union the current cell with the neighbor.
    • Check if (0,0) and (m-1,n-1) are in the same component. If yes, return the current cell's value.
  5. Return 0 (fallback, should not be reached for valid inputs).

Example Walkthrough

1Sorted cells (desc): 7, 6, 6, 5, 5, 4, 4, 2, 1. Add highest first.
0
1
2
0
1
2
1/6

Code