Minimum Operations to Make a Uni-Value Grid
MedPrompt
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:
m == grid.lengthn == grid[i].length1 <= m, n <= 1051 <= m * n <= 1051 <= x, grid[i][j] <= 104
Approaches
3 approaches with complexity analysis and trade-offs.
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.
Algorithm
-
- Check if all elements in the grid have the same remainder when divided by
x. If not, return -1.
- Check if all elements in the grid have the same remainder when divided by
-
- Find the minimum (
minVal) and maximum (maxVal) values in the grid.
- Find the minimum (
-
- Initialize
minOpsto infinity.
- Initialize
-
- Iterate through each potential target
TfromminValtomaxVal.
- Iterate through each potential target
-
- If
(T - minVal) % x == 0:
- a. Calculate the total operations
currentOpsto make all elements equal toT. - b.
currentOps = sum(abs(grid[i][j] - T) / x)for alli, j. - c. Update
minOps = min(minOps, currentOps).
- If
-
- Return
minOpsif it was updated, otherwise handle the case where no valid target was found (though the initial check should prevent this).
- Return
Walkthrough
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.
Complexity
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.
Trade-offs
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.
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.
Algorithm
-
- Create a 1D array
numsof sizem * n.
- Create a 1D array
-
- Flatten the
gridintonums. While doing so, check if allgrid[i][j] % xare equal. If not, return -1.
- Flatten the
-
- Sort the
numsarray.
- Sort the
-
- Identify the median element:
median = nums[(m * n) / 2].
- Identify the median element:
-
- Calculate the total operations:
operations = 0.
- Calculate the total operations:
-
- For each
numinnums, addabs(num - median) / xtooperations.
- For each
-
- Return
operations.
- Return
Walkthrough
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
gridinto a 1D array, let's call itnums. - During this process, we also perform the crucial check: all elements must have the same remainder when divided by
x. Ifgrid[i][j] % xis not consistent for all elements, we return -1 immediately. - Next, we sort the
numsarray in non-decreasing order. - The optimal target value
Tis the median of this sorted array. For an array of sizeS, the median is the element at indexS / 2. - Finally, we calculate the minimum number of operations by iterating through the
numsarray 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.
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; }}Complexity
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`.
Trade-offs
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.
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.
Algorithm
-
- Create a 1D array
numsof sizem * n.
- Create a 1D array
-
- Flatten the
gridintonumsand check the remainder condition. If it fails, return -1.
- Flatten the
-
- Use the Quickselect algorithm to find the
(m * n) / 2-th smallest element innums. This element is the median.
- Use the Quickselect algorithm to find the
-
- Calculate the total operations by summing
abs(num - median) / xfor eachnuminnums.
- Calculate the total operations by summing
-
- Return the total operations.
Walkthrough
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
numsand check the remainder condition, returning -1 if it fails. - Instead of sorting the entire
numsarray, 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) / xfor allnumin the (partially rearranged)numsarray.
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.
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; }}Complexity
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.
Trade-offs
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).
Solutions
Solution
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; }}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 ; }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; }};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)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.