Minimum Operations to Make a Uni-Value Grid Solution in Java

Problem Description

So, you think you can just waltz into a grid of numbers and make them all the same with a few operations? Well, welcome to the world of “Minimum Operations to Make a Uni-Value Grid.” Imagine you have a grid of numbers, and you want to make them all the same value. Sounds easy, right? Just like trying to convince your friends to agree on a restaurant choice—everyone has their own favorite, and good luck getting them to settle on one!

In this problem, you can only change the values in the grid by adding or subtracting a fixed integer x. If you can’t make all the numbers the same, you might as well throw in the towel and admit defeat. The challenge is to find the minimum number of operations required to achieve this uni-value grid.

Code Solution


class Solution {
  public int minOperations(int[][] grid, int x) {
    final int m = grid.length;
    final int n = grid[0].length;

    int[] A = new int[m * n];
    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        A[i * n + j] = grid[i][j];
    if (Arrays.stream(A).anyMatch(a -> (a - A[0]) % x != 0))
      return -1;

    int ans = 0;

    Arrays.sort(A);

    for (final int a : A)
      ans += Math.abs(a - A[A.length / 2]) / x;

    return ans;
  }
}

Approach

The approach taken in this solution is quite straightforward. First, we flatten the 2D grid into a 1D array. Then, we check if all elements can be transformed into the same value by verifying if the difference between each element and the first element is divisible by x. If not, we return -1.

Next, we sort the array and calculate the total number of operations needed to convert all elements to the median value of the array. The median is chosen because it minimizes the sum of absolute deviations, making it the most efficient target value.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(m * n log(m * n)), where m is the number of rows and n is the number of columns in the grid.
Space Complexity	O(m * n) for storing the flattened array.

Real-World Example

Imagine you and your friends are trying to agree on a single pizza topping for a party. Each of you has a different favorite topping, and you can only change your choice by swapping toppings with a fixed number of options. The goal is to find the least number of swaps needed to make everyone happy with the same topping. This is essentially what the problem is asking you to solve with numbers in a grid!