Minimize Maximum Value in a Grid - Practice Coding Problems

Minimize Maximum Value in a Grid - Problem

Array Union Find Graph Topological Sort Sorting Matrix Hard

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:

1. The relative order of every two elements that are in the same row or column should stay the same after the replacements.

2. 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.

Input & Output

Example 1 — Basic Grid

$ Input: grid = [[2,4,5],[7,3,9]]

› Output: [[1,2,3],[2,1,4]]

💡 Note: Process elements by value: 2→rank 1, 3→rank 1, 4→rank 2, 5→rank 3, 7→rank 2, 9→rank 4. Each rank respects row/column ordering constraints.

Example 2 — Single Row

$ Input: grid = [[1,3,2]]

› Output: [[1,3,2]]

💡 Note: In a single row, elements must maintain their relative order: 1 < 2 < 3, so the minimum assignment is [1,3,2].

Example 3 — Single Column

$ Input: grid = [[5],[2],[8]]

› Output: [[2],[1],[3]]

💡 Note: In a single column, we process 2→1, 5→2, 8→3 to maintain the constraint 2 < 5 < 8.

Constraints

m == grid.length
n == grid[i].length
1 ≤ m, n ≤ 1000
1 ≤ grid[i][j] ≤ 10⁹
All integers in grid are distinct

Visualization

Tap to expand

Understanding the Visualization

Input Grid

Original grid with distinct positive integers

Maintain Order

Preserve relative order within each row and column

Minimize Maximum

Assign smallest possible values while respecting constraints

Key Takeaway

🎯 Key Insight: Process elements in ascending order and assign each the minimum rank that respects existing row/column maximums

Asked in

G Google 15 a Amazon 8 M Microsoft 6

The key insight is to process elements in sorted order and assign each the minimum rank that maintains row/column ordering constraints. Use coordinate compression: for each element, assign max(current_row_max, current_col_max) + 1. Best approach is coordinate compression with Time: O(mn log(mn)), Space: O(mn).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Constraint Checking	O((mn)!)	O(mn)	Try all possible value assignments and verify constraints
Coordinate Compression with Union-Find	O(mn log(mn))	O(mn)	Use union-find to group connected elements and assign minimum ranks

Brute Force Constraint Checking — Algorithm Steps

Step 1: Generate all permutations of values 1 to m*n
Step 2: For each permutation, check if it satisfies row and column ordering constraints
Step 3: Return the first valid assignment found

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Permutations

Create all possible ways to assign values 1-6

Check Constraints

Verify each assignment maintains row/column order

Return Valid

Return first assignment that satisfies all constraints

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int i, j, val;
} Position;

int compare(const void* a, const void* b) {
    Position* pa = (Position*)a;
    Position* pb = (Position*)b;
    return pa->val - pb->val;
}

int** solution(int** grid, int gridSize, int* gridColSize, int* returnSize, int** returnColumnSizes) {
    int m = gridSize, n = gridColSize[0];
    Position* positions = malloc(m * n * sizeof(Position));
    int idx = 0;
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            positions[idx++] = (Position){i, j, grid[i][j]};
        }
    }
    
    qsort(positions, m * n, sizeof(Position), compare);
    
    int** result = malloc(m * sizeof(int*));
    *returnColumnSizes = malloc(m * sizeof(int));
    *returnSize = m;
    
    for (int i = 0; i < m; i++) {
        result[i] = malloc(n * sizeof(int));
        (*returnColumnSizes)[i] = n;
    }
    
    for (int i = 0; i < m * n; i++) {
        result[positions[i].i][positions[i].j] = i + 1;
    }
    
    free(positions);
    return result;
}

int main() {
    // Simplified for demonstration
    int grid_data[2][3] = {{2, 4, 5}, {7, 3, 9}};
    int* grid[2] = {grid_data[0], grid_data[1]};
    int gridColSize[2] = {3, 3};
    int returnSize;
    int* returnColumnSizes;
    
    int** result = solution(grid, 2, gridColSize, &returnSize, &returnColumnSizes);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        if (i > 0) printf(",");
        printf("[");
        for (int j = 0; j < returnColumnSizes[i]; j++) {
            if (j > 0) printf(",");
            printf("%d", result[i][j]);
        }
        printf("]");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O((mn)!)

Generate all permutations of mn elements and check each one

✓ Linear Growth

Space Complexity

O(mn)

Store the current permutation and result matrix

⚡ Linearithmic Space

15.6K Views

Medium Frequency

~35 min Avg. Time

425 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Constraint Checking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler