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 = 2Output:4Explanation: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 = 1Output:5Explanation:We can make every element equal to 3.

**Example 3:**

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

**Constraints:**

`m == grid.length`

`n == grid[i].length`

`1 <= m, n <= 10`

^{5}`1 <= m * n <= 10`

^{5}`1 <= x, grid[i][j] <= 10`

^{4}

**Solution: Median**

To achieve minimum operations, the uni-value must be the median of the array.

Time complexity: O(m*n)

Space complexity: O(m*n)

## C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// Author; Huahua class Solution { public: int minOperations(vector<vector<int>>& grid, int x) { const int mn = grid.size() * grid[0].size(); vector<int> nums; nums.reserve(mn); for (const auto& row : grid) nums.insert(end(nums), begin(row), end(row)); nth_element(begin(nums), begin(nums) + mn / 2, end(nums)); const int median = nums[mn / 2]; int ans = 0; for (int v : nums) { if (abs(v - median) % x) return -1; ans += abs(v - median) / x; } return ans; } }; |