2033. Minimum Operations to Make a Uni-Value Grid

Array
Math
Sorting
Matrix

TIME

O(mn * log(mn))

SPACE

O(mn)

Intuition

All elements must have the same remainder mod x (otherwise impossible)
Target value should be the median (minimizes sum of absolute differences)
Operations = Σ |element - median| / x

Solution

Why Median?

The median minimizes the sum of absolute deviations. Classic result from statistics.

For any value v, the total cost is Σ|arr[i] - v|. This is minimized when v = median.

Algorithm

# Flatten grid
arr = [val for row in grid for val in row]

# Check all have same remainder
if not all(val % x == arr[0] % x for val in arr):
    return -1

# Sort and find median
arr.sort()
median = arr[len(arr) // 2]

# Count operations
return sum(abs(val - median) // x for val in arr)

Complexity

Time: O(mn log(mn)) for sorting
Space: O(mn) for flattened array

Edge Cases

Single element → 0 operations
All elements equal → 0 operations
Different remainders → impossible (-1)

Code

from typing import List


class Solution:
    def minOperations(self, grid: List[List[int]], x: int) -> int:
        """
        2033. Minimum Operations to Make a Uni-Value Grid
        Time: O(mn * log(mn))
        Space: O(mn)
        """
        # Flatten grid
        arr = [val for row in grid for val in row]

        # Check if all elements have the same remainder mod x
        remainder = arr[0] % x
        for val in arr:
            if val % x != remainder:
                return -1

        # Sort and find median
        arr.sort()
        median = arr[len(arr) // 2]

        # Count total operations
        operations = sum(abs(val - median) // x for val in arr)

        return operations

import java.util.*;

/**
 * 2033. Minimum Operations to Make a Uni-Value Grid
 * Time: O(mn * log(mn))
 * Space: O(mn)
 */
class Solution {
    public int minOperations(int[][] grid, int x) {
        int m = grid.length, n = grid[0].length;
        int[] arr = new int[m * n];

        // Flatten grid
        int idx = 0;
        int remainder = grid[0][0] % x;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] % x != remainder) {
                    return -1;
                }
                arr[idx++] = grid[i][j];
            }
        }

        // Sort and find median
        Arrays.sort(arr);
        int median = arr[arr.length / 2];

        // Count total operations
        int operations = 0;
        for (int val : arr) {
            operations += Math.abs(val - median) / x;
        }

        return operations;
    }
}