MediumNo. 1102LeetCode Premium
Path With Maximum Minimum Value — LeetCode 1102 Python Solution
- Pattern
- Union-Find
- Topics
- Depth-First Search, Breadth-First Search, Union Find, Array, Binary Search, Matrix, Heap (Priority Queue)
- Reading time
- 4 min
- Source
- leetcode.com
The problem
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.
Example
- Input
- grid = [[5,4,5],[1,2,6],[7,4,6]]
- Output
- 4
- Explanation
- The path with the maximum score is highlighted in yellow.
Python solution
class Solution:
def maximumMinimumPath(self, grid: List[List[int]]) -> int:
def find(x: int) -> int:
if p[x] != x:
p[x] = find(p[x])
return p[x]
m, n = len(grid), len(grid[0])
p = list(range(m * n))
q = [(v, i, j) for i, row in enumerate(grid) for j, v in enumerate(row)]
q.sort()
ans = 0
dirs = (-1, 0, 1, 0, -1)
vis = set()
while find(0) != find(m * n - 1):
v, i, j = q.pop()
ans = v
vis.add((i, j))
for a, b in pairwise(dirs):
x, y = i + a, j + b
if (x, y) in vis:
p[find(i * n + j)] = find(x * n + y)
return ansComplexity
- Time
- O(m × n × (log (m × n) + α(m × n))), where m and n are the number of rows and columns of the matrix, respectively
- Space · auxiliary
- O(1)
Pattern: Union-Find
Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 1102. Path With Maximum Minimum Value is filed here because LeetCode tags it Union Find, which is the vocabulary this hub collects.
The union-find guide has the Python template for the pattern and the 83 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0778 | Swim in Rising Water | Hard |
| 1631 | Path With Minimum Effort | Medium |
| 1970 | Last Day Where You Can Still Cross | Hard |
| 2812 | Find the Safest Path in a Grid | Medium |
| 0378 | Kth Smallest Element in a Sorted Matrix | Medium |
| 1337 | The K Weakest Rows in a Matrix | Easy |
Frequently asked questions
- How hard is LeetCode 1102. Path With Maximum Minimum Value?
LeetCode 1102. Path With Maximum Minimum Value is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1102. Path With Maximum Minimum Value?
The Python solution on this page runs in O(m \times n \times (\log (m \times n) + \alpha(m \times n))), where m and n are the number of rows and columns of the matrix, respectively.
- What is the space complexity of LeetCode 1102. Path With Maximum Minimum Value?
The Python solution on this page uses O(1) auxiliary space.
- What topics does LeetCode 1102. Path With Maximum Minimum Value cover?
LeetCode 1102. Path With Maximum Minimum Value is tagged Depth-First Search, Breadth-First Search, Union Find, Array, Binary Search, Matrix and Heap (Priority Queue) on LeetCode.
- Is LeetCode 1102. Path With Maximum Minimum Value a premium problem?
Yes. LeetCode 1102. Path With Maximum Minimum Value is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.