Skip to content

2033. Minimum Operations to Make a Uni-Value Grid 👍

  • Time: $O(mn)$ (C++), $O(mn\log mn)$ (Java/Python)
  • Space: $O(mn)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
 public:
  int minOperations(vector<vector<int>>& grid, int x) {
    vector<int> A;
    for (const vector<int>& row : grid)
      A.insert(A.end(), row.begin(), row.end());
    if (ranges::any_of(A, [&](int a) { return (a - A[0]) % x; }))
      return -1;

    int ans = 0;

    nth_element(A.begin(), A.begin() + A.size() / 2, A.end());

    for (const int a : A)
      ans += abs(a - A[A.size() / 2]) / x;

    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 {
  public int minOperations(int[][] grid, int x) {
    final int m = grid.length;
    final int n = grid[0].length;

    int[] A = new int[m * n];
    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        A[i * n + j] = grid[i][j];
    if (Arrays.stream(A).anyMatch(a -> (a - A[0]) % x != 0))
      return -1;

    int ans = 0;

    Arrays.sort(A);

    for (final int a : A)
      ans += Math.abs(a - A[A.length / 2]) / x;

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
  def minOperations(self, grid: List[List[int]], x: int) -> int:
    A = sorted([a for row in grid for a in row])
    if any((a - A[0]) % x for a in A):
      return -1

    ans = 0

    for a in A:
      ans += abs(a - A[len(A) // 2]) // x

    return ans