Skip to content

2371. Minimize Maximum Value in a Grid 👍

  • Time: $O(mn)$
  • Space: $O(mn)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
 public:
  vector<vector<int>> minScore(vector<vector<int>>& grid) {
    const int m = grid.size();
    const int n = grid[0].size();
    vector<vector<int>> ans(m, vector<int>(n));
    vector<array<int, 3>> valAndIndices;
    vector<int> rows(m);  // rows[i] := the maximum used number so far
    vector<int> cols(n);  // cols[j] := the maximum used number so far

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        valAndIndices.push_back({grid[i][j], i, j});

    ranges::sort(valAndIndices);

    for (const auto& [_, i, j] : valAndIndices) {
      const int nextAvailable = max(rows[i], cols[j]) + 1;
      ans[i][j] = nextAvailable;
      rows[i] = nextAvailable;
      cols[j] = nextAvailable;
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
  public int[][] minScore(int[][] grid) {
    final int m = grid.length;
    final int n = grid[0].length;
    int[][] ans = new int[m][n];
    List<int[]> valAndIndices = new ArrayList<>();
    int[] rows = new int[m]; // rows[i] := the maximum used number so far
    int[] cols = new int[n]; // cols[j] := the maximum used number so far

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        valAndIndices.add(new int[] {grid[i][j], i, j});

    Collections.sort(valAndIndices, new Comparator<int[]>() {
      @Override
      public int compare(int[] a, int[] b) {
        return Integer.compare(a[0], b[0]);
      }
    });

    for (int[] valAndIndex : valAndIndices) {
      final int i = valAndIndex[1];
      final int j = valAndIndex[2];
      final int nextAvailable = Math.max(rows[i], cols[j]) + 1;
      ans[i][j] = nextAvailable;
      rows[i] = nextAvailable;
      cols[j] = nextAvailable;
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
  def minScore(self, grid: list[list[int]]) -> list[list[int]]:
    m = len(grid)
    n = len(grid[0])
    ans = [[0] * n for _ in range(m)]
    valAndIndices = []
    rows = [0] * m  # rows[i] := the maximum used number so far
    cols = [0] * n  # cols[j] := the maximum used number so far

    for i in range(m):
      for j in range(n):
        valAndIndices.append((grid[i][j], i, j))

    valAndIndices.sort()

    for _, i, j in valAndIndices:
      nextAvailable = max(rows[i], cols[j]) + 1
      ans[i][j] = nextAvailable
      rows[i] = nextAvailable
      cols[j] = nextAvailable

    return ans