LeetCode 2371 - Minimize Maximum Value in a Grid

The problem presents a matrix grid of size m x n with distinct positive integers. The goal is to transform this matrix so that every element is replaced with another positive integer while maintaining the relative order in each row and column.

leetcodehardarrayunion-findgraph-theorytopological-sortsortingmatrix

LeetCode Problem 2371

Difficulty: 🔴 Hard
Topics: Array, Union-Find, Graph Theory, Topological Sort, Sorting, Matrix

Solution

Problem Understanding

The problem presents a matrix grid of size m x n with distinct positive integers. The goal is to transform this matrix so that every element is replaced with another positive integer while maintaining the relative order in each row and column. This means that if an element was larger than another in the same row or column originally, it must remain larger after the transformation. Among all possible transformations, the matrix's maximum value should be minimized.

In simpler terms, you want to "compress" the matrix values while preserving row and column order. For example, if a row has [3,1,5], you could map it to [2,1,3] as long as the order 3>1<5 is preserved.

The constraints suggest that m and n can each go up to 1000, and the total number of elements is up to 105. Since grid contains distinct integers, we do not need to handle equal values, simplifying the ordering logic. Important edge cases include single-element matrices, rows or columns with consecutive numbers, and matrices where minimum and maximum values appear in different rows and columns.

Approaches

A brute-force approach would be to try all possible positive integer replacements and verify the order in rows and columns. While this guarantees correctness, the number of permutations is astronomically large (O((max(grid))^(m*n))) and infeasible given the constraints.

The key insight for an optimal approach is that this problem can be modeled using graph theory. Each matrix element can be treated as a node. If an element a is larger than b in the same row or column, we can add a directed edge b -> a, indicating b must get a smaller or equal number than a. Once we have all edges, we effectively have a Directed Acyclic Graph (DAG) because the matrix has distinct numbers and comparisons are strict. The problem now reduces to assigning the smallest possible integer to each node while respecting all DAG edges, which can be solved using a topological sort combined with dynamic programming to assign ranks incrementally.

Approach Time Complexity Space Complexity Notes
Brute Force O((max(grid))^(m*n)) O(m*n) Try all possible replacements, impractical for large inputs
Optimal O(m_n * log(m_n)) O(m*n) Use sorting, topological constraints, and union-find or row/column rank tracking

Algorithm Walkthrough

  1. Flatten the matrix into a list of (value, row, column) tuples to process the elements in increasing order of value.
  2. Initialize two arrays, row_max and col_max, to keep track of the current maximum rank assigned to each row and column.
  3. Sort the flattened list by the value in ascending order.
  4. Iterate through the sorted elements. For each element at (r, c):
  • The new value assigned to grid[r][c] should be max(row_max[r], col_max[c]) + 1. This ensures the relative order is maintained.
  • Update row_max[r] and col_max[c] to this new value.
  1. After processing all elements, the matrix has been transformed, and the maximum value is minimized.
  2. Return the resulting matrix.

Why it works: By processing elements from smallest to largest and assigning a rank based on the maximum rank seen so far in its row or column, the algorithm guarantees that all relative order constraints are satisfied. Each element gets the smallest possible number consistent with the constraints, minimizing the global maximum.

Python Solution

from typing import List

class Solution:
    def minScore(self, grid: List[List[int]]) -> List[List[int]]:
        m, n = len(grid), len(grid[0])
        row_max = [0] * m
        col_max = [0] * n
        result = [[0] * n for _ in range(m)]
        
        # Flatten grid with coordinates and sort by value
        elements = sorted([(grid[r][c], r, c) for r in range(m) for c in range(n)])
        
        for value, r, c in elements:
            rank = max(row_max[r], col_max[c]) + 1
            result[r][c] = rank
            row_max[r] = rank
            col_max[c] = rank
        
        return result

Implementation walkthrough: The row_max and col_max arrays track the largest number assigned in each row and column so far. Sorting ensures we process smaller elements first, which is critical to maintaining the relative order. Assigning rank = max(row_max[r], col_max[c]) + 1 guarantees that the new number is strictly greater than all smaller numbers in the same row or column.

Go Solution

func minScore(grid [][]int) [][]int {
    m, n := len(grid), len(grid[0])
    rowMax := make([]int, m)
    colMax := make([]int, n)
    result := make([][]int, m)
    for i := range result {
        result[i] = make([]int, n)
    }

    type Element struct {
        val, r, c int
    }
    elements := make([]Element, 0, m*n)
    for r := 0; r < m; r++ {
        for c := 0; c < n; c++ {
            elements = append(elements, Element{grid[r][c], r, c})
        }
    }

    sort.Slice(elements, func(i, j int) bool {
        return elements[i].val < elements[j].val
    })

    for _, e := range elements {
        rank := max(rowMax[e.r], colMax[e.c]) + 1
        result[e.r][e.c] = rank
        rowMax[e.r] = rank
        colMax[e.c] = rank
    }

    return result
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Go-specific notes: We define a struct Element to store value and coordinates. sort.Slice is used for sorting. The logic is identical to Python. Slices are preallocated to avoid repeated appends. The max helper function simplifies rank assignment.

Worked Examples

Example 1: grid = [[3,1],[2,5]]

Flatten and sort: [(1,0,1),(2,1,0),(3,0,0),(5,1,1)]

Step Element row_max col_max rank result
1 1 at (0,1) [0,0] [0,0] 1 [[0,1],[0,0]]
2 2 at (1,0) [0,0] [0,0] 1 [[0,1],[1,0]]
3 3 at (0,0) [1,0] [1,0] 2 [[2,1],[1,0]]
4 5 at (1,1) [2,1] [2,1] 2 [[2,1],[1,2]]

Example 2: grid = [[10]]

Only one element, rank = 1, result = [[1]].

Complexity Analysis

Measure Complexity Explanation
Time O(m_n_log(m*n)) Sorting all elements dominates the time complexity
Space O(m*n) Storing flattened elements and the result matrix

The algorithm scales efficiently for matrices up to 10^5 elements, and only requires linear extra space beyond the output.

Test Cases

# Provided examples
assert Solution().minScore([[3,1],[2,5]]) == [[2,1],[1,2]]  # example 1
assert Solution().minScore([[10]]) == [[1]]  # example 2

# Edge and larger cases
assert Solution().minScore([[1,2,3],[4,5,6]]) == [[1,2,3],[2,3,4]]  # ascending rows/cols
assert Solution().minScore([[6,1],[3,2]]) == [[2,1],[1,2]]  # mixed order
assert Solution().minScore([[100,50],[70,20]]) == [[2,1],[2,1]]  # larger numbers
assert Solution().minScore([[1]]) == [[1]]  # single element
Test Why
[[3,1],[2,5]] Validates general 2x2 replacement logic
[[10]] Single-element matrix
[[1,2,3],[4,5,6]] Ascending numbers across rows/columns
[[6,1],[3,2]] Random order matrix
[[100,50],[70,20]] Large numbers
[[1]] Minimum boundary

Edge Cases

  1. Single-element matrix: The matrix contains only one number. The algorithm handles it by assigning rank 1. This is the minimum possible maximum by definition.
  2. **Row or column