Problem Statement in English

You’re given a m x n grid. Each cell in the grid has an integer value. You can perform the following operation any number of times:

  • Choose any cell in the grid and add or subtract x from the value of that cell.

Your task is to make all the values in the grid the same. Return the minimum number of operations required to achieve this, or -1 if it’s not possible.

Approach

You’re going to need a little math for this.

In order to minimize the number of operations, we should aim to make all the values in the grid equal to the median of the values. This is because the median minimizes the sum of absolute deviations.

Thus we flatten the grid into a single list, sort it, and find the median. Then we calculate the number of operations required to make all values equal to the median. If any value cannot be made equal to the median (i.e., if the absolute difference between the value and the median is not divisible by x), we return -1.

And we’re done!

Solution in Python


class Solution:
    def minOperations(self, grid: List[List[int]], x: int) -> int:
        arr = [cell for row in grid for cell in row]
        arr.sort()

        median = arr[len(arr) // 2]
        res = 0

        for cell in arr:
            if abs(median - cell) % x:
                return -1
            res += abs(median - cell) // x

        return res

Complexity

  • Time: $O(mn \log(mn))$

    • Flattening the grid takes $O(mn)$ time.
    • Sorting the array takes $O(mn \log(mn))$ time.
    • Calculating the number of operations takes $O(mn)$ time.

  • Space: $O(mn)$

    • The flattened array requires $O(mn)$ space.

Mistakes I Made

I had to look this up :(

And we are done.