LeetCode Solutions Blog

Minimize Maximum Value in a Grid

Number: 2506

Difficulty: Hard

Paid? Yes

Companies: Google

Problem Description

Given an m x n matrix of distinct positive integers, replace each integer with a positive integer so that:

For any two elements in the same row or same column, if one element was originally greater than the other then it must remain greater after the change.
The maximum number in the resulting matrix is as small as possible. Return any valid resulting matrix.

Key Insights

The relative order per row and per column must be preserved.
You want to assign the smallest possible positive integers while satisfying row/column ordering constraints.
The problem is equivalent to “Matrix Rank Transformation”. The idea is to assign a “rank” to each cell that is at least one larger than the maximum rank seen so far in its row and column.
Process the cells in increasing order, grouping by equal values (here groups are trivial since values are distinct, but the approach generalizes).
For each group, use union-find to merge cells in the same row or column so that they share the same rank based on the maximum current rank in that row or column.
Update row- and column-wise maximum ranks after assigning each group’s rank.

Space and Time Complexity

Time Complexity: O(m * n * log(m*n)) (dominated by sorting the cells and union-find operations) Space Complexity: O(m * n) (to store the result, rank arrays, and union-find data structures)

Solution

The core idea is to compute a rank for each cell such that the rank is one more than the maximum rank already seen in the same row or column. We first sort the cells by their original values so that when processing a cell all smaller cells (in row or column) have already been processed. Then, we process the cells in groups of equal value. For each group, we use union-find to merge cells that are in the same row or column. Once merged, the rank for the whole group is determined by taking the maximum of the current row or column rank among all cells in that group and adding one. Finally, we update the row and column maximum ranks for each cell in the group using the computed rank. This guarantees that the relative ordering is preserved and that the maximum assigned value is minimized.

Data Structures and Algorithms Used:

Sorting: To process the cells in increasing order of value.
Union Find: To group cells in the same row or column that appear in the same sorted group.
Arrays for row and column maximum ranks: To keep track of the best rank assigned so far for each row and column.

Code Solutions

# Python solution using union-find
class UnionFind:
    def __init__(self):
        self.parent = {}

    def find(self, x):
        # Path compression find
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        # Union two sets by pointing one root to another
        rootX, rootY = self.find(x), self.find(y)
        if rootX != rootY:
            self.parent[rootY] = rootX

def minimize_max_value_in_grid(grid):
    m, n = len(grid), len(grid[0])
    
    # result matrix
    answer = [[0] * n for _ in range(m)]
    # track maximum rank assigned so far for each row and column
    rowMax = [0] * m
    colMax = [0] * n
    
    # build list of (value, row, col) for sorting
    cells = [(grid[r][c], r, c) for r in range(m) for c in range(n)]
    cells.sort()
    
    i = 0
    while i < len(cells):
        # process group with same value
        same_value_group = []
        current_value = cells[i][0]
        while i < len(cells) and cells[i][0] == current_value:
            same_value_group.append(cells[i])
            i += 1
        
        uf = UnionFind()
        # Initialize union-find for each cell in this group
        for _, r, c in same_value_group:
            uf.parent[(r, c)] = (r, c)
        
        # dictionaries to store first cell in each row and column for current group
        row_lookup = {}
        col_lookup = {}
        
        # Merge cells in the same row or column within the current group
        for _, r, c in same_value_group:
            if r in row_lookup:
                uf.union((r, c), row_lookup[r])
            else:
                row_lookup[r] = (r, c)
            if c in col_lookup:
                uf.union((r, c), col_lookup[c])
            else:
                col_lookup[c] = (r, c)
        
        # Group cells by their union-find root
        groups = {}
        for _, r, c in same_value_group:
            root = uf.find((r, c))
            if root not in groups:
                groups[root] = []
            groups[root].append((r, c))
        
        # Compute rank for each group and update answer
        for group_cells in groups.values():
            # Determine new rank as one more than maximum rank among all of the group's rows and columns
            new_rank = 0
            for r, c in group_cells:
                new_rank = max(new_rank, rowMax[r], colMax[c])
            new_rank += 1
            for r, c in group_cells:
                answer[r][c] = new_rank
                rowMax[r] = max(rowMax[r], new_rank)
                colMax[c] = max(colMax[c], new_rank)
                
    return answer

# Example usage:
grid = [[3, 1], [2, 5]]
print(minimize_max_value_in_grid(grid))  # Output: [[2, 1], [1, 2]] or any valid configuration