Is Minimize Maximum Value in a Grid easy or hard?

LeetCode classifies this problem as Hard because it combines multiple concepts: sorting, Union Find, and dependency ranking across matrix rows and columns. The challenge is recognizing that equal values must be processed together and that row/column constraints can be compressed using DSU.

Minimize Maximum Value in a Grid Python/Java solution

Python and Java implementations typically sort all cells by value, group equal values, union their row and column indices, compute the rank for each component, and update rowRank and colRank arrays. The algorithm runs in O(mn log(mn)) time and uses Union Find with path compression.

How to solve Minimize Maximum Value in a Grid in O(n)?

A strictly O(n) solution is not practical because the algorithm must examine and order all mn cells. The closest optimal approach sorts cells and then processes them using Union Find, giving O(mn log(mn)) time. Sorting is required to ensure constraints are applied in increasing value order.

What is the best approach for Minimize Maximum Value in a Grid?

The most efficient approach sorts cells by value and processes equal values together while using Union Find to connect rows and columns. Each connected component receives rank max(rowRank, colRank) + 1. This avoids building a full dependency graph and runs in O(mn log(mn)) time with O(m+n) space.

Is Minimize Maximum Value in a Grid asked at Google/Amazon/Meta?

Problems combining Union Find, matrix processing, and topological dependency reasoning appear frequently in interviews at companies like Google, Amazon, and Meta. Variants of rank assignment or dependency ordering across rows and columns test graph modeling and data structure knowledge.

What data structure is used in Minimize Maximum Value in a Grid?

The core data structures are Union Find (Disjoint Set Union) to group rows and columns for equal values, arrays to track row and column ranks, and sorting for processing cells in ascending order. Together they enforce ordering constraints efficiently.

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

The optimal solution runs in O(mn log(mn)) time due to sorting all grid cells by value. Union Find operations and rank updates are nearly constant time with path compression. Space complexity is O(m+n) for tracking row and column ranks plus temporary grouping.

Description Hints 2 Solution Video 9:34

2371. Minimize Maximum Value in a Grid

Hard70.1% acceptance1 companyPremium elsewhere, free here

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.
The maximum number in the matrix after the replacements should be as small as possible.

The relative order stays the same if for all pairs of elements in the original matrix such that grid[r₁][c₁] > grid[r₂][c₂] where either r₁ == r₂ or c₁ == c₂, then it must be true that grid[r₁][c₁] > grid[r₂][c₂] after the replacements.

For example, if grid = [[2, 4, 5], [7, 3, 9]] then a good replacement could be either grid = [[1, 2, 3], [2, 1, 4]] or grid = [[1, 2, 3], [3, 1, 4]].

Return the resulting matrix. If there are multiple answers, return any of them.

Example 1:

Input: grid = [[3,1],[2,5]]
Output: [[2,1],[1,2]]
Explanation: The above diagram shows a valid replacement.
The maximum number in the matrix is 2. It can be shown that no smaller value can be obtained.

Example 2:

Input: grid = [[10]]
Output: [[1]]
Explanation: We replace the only number in the matrix with 1.

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 1000
1 <= m * n <= 10⁵
1 <= grid[i][j] <= 10⁹
grid consists of distinct integers.

Asked at 1 company

Google

Topics

Hints open one at a time

Hint 1

Can you think of which element in the grid you should replace first?

Hint 2

Replace the elements in the matrix from the smallest number to the largest. Replace each element with the smallest possible number so far.

9:34

Still stuck?Read the written solution, or watch a walkthrough.

Open solution