Skip to main content
Talentd

Minimize Maximum Value in a Grid - Solution & Explanation

HardPremiumFree on FleetCodeArrayUnion FindGraphTopological Sort5 min readAsked at: Google
Practice this problem

Problem Statement

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[r1][c1] > grid[r2][c2] where either r1 == r2 or c1 == c2, then it must be true that grid[r1][c1] > grid[r2][c2] 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 <= 105
  • 1 <= grid[i][j] <= 109
  • grid consists of distinct integers.

Approach Overview

Problem Overview: You receive an m x n matrix. You must replace each cell with a positive integer so that ordering constraints in every row and column are preserved. If grid[i][j] < grid[x][y] in the same row or column, the assigned value must also be smaller. The objective is to minimize the maximum assigned value across the grid.

Approach 1: Row/Column Simulation (Brute Force) (Time: O((mn)^2), Space: O(mn))

A direct idea is to repeatedly compare every pair of cells that share a row or column and enforce ordering constraints. For each cell, compute the largest value required based on smaller elements in its row and column. This often requires reprocessing cells whenever a constraint changes, leading to quadratic behavior over all mn cells. The method models the dependency rules correctly but becomes impractical for large grids.

Approach 2: Graph Modeling + Topological Sort (Time: O(mn log(mn)), Space: O(mn))

Treat each cell as a node in a directed graph. If two cells share a row or column and one value is smaller, create a directed edge from the smaller to the larger node. After building the graph, perform topological sort and assign ranks in order of dependencies. The rank of a node becomes max(parent ranks) + 1. Sorting cells by value helps build edges efficiently. This models the constraint system explicitly but constructing all edges can still be expensive in dense rows and columns.

Approach 3: Sorting + Union Find on Rows and Columns (Optimal) (Time: O(mn log(mn)), Space: O(m+n))

Process cells in ascending order of their original values using sorting. Cells with the same value must be processed together because they should receive the same rank relative to existing constraints. For each value group, connect its row and column indices using Union Find. Each connected component represents cells that must share the same rank level. Compute the rank for a component as max(rowRank[r], colRank[c]) + 1 across its members. After assigning ranks, update the row and column maximum ranks. This avoids building a full dependency graph and keeps operations near linear after sorting.

Recommended for interviews: The Union Find + sorting approach is what interviewers typically expect. The brute force explanation demonstrates you understand the ordering constraints, but the optimized method shows you can compress dependencies and avoid building a full graph. It scales cleanly to large matrices and combines sorting, union-find, and rank propagation in a concise implementation.

Solution

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Row/Column Simulation (Brute Force)O((mn)^2)O(mn)Useful for understanding ordering constraints and validating logic on small grids
Graph + Topological SortO(mn log(mn))O(mn)When modeling dependencies explicitly as a DAG between cells
Sorting + Union Find (Optimal)O(mn log(mn))O(m+n)Best general solution for large matrices; avoids building a full dependency graph

Video Solution

Leetcode 2371. Minimize Maximum Value in a Grid - reset from positions with smaller values to larger • Code-Yao • 658 views views

Watch 4 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Minimize Maximum Value in a Grid with our built-in code editor and test cases.

Practice on FleetCode
Previous

Candy