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:

$$ \begin{bmatrix} 2 & 4 \\ 6 & 8 \end{bmatrix} $$

1
2
3
4
5
6
7

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:

$$ \begin{bmatrix} 1 & 5 \\ 2 & 3 \end{bmatrix} $$

1
2
3

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

Example 3:

$$ \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix} $$

1
2
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

 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

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

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)