Minimum Operations to Make a Uni-Value Grid

Leetcode Problem:

• Minimum Operations to Make a Uni-Value Grid

Summary

• This problem requires finding the minimum number of operations to make a 2D grid uni-value by adding or subtracting a given number x from any element in the grid.

Approach

• The solution first finds the minimum value in the grid and then calculates the sum of all elements in the grid after subtracting the minimum value
• It then checks if the sum is divisible by x and if it is, it calculates the minimum number of operations needed to make all elements equal to the sum divided by the number of elements in the grid
• If the sum is not divisible by x, it returns -1
• Otherwise, it uses a binary search approach to find the minimum number of operations needed to make all elements equal to the sum divided by the number of elements in the grid.

Complexity

• O(m*n log(m*n))

Explanation

• The solution first finds the minimum value in the grid and then calculates the sum of all elements in the grid after subtracting the minimum value
• It then checks if the sum is divisible by x and if it is, it calculates the minimum number of operations needed to make all elements equal to the sum divided by the number of elements in the grid
• If the sum is not divisible by x, it returns -1
• Otherwise, it uses a binary search approach to find the minimum number of operations needed to make all elements equal to the sum divided by the number of elements in the grid.

Solution Code:

class Solution {
public:
    int minOperations(vector>& grid, int x) {
        int m = grid.size();
        int n = grid[0].size();
        int minValue = 1000000;
        for(int i = 0 ; i < m; i++){
            for(int j = 0 ; j < n; j++){
                if(minValue > grid[i][j]){
                    minValue = grid[i][j];
                }
            }
        }
        int sum = 0;        
        for(int i = 0 ; i < m; i++){
            for(int j = 0 ; j < n; j++){
                grid[i][j] -= minValue;
                if(grid[i][j] % x != 0) return -1;
                grid[i][j] /= x;
                sum += grid[i][j];
            }
        }
        double temp = sum / double(m*n);
        int goal = temp + 0.5;
        int ans = 1000000001;
        for(int k = -20; k <= 20; k++){
            int goal2 = goal + k;
            int sum2 = 0;
            for(int i = 0 ; i < m; i++){
                for(int j = 0 ; j < n; j++){
                    sum2 += abs(goal2 - grid[i][j]);
                }
            }
            ans = min(ans, sum2);
        }
        
        return ans;
    }
};