How hard is LeetCode 2371. Minimize Maximum Value in a Grid?

LeetCode 2371. Minimize Maximum Value in a Grid is rated Hard on LeetCode.

What is the time complexity of LeetCode 2371. Minimize Maximum Value in a Grid?

The Python solution on this page runs in O(V+E).

What is the space complexity of LeetCode 2371. Minimize Maximum Value in a Grid?

The Python solution on this page uses O(V) auxiliary space.

What topics does LeetCode 2371. Minimize Maximum Value in a Grid cover?

LeetCode 2371. Minimize Maximum Value in a Grid is tagged Union Find, Graph, Topological Sort, Array, Matrix and Sorting on LeetCode.

Is LeetCode 2371. Minimize Maximum Value in a Grid a premium problem?

Yes. LeetCode 2371. Minimize Maximum Value in a Grid is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Minimize Maximum Value in a Grid — LeetCode 2371 Python Solution

HardLeetCode PremiumUnion FindGraphTopological SortArrayMatrixSorting

Problem: #2371
Pattern: Topological Sort
Reading time: 2 min
Source: leetcode.com

The problem

You are given an m x n integer matrix grid containing distinct positive integers. You have to replace each integer in the matrix with a positive integer satisfying the following conditions: The relative order of every two elements that are in the same row or column should stay the same after the replacements.

Example

Input: grid = [[3,1],[2,5]]
Output: [[2,1],[1,2]]
Explanation: The above diagram shows a valid replacement.

Python solution

Python

class Solution:
    def minScore(self, grid: List[List[int]]) -> List[List[int]]:
        m, n = len(grid), len(grid[0])
        nums = [(v, i, j) for i, row in enumerate(grid) for j, v in enumerate(row)]
        nums.sort()
        row_max = [0] * m
        col_max = [0] * n
        ans = [[0] * n for _ in range(m)]
        for _, i, j in nums:
            ans[i][j] = max(row_max[i], col_max[j]) + 1
            row_max[i] = col_max[j] = ans[i][j]
        return ans

Complexity

Measure	Complexity
Time	O(V+E)
Space	O(V) auxiliary

Pattern: Topological Sort

Order a set of tasks so that every dependency comes before the thing that needs it. LeetCode 2371. Minimize Maximum Value in a Grid is filed here because LeetCode tags it Topological Sort, which is the vocabulary this hub collects.

The topological sort guide has the Python template for the pattern and the 32 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 2371. Minimize Maximum Value in a Grid?: LeetCode 2371. Minimize Maximum Value in a Grid is rated Hard on LeetCode.
What is the time complexity of LeetCode 2371. Minimize Maximum Value in a Grid?: The Python solution on this page runs in O(V+E).
What is the space complexity of LeetCode 2371. Minimize Maximum Value in a Grid?: The Python solution on this page uses O(V) auxiliary space.
What topics does LeetCode 2371. Minimize Maximum Value in a Grid cover?: LeetCode 2371. Minimize Maximum Value in a Grid is tagged Union Find, Graph, Topological Sort, Array, Matrix and Sorting on LeetCode.
Is LeetCode 2371. Minimize Maximum Value in a Grid a premium problem?: Yes. LeetCode 2371. Minimize Maximum Value in a Grid is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.