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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Operations to Make a Uni-Value Grid

Number: 2160

Difficulty: Medium

Paid? No

Companies: Google, Microsoft, EPAM Systems

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 or subtract x from any element in the grid. A uni-value grid is achieved when every element in the grid is equal. The task is to determine the minimum number of operations required to make the grid uni-valued. If it is impossible, return -1.

Key Insights

  • The only valid moves change an element by multiples of x, so for any two grid elements a and b to be made equal, (a - b) must be divisible by x.
  • Check if all elements have the same remainder when divided by x. If not, the answer is -1.
  • The optimal target value to which the grid should be transformed is the median of the list of elements (after confirming validity), because median minimizes the sum of absolute differences.
  • Calculate the number of moves required by summing the absolute differences between each element and the median, then dividing each difference by x.
  • Sorting is used to easily determine the median.

Space and Time Complexity

Time Complexity: O(m * n * log(m * n)) due to sorting the flattened grid.
Space Complexity: O(m * n) for storing the flattened grid.

Solution

The solution involves the following steps:

  1. Flatten the 2D grid into a 1D list.
  2. Verify that every element in the grid leaves the same remainder when divided by x. If not, return -1 as it is impossible to equalize the grid.
  3. Sort the flattened list and find the median value.
  4. Calculate the total number of operations by summing (|element - median| / x) for every element.
  5. Return the total count of operations.

This approach leverages the property of the median minimizing the sum of absolute differences and ensures correctness by validating the modulo condition. Sorting plays a crucial role in efficiently obtaining the correct median, yielding an overall manageable time complexity given the constraints.

Code Solutions

# Python solution with comments
def minOperations(grid, x):
    # Flatten the grid into a single list of numbers.
    flat_list = [num for row in grid for num in row]
    
    # Check if all elements have the same remainder modulo x.
    remainder = flat_list[0] % x
    for num in flat_list:
        if num % x != remainder:
            return -1  # It is impossible to make all elements equal.
    
    # Sort the list to find the median.
    flat_list.sort()
    n = len(flat_list)
    median = flat_list[n // 2]
    
    # Calculate the total number of operations.
    operations = 0
    for num in flat_list:
        # The difference divided by x gives the number of operations.
        operations += abs(num - median) // x
    return operations

# Example usage:
# grid = [[2,4],[6,8]]
# x = 2
# print(minOperations(grid, x))  # Output: 4
← Back to All Questions