Problem Informations

• Problem Index: 2033
• Problem Link: Minimum Operations to Make a Uni-Value Grid
• Topics: Array, Math, Sorting, Matrix

Problem Description

You are given a 2D integer grid of size $m \times 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 == \text{grid.length}$
• $n == \text{grid[i].length}$
• $1 \leq m, n \leq 10^5$
• $1 \leq m \times n \leq 10^5$
• $1 \leq x, \text{grid[i][j]} \leq 10^4$

Intuition

The problem requires transforming a given grid into a uni-value grid where all elements are equal using a series of defined operations. Each operation involves either adding or subtracting a given integer $x$ to an element of the grid. The optimal approach to minimize the number of operations involves guiding the transformation of the elements towards a central tendency, specifically the median of the grid’s values, ensuring the smallest aggregate distance.

Approach

The solution begins by flattening the 2D grid into a 1D array. This step simplifies the complexity of working with multidimensional data and allows us to more easily sort and manipulate the grid’s values.

1. Flatten the Grid: Each element in the 2D grid is extracted and stored in a 1D array, flatGrid. This process involves iterating through each row of the grid and appending each element to flatGrid.

2. Sort the Flattened Array: Once we have a flattened version of the grid, we sort flatGrid. Sorting is a crucial step as it enables the identification of the median value in the next step.

3. Identify the Target Value: The median of the sorted array is chosen as the target value for transformation. The median is ideal because minimizing the sum of absolute deviations is achieved by aligning elements to this central value.

4. Calculate Operations: For each element in flatGrid, calculate the absolute difference from the target value (median). The difference dictates how much change is needed for that element. If an element requires transformation to become equal to the target and the difference is not divisible by $x$, then it is impossible for that element to reach the target using available operations, prompting an immediate return of -1.

5. Sum of Operations: For differences that are divisible by $x$, compute the number of operations required by dividing the difference by $x$, and accumulate this count into totalOperations.

6. Return the Result: If all differences are divisible by $x$, the final totalOperations value represents the minimum operations required to transform the grid into a uni-value grid. Otherwise, the transformation is not feasible, as identified earlier by non-divisible differences, and the function returns -1.

This approach efficiently transforms the grid by leveraging the properties of the median and direct transformations using arithmetic operations, resulting in a solution that is feasible within the constraints given.

Code

C++

class Solution {
public:
    int minOperations(vector<vector<int>>& grid, int x) {
        vector<int> flatGrid;
        
        // Flatten the 2D grid into a 1D array for easier manipulation
        for (vector<int>& row : grid) {
            for (int value : row) {
                flatGrid.push_back(value);
            }
        }
        
        // Sort the 1D array to find the median
        sort(flatGrid.begin(), flatGrid.end());
        
        int totalOperations = 0;
        int targetValue = flatGrid[flatGrid.size() / 2]; 
        
        // Calculate the total number of operations required to make the grid uni-value
        for (int i = 0; i < flatGrid.size(); i++) {
            int difference = abs(flatGrid[i] - targetValue);
            
            // Check if it's possible to make all elements equal
            if (difference % x != 0) {
                return -1;
            }
            
            totalOperations += difference / x;
        }
        
        return totalOperations;
    }
};

Python

class Solution:
    def minOperations(self, grid, x):
        flatGrid = []
        
        # Flatten the 2D grid into a 1D array for easier manipulation
        for row in grid:
            for value in row:
                flatGrid.append(value)
        
        # Sort the 1D array to find the median
        flatGrid.sort()
        
        totalOperations = 0
        targetValue = flatGrid[len(flatGrid) // 2]
        
        # Calculate the total number of operations required to make the grid uni-value
        for i in range(len(flatGrid)):
            difference = abs(flatGrid[i] - targetValue)
            
            # Check if it's possible to make all elements equal
            if difference % x != 0:
                return -1
            
            totalOperations += difference // x
        
        return totalOperations

Complexity

• Time complexity: $O(m \times n \log (m \times n))$

  The solution involves a few key steps: flattening the grid into a 1D array, sorting that array, and then iterating through it to calculate the total number of operations.

  • Flattening the grid takes $O(m \times n)$ time since each element is accessed once.

  • Sorting the flattened array requires $O(m \times n \log (m \times n))$ time complexity, which dominates the other operations in terms of time.

  • Once sorted, the algorithm calculates the number of operations, which again requires $O(m \times n)$ time because it processes each element once.

  Therefore, the overall time complexity is dominated by the sorting step, yielding a complexity of $O(m \times n \log (m \times n))$.

• Space complexity: $O(m \times n)$

  • The space complexity is determined by the additional space used, which primarily consists of the flatGrid vector used to store the elements of the original grid. This vector contains $m \times n$ elements.

  • Aside from this, a constant amount of extra space is used for variables like totalOperations and targetValue.

  Hence, the overall space complexity is $O(m \times n)$.