← All problems

2033. Minimum Operations to Make a Uni Value Grid

MediumOpen on LeetCodeProblem statement

Problem Statement

2033. Minimum Operations to Make a Uni-Value Grid

Medium

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.

 

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:

Java

Source file
class Solution {

    public int minOperations(int[][] grid, int x) {
        List<Integer> numsArray = new ArrayList<>();
        int result = 0;

        // Flatten the grid into numsArray and check remainder condition
        for (int row = 0; row < grid.length; row++) {
            for (int col = 0; col < grid[0].length; col++) {
                if (grid[row][col] % x != grid[0][0] % x) return -1;
                // If any element has a different remainder than the first
                // element, it is impossible to make all elements equal, so
                // return -1
                numsArray.add(grid[row][col]);
            }
        }

        Collections.sort(numsArray);

        int length = numsArray.size();
        int prefixIndex = 0;
        int suffixIndex = length - 1;

        // Move prefixIndex and suffixIndex towards the middle
        while (prefixIndex < suffixIndex) {
            // If the prefix of equal elements is shorter than the suffix
            if (prefixIndex < length - suffixIndex - 1) {
                // Calculate the number of operations required to extend the prefix
                int prefixOperations =
                    ((prefixIndex + 1) *
                        (numsArray.get(prefixIndex + 1) -
                            numsArray.get(prefixIndex))) /
                    x;
                result += prefixOperations;
                // Move the prefix index forward
                prefixIndex++;
            } else {
                // Calculate the number of operations required to extend the suffix
                int suffixOperations =
                    ((length - suffixIndex) *
                        (numsArray.get(suffixIndex) -
                            numsArray.get(suffixIndex - 1))) /
                    x;
                result += suffixOperations;
                // Move the suffix index backward
                suffixIndex--;
            }
        }

        return result;
    }
}