2033. Minimum Operations to Make a Uni-Value Grid

Description

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.

 

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 <= 105
• 1 <= m * n <= 105
• 1 <= x, grid[i][j] <= 104

Solution

minimum-operations-to-make-a-uni-value-grid.py

class Solution:
    def minOperations(self, grid: List[List[int]], x: int) -> int:
        A = []

        for row in grid:
            A += row

        n = len(A)
        A.sort()

        for i in range(1, n):
            if (A[i] - A[i - 1]) % x != 0:
                return -1

        def go(target):
            count = 0

            for v in A:
                count += (abs(v - target)) // x

            return count

        mid = n // 2
        return go(A[mid]) if n & 1 else min(go(A[mid - 1]), go(A[mid]))