Minimize Maximum Value in a Grid - Video Solutions

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.