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.

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.

Path With Maximum Minimum Value — LeetCode 1102 Python Solution

MediumLeetCode PremiumDepth-First SearchBreadth-First SearchUnion FindArrayBinary SearchMatrixHeap (Priority Queue)

Problem: #1102
Pattern: Union-Find
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

Python

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 ans

Complexity

Measure	Complexity
Time	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
Space	O(1) auxiliary

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.

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.