LC 2033 [M] Minimum Operations to Make a Uni Value Grid - ALawliet/algorithms GitHub Wiki

i had the sort + median intuition

then if remainder is not 0, then it cannot be made the target

class Solution:
    def minOperations(self, grid: List[List[int]], x: int) -> int:
        n_rows = len(grid)
        n_cols = len(grid[0])

        # handle the edge case
        if n_rows == 1 and n_cols == 1: return 0

        # transform grid to array, easier to operate
        arr = [] 
        for i in range(n_rows):
            arr += grid[i]

        arr.sort()

        n = len(arr)

        # the median is arr[len(arr)//2] when len(arr) is odd
        # or may be arr[len(arr)//2] and arr[len(arr)//2-1] when len(arr) is even.
        m_odd = arr[n // 2]
        m_even = arr[n // 2 - 1]

        def num_ops_to_target(target, x):
            ans = 0
            for r in range(n_rows):
                for c in range(n_cols):
                    # if remainder is not 0, then it cannot be made the target
                    quotient, remainder = divmod(abs(grid[r][c] - target), x)
                    if remainder != 0: 
                        return -1
                    else:
                        ans += quotient
            return ans

        return min(
            num_ops_to_target(m_odd, x),
            num_ops_to_target(m_even, x)
        )