We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Operations to Make a Uni-Value Grid

Difficulty: Medium

Problem 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.

Key Insights

  • The difference between any two elements in the grid must be a multiple of x for it to be possible to make all elements equal.
  • We need to find a target value that minimizes the number of operations required to make all elements equal.
  • A good candidate for the target is the median of the grid values, as it minimizes the sum of absolute deviations.

Space and Time Complexity

Time Complexity: O(m * n) - We traverse the grid to compute the differences and operations. Space Complexity: O(1) - We use a constant amount of additional space for calculations.

Solution

To solve this problem, we will:

  1. Flatten the 2D grid into a 1D list.
  2. Check if all elements can be made equal by verifying if the difference between the maximum and minimum element is divisible by x.
  3. Calculate the median of the list, as it serves as the optimal target value for minimizing operations.
  4. Count the total operations required to make all elements equal to the median by computing the sum of absolute differences divided by x.

Code Solutions

def minOperations(grid, x):
    # Flatten the grid into a 1D array
    arr = [num for row in grid for num in row]
    # Calculate the minimum and maximum in the array
    min_val, max_val = min(arr), max(arr)
    
    # Check if it's possible to make all elements equal
    if (max_val - min_val) % x != 0:
        return -1
    
    # Calculate total operations needed by finding the target as the median
    arr.sort()
    n = len(arr)
    target = arr[n // 2]
    
    operations = 0
    for num in arr:
        operations += abs(num - target) // x
    
    return operations
← Back to All Questions