Skip to main content
Talentd
Talentd#1 Freshers Platform
Find Work
Learn
Tools
Post a JobFreeJoin Community
TalentdTalentd

Minimum Operations to Make All Grid Elements Equal - Solution & Explanation

HardPremiumFree on FleetCode14 min read
Practice this problem

Problem Statement

You are given a 2D integer array grid of size m × n, and an integer k.

In one operation, you can:

  • Select any k x k submatrix of grid, and
  • Increment all elements inside that submatrix by 1.

Return the minimum number of operations required to make all elements in the grid equal. If it is not possible, return -1.

A submatrix (x1, y1, x2, y2) is a matrix that forms by choosing all cells matrix[x][y] where x1 <= x <= x2 and y1 <= y <= y2.

 

Example 1:

Input: grid = [[3,3,5],[3,3,5]], k = 2

Output: 2

Explanation:

Choose the left 2 x 2 submatrix (covering the first two columns) and apply the operation twice.

  • After 1 operation: [[4, 4, 5], [4, 4, 5]]
  • After 2 operations: [[5, 5, 5], [5, 5, 5]]

All elements become equal to 5. Thus, the minimum number of operations is 2.

Example 2:

Input: grid = [[1,2],[2,3]], k = 1

Output: 4

Explanation:

Since k = 1, each operation increments a single cell grid[i][j] by 1. To make all elements equal, the final value must be 3.

  • Increase grid[0][0] = 1 to 3, requiring 2 operations.
  • Increase grid[0][1] = 2 to 3, requiring 1 operation.
  • Increase grid[1][0] = 2 to 3, requiring 1 operation.

Thus, the minimum number of operations is 2 + 1 + 1 + 0 = 4.

 

Constraints:

  • 1 <= m == grid.length <= 1000
  • 1 <= n == grid[i].length <= 1000
  • -105 <= grid[i][j] <= 105
  • 1 <= k <= min(m, n)

Approach Overview

Problem Overview: You are given a 2D grid of integers and must determine the minimum number of operations required to make every cell contain the same value. Each operation modifies a range of cells, so the challenge is tracking how previous operations affect future positions while minimizing redundant updates.

Approach 1: Direct Simulation (Brute Force) (Time: O((m*n)^2), Space: O(1))

The most straightforward idea is to repeatedly scan the grid and apply operations whenever a cell differs from the desired target value. For each mismatch, simulate the allowed operation that updates the affected region and propagate the change across the grid. This approach quickly becomes expensive because each operation may touch many cells, and repeated scans multiply the cost. It works only for very small grids and mainly serves as a conceptual baseline.

Approach 2: 2D Difference Array + Greedy (Time: O(m*n), Space: O(m*n))

The efficient solution tracks range updates using a 2D difference array. Instead of directly modifying every cell in a rectangle, record only the boundary adjustments in the difference structure. While iterating the grid from top-left to bottom-right, maintain the cumulative effect of previously applied operations using prefix accumulation. If the current effective value differs from the required value, compute the needed adjustment and greedily apply it starting at that cell. The difference array marks how this operation affects future cells without explicitly updating the entire region.

This greedy traversal works because once you process a cell in row-major order, earlier operations cannot affect it anymore. Each mismatch is fixed immediately, and its impact is propagated efficiently through the difference array. The technique is similar to using prefix sums but extended to two dimensions, which keeps updates constant time while scanning the grid once.

The core idea combines two concepts: fast range updates using a difference matrix and deterministic correction using a greedy scan. Problems involving repeated submatrix updates often benefit from this pattern. If you're unfamiliar with these techniques, review prefix sums, array manipulation, and greedy algorithms.

Recommended for interviews: The 2D Difference Array + Greedy approach is the expected solution. Interviewers want to see that you avoid naive repeated updates and instead track range effects efficiently. Mentioning the brute-force simulation demonstrates understanding of the problem mechanics, but implementing the difference-array optimization shows strong algorithmic maturity.

Solution

Since the operation can only increase the value of elements, all elements in the final grid must be equal to some target value T, and T \ge max(grid).

Start traversing the grid from the top-left corner (0, 0). For any position (i, j), if its current value is less than T, since subsequent operations (with a more rightward or downward position as the top-left corner) cannot cover (i, j), it is necessary to perform T - current_val operations at the current position, each using (i, j) as the top-left corner of a k times k increment operation.

If each operation traverses the k times k region, the complexity will reach O(m cdot n cdot k^2). We can use a 2D difference array diff to record the operations. By maintaining the 2D prefix sum of diff in real time, we can obtain the cumulative increment at the current position in O(1) time, and update the future impact of a k times k region in O(1) time.

In most cases, T = max(grid) is sufficient. However, in some cases where k times k regions overlap, a smaller T may cause the middle positions to be passively increased beyond T. According to mathematical consistency, if both T = max(grid) and T = max(grid) + 1 are not feasible, then it is impossible to flatten the grid using k times k operations.

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

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Direct Simulation (Brute Force)O((m*n)^2)O(1)Only for very small grids or to understand how operations affect cells
2D Difference Array + GreedyO(m*n)O(m*n)General case with frequent range updates across submatrices

Frequently Asked Questions

Is Minimum Operations to Make All Grid Elements Equal easy or hard?
The problem is categorized as Hard because it requires combining greedy reasoning with a 2D difference array technique. Many candidates initially attempt direct simulation, which becomes too slow. Recognizing that range updates can be tracked with a difference matrix is the key optimization.
Minimum Operations to Make All Grid Elements Equal Python/Java solution
The implementation typically builds a 2D difference matrix and iterates through the grid while maintaining prefix effects. When a mismatch is detected, the algorithm records the necessary update in the difference structure. The same logic translates directly across Python, Java, C++, Go, and TypeScript with identical O(m*n) complexity.
How to solve Minimum Operations to Make All Grid Elements Equal in O(n)?
Treat the grid as a 2D structure and process it with a difference array. Maintain cumulative prefix effects while iterating through the grid. When a cell's effective value does not match the desired value, compute the adjustment and record the update boundaries in the difference array. This ensures each operation is applied in constant time and the grid is processed in a single pass.
What is the best approach for Minimum Operations to Make All Grid Elements Equal?
The most efficient approach uses a 2D difference array combined with a greedy traversal. While scanning the grid from top-left to bottom-right, track the cumulative effect of prior operations using prefix accumulation. When the current cell differs from the target value, apply the required adjustment and record it in the difference matrix. This avoids repeatedly updating large submatrices and runs in O(m*n) time.
Is Minimum Operations to Make All Grid Elements Equal asked at Google/Amazon/Meta?
Problems involving grid transformations, prefix sums, and difference arrays appear frequently in interviews at companies like Google, Amazon, and Meta. Variants often require minimizing operations on matrices using efficient range updates or greedy traversal strategies.
What data structure is used in Minimum Operations to Make All Grid Elements Equal?
The key data structure is a 2D difference array, which allows constant-time updates for rectangular ranges. Combined with prefix accumulation, it efficiently propagates the impact of operations across the grid while scanning once.
What is the time complexity of Minimum Operations to Make All Grid Elements Equal?
The optimal solution runs in O(m*n) time where m and n are the grid dimensions. Each cell is processed exactly once while the difference array tracks the effect of operations. Space complexity is O(m*n) for storing the auxiliary difference structure used to propagate range updates.

Ready to solve this problem?

Practice Minimum Operations to Make All Grid Elements Equal with our built-in code editor and test cases.

Practice on FleetCode