Minimize Maximum Value in a Grid

class Solution {
public:
    vector<vector<int>> minScore(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<tuple<int,int,int>> cells;
        cells.reserve(m * n);
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                cells.push_back({grid[i][j], i, j});
        sort(cells.begin(), cells.end());
        vector<int> rowMax(m, 0), colMax(n, 0);
        vector<vector<int>> ans(m, vector<int>(n, 0));
        for (auto& [_, i, j] : cells) {
            int v = max(rowMax[i], colMax[j]) + 1;
            ans[i][j] = v;
            rowMax[i] = colMax[j] = v;
        }
        return ans;
    }
};

func minScore(grid [][]int) [][]int {
    m, n := len(grid), len(grid[0])
    type cell struct{ v, i, j int }
    cells := make([]cell, 0, m*n)
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            cells = append(cells, cell{grid[i][j], i, j})
        }
    }
    sort.Slice(cells, func(a, b int) bool { return cells[a].v < cells[b].v })
    rowMax := make([]int, m)
    colMax := make([]int, n)
    ans := make([][]int, m)
    for i := range ans {
        ans[i] = make([]int, n)
    }
    for _, c := range cells {
        v := rowMax[c.i]
        if colMax[c.j] > v {
            v = colMax[c.j]
        }
        v++
        ans[c.i][c.j] = v
        rowMax[c.i] = v
        colMax[c.j] = v
    }
    return ans
}

from typing import List

class Solution:
    def minScore(self, grid: List[List[int]]) -> List[List[int]]:
        m, n = len(grid), len(grid[0])
        cells = []
        for i in range(m):
            for j in range(n):
                cells.append((grid[i][j], i, j))
        cells.sort()
        row_max = [0] * m
        col_max = [0] * n
        ans = [[0] * n for _ in range(m)]
        for _, i, j in cells:
            v = max(row_max[i], col_max[j]) + 1
            ans[i][j] = v
            row_max[i] = v
            col_max[j] = v
        return ans

function minScore(grid) {
    const m = grid.length, n = grid[0].length;
    const cells = [];
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            cells.push([grid[i][j], i, j]);
        }
    }
    cells.sort((a, b) => a[0] - b[0]);
    const rowMax = new Array(m).fill(0);
    const colMax = new Array(n).fill(0);
    const ans = Array.from({ length: m }, () => new Array(n).fill(0));
    for (const [, i, j] of cells) {
        const v = Math.max(rowMax[i], colMax[j]) + 1;
        ans[i][j] = v;
        rowMax[i] = v;
        colMax[j] = v;
    }
    return ans;
}

class Solution {
    public int[][] minScore(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] cells = new int[m * n][3];
        int idx = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                cells[idx][0] = grid[i][j];
                cells[idx][1] = i;
                cells[idx][2] = j;
                idx++;
            }
        }
        Arrays.sort(cells, (a, b) -> a[0] - b[0]);
        int[] rowMax = new int[m];
        int[] colMax = new int[n];
        int[][] ans = new int[m][n];
        for (int[] c : cells) {
            int v = Math.max(rowMax[c[1]], colMax[c[2]]) + 1;
            ans[c[1]][c[2]] = v;
            rowMax[c[1]] = v;
            colMax[c[2]] = v;
        }
        return ans;
    }
}

function minScore(grid: number[][]): number[][] {
    const m = grid.length, n = grid[0].length;
    const cells: [number, number, number][] = [];
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            cells.push([grid[i][j], i, j]);
        }
    }
    cells.sort((a, b) => a[0] - b[0]);
    const rowMax: number[] = new Array(m).fill(0);
    const colMax: number[] = new Array(n).fill(0);
    const ans: number[][] = Array.from({ length: m }, () => new Array(n).fill(0));
    for (const [, i, j] of cells) {
        const v = Math.max(rowMax[i], colMax[j]) + 1;
        ans[i][j] = v;
        rowMax[i] = v;
        colMax[j] = v;
    }
    return ans;
}