Skip to main content
Talentd

Minimum Operations to Make a Uni-Value Grid - Solution & Explanation

MediumArrayMathSortingMatrix16 min readAsked at: Amazon, Microsoft, Meta +2
Practice this problem

Problem Statement

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.length
  • n == grid[i].length
  • 1 <= m, n <= 105
  • 1 <= m * n <= 105
  • 1 <= x, grid[i][j] <= 104

Approach Overview

Problem Overview: You are given an m x n grid and an integer x. In one operation, you can add or subtract x from any cell. The goal is to make every value in the grid equal using the minimum number of operations, or return -1 if it cannot be done.

The key observation: since each operation changes a value by exactly x, all numbers must belong to the same remainder group modulo x. If any element differs in value % x, reaching a single common value is impossible.

Approach 1: Heuristic with Median (Flatten + Sorting) (Time: O(mn log(mn)), Space: O(mn))

Flatten the matrix into a 1D array and check that every element has the same remainder when divided by x. If not, return -1 immediately. Otherwise, sort the array and pick the median value as the target.

The median minimizes the sum of absolute differences. For each element v, the number of operations required is |v - median| / x. Add these across all elements to compute the total operations. Sorting ensures you can find the median efficiently, and the absolute distance conversion turns the grid problem into a classic sorting and distance minimization task.

This works because converting all values to the median minimizes the total movement across the array. The approach is simple, deterministic, and performs well for typical grid sizes.

Approach 2: Dynamic Programming with Modulo Analysis (Time: O(mn * k), Space: O(k))

This method focuses on grouping values by the number of steps away from a base remainder class. After confirming that all elements share the same remainder modulo x, convert each value into a normalized step count: (value - base) / x. Now the problem becomes minimizing total moves to convert all step counts into one value.

Instead of sorting, you can build frequency counts of these normalized values and compute the minimum cost using prefix sums or dynamic programming over possible targets. Each transition evaluates how many increments or decrements are required to move elements toward a candidate value.

This technique emphasizes the mathematical structure of the problem and uses properties of arrays and math. While more complex than the median approach, it avoids explicitly sorting the entire dataset and can be useful when working with bounded ranges or precomputed frequencies.

Recommended for interviews: The median-based solution is what interviewers typically expect. It demonstrates that you recognize the modulo feasibility constraint and the median property for minimizing absolute distance. Mentioning the modulo check first shows strong problem insight. Implementing the flattened array + median approach quickly communicates practical algorithm skills.

Approach 1: Heuristic with Median

This approach uses the median for achieving a minimum number of operations. First, we flatten the grid into a 1D list and check if making each element same modulo x throughout the array is possible (i.e., every element should give the same remainder when divided by x). If not, return -1. Once verified, the optimal strategy involves changing each element to the median value since it minimizes the sum of absolute differences.

The code first collects all elements from the grid into a single array. It checks if all elements can be made uniform via x by checking the modulo condition. Then, it sorts the array, calculates the median, and sums up the transformations required to reach this median.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

The time complexity is O(m*n*log(m*n)) due to sorting of elements. The space complexity is O(m*n) for storing elements in the flat array.

Try this approach in the editor →

Approach 2: Dynamic Programming with Modulo Analysis

A dynamic programming approach can be conceived if the uniformity condition across the grid is known, leveraging precomputation of costs to certain potential target values. However, due to the wide range of potential values in the given constraints, this approach degrades to tailor a more heuristic method with optimal modulus checks similar to GCD, discussed earlier. Thus, a full DP-based optimization is often less effective with sheer brute-force modulo checking.

It is not practical to dynamically program solutions when median heuristics offer cost-effective approximations and efficient results within the problem's constraints.

Code

CJava

C

Java

Complexity

Naive complexity could reach O((maxA - minA)/x*m*n) under impractical conditions which are avoided by median heuristic.

Try this approach in the editor →

Approach 3: Greedy

Firstly, to make the grid a single-value grid, the remainder of all elements of the grid with x must be the same.

Therefore, we can first traverse the grid to check whether the remainder of all elements with x is the same. If not, return -1. Otherwise, we put all elements into an array, sort the array, take the median, then traverse the array, calculate the difference between each element and the median, divide it by x, and add all the differences to get the answer.

The time complexity is O((m times n) times log (m times n)), and the space complexity is O(m times n). Here, m and n are the number of rows and columns of the grid, respectively.

Code

PythonJavaC++GoTypeScriptJavaScript

Python

Java

C++

Go

TypeScript

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Heuristic with Median

The time complexity is O(m*n*log(m*n)) due to sorting of elements. The space complexity is O(m*n) for storing elements in the flat array.

Dynamic Programming with Modulo Analysis

Naive complexity could reach O((maxA - minA)/x*m*n) under impractical conditions which are avoided by median heuristic.

Greedy—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Heuristic with Median (Flatten + Sort)O(mn log(mn))O(mn)General case; simplest and most common interview solution
Dynamic Programming with Modulo AnalysisO(mn * k)O(k)Useful when value ranges are bounded or frequency-based optimization is preferred

Video Solution

Minimum Operations to Make a Uni-Value Grid | Detailed Simple Maths Proof | Leetcode 2033 | MIK • codestorywithMIK • 11,712 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Minimum Operations to Make a Uni-Value Grid easy or hard?
The problem is generally classified as Medium. The main challenge is recognizing the modulo feasibility constraint and the fact that the median minimizes total absolute movement. Once these insights are clear, the implementation becomes straightforward.
Minimum Operations to Make a Uni-Value Grid Python/Java solution
In Python or Java, flatten the grid into a list, verify all values share the same remainder modulo x, then sort the list and pick the middle element as the median. The total operations are computed using abs(value - median) / x for each element. The implementation is short and typically under 20 lines.
How to solve Minimum Operations to Make a Uni-Value Grid in O(n)?
After verifying that all numbers share the same remainder modulo x, you can avoid full sorting by using a selection algorithm (like Quickselect) to find the median in O(n) average time. Once the median is known, compute the operation cost in a single linear scan. This reduces the median search from O(n log n) to O(n).
What is the best approach for Minimum Operations to Make a Uni-Value Grid?
The optimal approach flattens the grid into a single array, checks that all elements share the same remainder modulo x, then sorts the array and converts all values to the median. The median minimizes the total absolute distance, so the total operations become the sum of |value − median| / x. This solution runs in O(mn log(mn)) time due to sorting.
Is Minimum Operations to Make a Uni-Value Grid asked at Google/Amazon/Meta?
Problems involving median minimization, grid transformations, and modular feasibility checks commonly appear in interviews at companies like Google, Amazon, and Meta. Variants of this problem test understanding of sorting, absolute difference minimization, and mathematical constraints.
What data structure is used in Minimum Operations to Make a Uni-Value Grid?
The solution primarily uses arrays. The grid is flattened into a one-dimensional array so that sorting or median selection can be applied efficiently. Additional logic relies on modular arithmetic and simple iteration over the array.
What is the time complexity of Minimum Operations to Make a Uni-Value Grid?
The common optimal solution runs in O(mn log(mn)) time and O(mn) space. The grid is flattened into an array of size m*n, then sorted to locate the median. After that, a linear pass computes the number of operations required for each element.

Ready to solve this problem?

Practice Minimum Operations to Make a Uni-Value Grid with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Moves to Equal Array Elements II