# Minimum Operations to Make a Uni-Value Grid
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-operations-to-make-a-uni-value-grid)
Canonical: https://scaleengineer.com/dsa/problems/minimum-operations-to-make-a-uni-value-grid
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Matrix
**Companies:** [EPAM Systems](https://scaleengineer.com/companies/epam-systems)
---
## Problem
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:**

![](https://assets.glich.co/dsa/minimum-operations-to-make-a-uni-value-grid/image0.png) 

**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:**

![](https://assets.glich.co/dsa/minimum-operations-to-make-a-uni-value-grid/image1.png) 

**Input:** grid = [[1,5],[2,3]], x = 1
**Output:** 5
**Explanation:** We can make every element equal to 3.

**Example 3:**

![](https://assets.glich.co/dsa/minimum-operations-to-make-a-uni-value-grid/image2.png) 

**Input:** grid = [[1,2],[3,4]], x = 2
**Output:** -1
**Explanation:** It is impossible to make every element equal.

**Constraints:**

* `m == grid.length`
* `n == grid[i].length`
* `1 <= m, n <= 105`
* `1 <= m * n <= 105`
* `1 <= x, grid[i][j] <= 104`

# Approaches
## Brute Force by Checking Potential Targets
This approach involves testing every possible value that the grid elements could converge to. The range of possible target values is bounded by the minimum and maximum values present in the grid. While conceptually simple, it is computationally too expensive for the problem's constraints.
**Time:** O(S * (V_max - V_min) / x), where `S` is the total number of elements (`m*n`), and `V_max`, `V_min` are the maximum and minimum values in the grid. This is too slow for the given constraints. · **Space:** O(1), as we only need a few variables to store state.
**Pros:** Simple to understand and implement.; Doesn't require complex data structures or algorithms.
**Cons:** Extremely inefficient. The time complexity depends on the range of values in the grid, which can be large.; Will likely result in a 'Time Limit Exceeded' error for the given constraints.
### Explanation
First, we must ensure that it's even possible to make the grid uni-value. This is only true if the difference between any two elements is a multiple of `x`. A simpler way to check this is to verify that all elements in the grid have the same remainder when divided by `x`. We can compute the remainder of the first element, `grid[0][0] % x`, and then iterate through the rest of the grid. If we find any element with a different remainder, we return -1.

If the condition holds, we identify the minimum (`minVal`) and maximum (`maxVal`) elements in the grid. The optimal target value must lie within this range.

We then iterate through all possible target values `T` from `minVal` to `maxVal`. For each `T`, we first check if it's a valid target (i.e., `(T - grid[0][0]) % x == 0`). If it is, we calculate the total operations required to make every grid element equal to `T`. This is done by summing up `abs(grid[i][j] - T) / x` for all elements. We keep track of the minimum number of operations found across all valid targets. After checking all possibilities, the minimum value found is the answer.
### Algorithm
- 1. Check if all elements in the grid have the same remainder when divided by `x`. If not, return -1.
- 2. Find the minimum (`minVal`) and maximum (`maxVal`) values in the grid.
- 3. Initialize `minOps` to infinity.
- 4. Iterate through each potential target `T` from `minVal` to `maxVal`.
- 5. If `(T - minVal) % x == 0`:
    - a. Calculate the total operations `currentOps` to make all elements equal to `T`.
    - b. `currentOps = sum(abs(grid[i][j] - T) / x)` for all `i, j`.
    - c. Update `minOps = min(minOps, currentOps)`.
- 6. Return `minOps` if it was updated, otherwise handle the case where no valid target was found (though the initial check should prevent this).

## Sorting to Find the Optimal Target (Median)
A more efficient approach recognizes that the problem is equivalent to finding a number `T` that minimizes the sum of absolute differences `Σ|num - T|`. The optimal value for `T` is the median of the numbers. By sorting the grid elements, we can easily find the median and calculate the total operations.
**Time:** O(S log S), where `S = m * n`. The dominant operation is sorting the flattened array of `S` elements. · **Space:** O(S) to store the flattened `nums` array, where `S = m * n`.
**Pros:** Correct and much more efficient than brute force.; Guaranteed to find the optimal solution.; Relatively easy to implement using standard library functions for sorting.
**Cons:** The sorting step takes `O(S log S)` time, which can be improved upon.; Requires extra space to store the flattened array.
### Explanation
The core insight is that the total number of operations is `(Σ|grid[i][j] - T|) / x`. To minimize this, we need to find a target value `T` that minimizes `Σ|grid[i][j] - T|`. This is a classic statistical problem, and the solution is to choose `T` as the median of all the elements in the grid.

The algorithm proceeds as follows:
- First, we flatten the 2D `grid` into a 1D array, let's call it `nums`.
- During this process, we also perform the crucial check: all elements must have the same remainder when divided by `x`. If `grid[i][j] % x` is not consistent for all elements, we return -1 immediately.
- Next, we sort the `nums` array in non-decreasing order.
- The optimal target value `T` is the median of this sorted array. For an array of size `S`, the median is the element at index `S / 2`.
- Finally, we calculate the minimum number of operations by iterating through the `nums` array and summing the operations for each element to reach the median: `totalOps = Σ(|num - median|) / x`.

This approach is significantly faster than brute force because it directly calculates the optimal target instead of searching for it.
```java
import java.util.Arrays;

class Solution {
    public int minOperations(int[][] grid, int x) {
        int m = grid.length;
        int n = grid[0].length;
        int[] nums = new int[m * n];
        int k = 0;
        
        int remainder = grid[0][0] % x;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] % x != remainder) {
                    return -1;
                }
                nums[k++] = grid[i][j];
            }
        }
        
        Arrays.sort(nums);
        
        int median = nums[(m * n) / 2];
        int operations = 0;
        
        for (int num : nums) {
            operations += Math.abs(num - median) / x;
        }
        
        return operations;
    }
}
```
### Algorithm
- 1. Create a 1D array `nums` of size `m * n`.
- 2. Flatten the `grid` into `nums`. While doing so, check if all `grid[i][j] % x` are equal. If not, return -1.
- 3. Sort the `nums` array.
- 4. Identify the median element: `median = nums[(m * n) / 2]`.
- 5. Calculate the total operations: `operations = 0`.
- 6. For each `num` in `nums`, add `abs(num - median) / x` to `operations`.
- 7. Return `operations`.

## Optimal Solution using Linear-Time Median Selection (Quickselect)
This approach optimizes the previous one by finding the median in linear time on average, instead of `O(S log S)` time required for sorting. This is achieved using a selection algorithm like Quickselect, making it the most efficient approach for this problem.
**Time:** O(S) on average, where `S = m * n`. This is due to the linear-time average complexity of Quickselect. The worst-case is `O(S^2)`. · **Space:** O(S) to store the flattened `nums` array. The iterative implementation of Quickselect shown uses O(1) extra space, while a recursive one would use O(log S) stack space on average.
**Pros:** Asymptotically faster than the sorting approach on average.; Represents the most efficient known solution for this problem.
**Cons:** More complex to implement than the sorting approach.; Quickselect has a worst-case `O(S^2)` time complexity, although this is rare with a good pivot selection strategy (like randomization).
### Explanation
This method builds upon the median-finding approach but replaces the full sort with a more efficient algorithm. The median is the k-th smallest element in a set of `S` numbers, where `k = S / 2`. An algorithm like Quickselect can find the k-th smallest element in an unsorted array in average linear time.

The overall algorithm is very similar:
- First, flatten the grid into a 1D array `nums` and check the remainder condition, returning -1 if it fails.
- Instead of sorting the entire `nums` array, use the Quickselect algorithm to find the median element. Quickselect partitions the array around a pivot and recursively searches only in the partition that contains the k-th element.
- Once the median is found, we calculate the total operations by summing `abs(num - median) / x` for all `num` in the (partially rearranged) `nums` array.

While Quickselect has a worst-case time complexity of `O(S^2)`, its average-case performance is `O(S)`, making it faster in practice for large inputs than sorting.
```java
import java.util.Random;

class Solution {
    public int minOperations(int[][] grid, int x) {
        int m = grid.length;
        int n = grid[0].length;
        int size = m * n;
        int[] nums = new int[size];
        int k = 0;
        
        int remainder = grid[0][0] % x;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] % x != remainder) {
                    return -1;
                }
                nums[k++] = grid[i][j];
            }
        }
        
        int median = findKthSmallest(nums, 0, size - 1, size / 2);
        
        int operations = 0;
        for (int num : nums) {
            operations += Math.abs(num - median) / x;
        }
        
        return operations;
    }

    // Quickselect algorithm to find the k-th smallest element
    private int findKthSmallest(int[] nums, int left, int right, int k) {
        while (left <= right) {
            int pivotIndex = partition(nums, left, right);
            if (pivotIndex == k) {
                return nums[pivotIndex];
            } else if (pivotIndex > k) {
                right = pivotIndex - 1;
            } else {
                left = pivotIndex + 1;
            }
        }
        return -1; // Should not happen
    }

    private int partition(int[] nums, int left, int right) {
        // Randomized pivot to avoid worst-case
        Random rand = new Random();
        int pivotIndex = left + rand.nextInt(right - left + 1);
        int pivotValue = nums[pivotIndex];
        
        swap(nums, pivotIndex, right); // Move pivot to end
        
        int storeIndex = left;
        for (int i = left; i < right; i++) {
            if (nums[i] < pivotValue) {
                swap(nums, storeIndex, i);
                storeIndex++;
            }
        }
        
        swap(nums, storeIndex, right); // Move pivot to its final place
        return storeIndex;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
```
### Algorithm
- 1. Create a 1D array `nums` of size `m * n`.
- 2. Flatten the `grid` into `nums` and check the remainder condition. If it fails, return -1.
- 3. Use the Quickselect algorithm to find the `(m * n) / 2`-th smallest element in `nums`. This element is the median.
- 4. Calculate the total operations by summing `abs(num - median) / x` for each `num` in `nums`.
- 5. Return the total operations.

# Solutions
### Java

```java
class Solution {
public
  int minOperations(int[][] grid, int x) {
    int m = grid.length, n = grid[0].length;
    int[] nums = new int[m * n];
    int mod = grid[0][0] % x;
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (grid[i][j] % x != mod) {
          return -1;
        }
        nums[i * n + j] = grid[i][j];
      }
    }
    Arrays.sort(nums);
    int mid = nums[nums.length >> 1];
    int ans = 0;
    for (int v : nums) {
      ans += Math.abs(v - mid) / x;
    }
    return ans;
  }
}

```

### JavaScript

```javascript
function minOperations ( grid , x ) { const arr = grid . flat ( 2 ); arr . sort (( a , b ) => a - b ); const median = arr [ Math . floor ( arr . length / 2 )]; let res = 0 ; for ( const val of arr ) { const c = Math . abs ( val - median ) / x ; if ( c !== ( c | 0 )) return - 1 ; res += c ; } return res ; }
```

### CPP

```cpp
class Solution {
public:
  int minOperations(vector<vector<int>> &grid, int x) {
    int m = grid.size(), n = grid[0].size();
    int mod = grid[0][0] % x;
    int nums[m * n];
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (grid[i][j] % x != mod) {
          return -1;
        }
        nums[i * n + j] = grid[i][j];
      }
    }
    sort(nums, nums + m * n);
    int mid = nums[(m * n) >> 1];
    int ans = 0;
    for (int v : nums) {
      ans += abs(v - mid) / x;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def minOperations(self, grid: List[List[int]], x: int) -> int: nums = [] mod = grid[0][0] % x for row in grid: for v in row: if v % x != mod: return - 1 nums . append(v) nums . sort() mid = nums[len(nums) >> 1] return sum(abs(v - mid) // x for v in nums)

```