Path With Maximum Minimum Value - Video Solutions
1102. Path With Maximum Minimum Value | Medium | English
Path With Maximum Minimum Value - Video Solution
Watch 8 video solutions for Path With Maximum Minimum Value, a medium level problem involving Array, Binary Search, Depth-First Search. This walkthrough by Simple Code - 단순코드 has 4,484 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
Given an m x n integer matrix grid, return the maximum score of a path starting at (0, 0) and ending at (m - 1, n - 1) moving in the 4 cardinal directions.
The score of a path is the minimum value in that path.
- For example, the score of the path
8 → 4 → 5 → 9is4.
Example 1:
Input: grid = [[5,4,5],[1,2,6],[7,4,6]] Output: 4 Explanation: The path with the maximum score is highlighted in yellow.
Example 2:
Input: grid = [[2,2,1,2,2,2],[1,2,2,2,1,2]] Output: 2
Example 3:
Input: grid = [[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]] Output: 3
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 1000 <= grid[i][j] <= 109
Approach Overview
Problem Overview: Given an m × n grid, you start at (0,0) and must reach (m-1,n-1). Every path has a score defined by the minimum value encountered along that path. The goal is to choose the path whose minimum value is as large as possible.
Approach 1: Max Heap (Priority Queue) Search (O(mn log(mn)) time, O(mn) space)
This approach is a variation of Dijkstra’s algorithm on a grid. Instead of minimizing distance, you maximize the minimum value seen so far. Use a max heap (priority queue) that always expands the cell with the highest value first. Track the path score as the minimum value along the current path. Each time you pop a cell, update the score and push its four neighbors if they are unvisited. The first time you reach the bottom-right cell, the recorded score is the best possible. The greedy ordering works because exploring higher values first guarantees no later path can produce a better minimum.
This method resembles graph traversal using BFS with a priority queue. It is easy to implement and performs well for typical grid sizes.
Approach 2: Sorting + Union-Find (O(mn log(mn)) time, O(mn) space)
Think about the problem in reverse: instead of building a path, gradually allow cells from highest value to lowest. Sort all grid cells in descending order by value. As you activate each cell, connect it with its already-active neighbors using a Union-Find structure. The moment the start cell and end cell become connected, the current value is the maximum possible minimum value of a valid path.
The key insight: if you only allow cells with value ≥ x, you are effectively checking whether a path exists where every cell meets that threshold. Activating cells from largest to smallest guarantees that the first successful connection yields the optimal answer.
This approach turns the grid into a connectivity problem. Union-Find keeps the operations near constant time using path compression and union by rank.
Recommended for interviews: The max-heap search is the most intuitive and closest to classic graph algorithms, so many candidates reach it first. The sorting + Union-Find method demonstrates deeper insight into connectivity and threshold problems. Showing the heap approach first and then discussing the Union-Find optimization signals strong problem-solving range.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Max Heap (Priority Queue) Grid Search | O(mn log(mn)) | O(mn) | General solution. Intuitive if you think of the grid as a graph and apply Dijkstra-style traversal. |
| Sorting + Union-Find | O(mn log(mn)) | O(mn) | Best when reasoning about connectivity thresholds. Efficient and elegant for grid activation problems. |