DSA problem
Path With Maximum Minimum Value
Given an m x n integer matrix grid, return the maximum score of a path going from (0, 0) to (m - 1, n - 1) moving in the 4 cardinal directions. The score of a path is the minimum value in that path; we want to find the path whose minimum value is as large as possible.
The objective is unusual — instead of minimizing total cost we want to maximize the bottleneck. The trick is to reverse the usual Dijkstra mindset. Think of the cost of moving onto a cell as that cell's value, and define a path's "score" as the minimum cost so far. We want the path that maximizes this running minimum.
A clean implementation uses a max-heap keyed by the running minimum. Start by pushing (grid[0][0], 0, 0) onto the heap. Repeatedly pop the cell with the largest known running minimum, mark it visited, and push each unvisited neighbour with the new running minimum equal to min(currentRunningMin, grid[nr][nc]). The first time we pop the destination, the popped value is the answer.
The algorithm is essentially Dijkstra with the relaxation step replaced by a maximum: we always extend the most promising path first, so when we reach the destination we are guaranteed it cannot be improved. Time is O(m * n * log(m * n)) because each cell is pushed onto the heap at most a constant number of times, and space is O(m * n) for the heap and visited matrix.
Examples
grid = [[5,4,5],[1,2,6],[7,4,6]]4grid = [[2,2,1,2,2,2],[1,2,2,2,1,2]]2grid = [[3,4,6,3,4],[0,2,1,1,7],[8,8,3,2,7],[3,2,4,9,8],[4,1,2,0,0],[4,6,5,4,3]]3Constraints
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 100
- 0 <= grid[i][j] <= 10^9
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.