Minimum Operations to Make a Uni-Value Grid

Problem

You are given a 2D integer grid of size m x n and an integer x. In one operation, you can add x to or subtract x from any element in the grid.

A uni-value grid is a grid where all the elements of it are equal.

Return the minimum number of operations to make the grid uni-value. If it is not possible, return -1.

Examples

Example 1:

Input: grid = [[2,4],[6,8]], x = 2
Output: 4
Explanation: We can make every element equal to 4 by doing the following: 
- Add x to 2 once.
- Subtract x from 6 once.
- Subtract x from 8 twice.
A total of 4 operations were used.

Example 2:

Input: grid = [[1,5],[2,3]], x = 1
Output: 5
Explanation: We can make every element equal to 3.

Example 3:

Input: grid = [[1,2],[3,4]], x = 2
Output: -1
Explanation: It is impossible to make every element equal.

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 10^5
• 1 <= m * n <= 10^5
• 1 <= x, grid[i][j] <= 10^4

Solution

Method 1 - Finding median

A grid is uni-value if all the elements equal the same value. For this to be possible, all the grid elements must have the same remainder when divided by x (i.e., grid[i][j] % x must be consistent). If this condition fails, return -1, as transforming the grid is impossible.

• Flatten the grid into a 1D list.
• Check divisibility, as explained above.
• Use the median of the flattened list to minimise operations (because the median minimises the sum of absolute differences in a sorted list).
• Calculate the total cost by summing the number of operations needed to adjust all elements to the median value.

Code

Java

class Solution {
    public int minOperations(int[][] grid, int x) {
        // Flatten the grid into 1D array
        List<Integer> flatGrid = new ArrayList<>();
        for (int[] row : grid) {
            for (int num : row) {
                flatGrid.add(num);
            }
        }
        
        // Check if all numbers are divisible consistently by x
        int remainder = flatGrid.get(0) % x;
        for (int num : flatGrid) {
            if (num % x != remainder) {
                return -1;
            }
        }
        
        // Sort the grid and find the median
        Collections.sort(flatGrid);
        int median = flatGrid.get(flatGrid.size() / 2);
        
        // Calculate the total operations
        int ans = 0;
        for (int num : flatGrid) {
            ans += Math.abs(num - median) / x;
        }
        return ans;
    }
}

Python

class Solution:
    def minOperations(self, grid: List[List[int]], x: int) -> int:
        # Flatten the grid into 1D list
        flat_grid = [num for row in grid for num in row]
        
        # Check if all numbers are divisible consistently by x
        remainder = flat_grid[0] % x
        if any(num % x != remainder for num in flat_grid):
            return -1
        
        # Sort the grid and find the median
        flat_grid.sort()
        median = flat_grid[len(flat_grid) // 2]
        
        # Calculate the total operations
        ans = sum(abs(num - median) // x for num in flat_grid)
        return ans

Complexity

• ⏰ Time complexity: O(m * n * log(m * n)).
  • Flattening the grid: O(m * n)
  • Sorting: O(m * n * log(m * n))
  • Total cost calculation: O(m * n)
  • Overall: O(m * n * log(m * n))
• 🧺 Space complexity: O(m * n)