LogoKode$word
LeetCode 2033: Minimum Operations to Make a Uni-Value Grid | Java Solution Explained (Median Approach)
LeetCode 2033: Minimum Operations to Make a Uni-Value Grid | Java Solution Explained (Median Approach)

LeetCode 2033: Minimum Operations to Make a Uni-Value Grid | Java Solution Explained (Median Approach)

Learn how to solve LeetCode 2033 using a median-based greedy approach. This guide covers intuition, dry run, multiple approaches, Java solution, complexity analysis, common mistakes, and a step-by-step explanation for beginners.

19 views
0
0
ArraySortingMathMedianMediumMatrixGridLeetCodeJava
Github icon
Github icon
Listen to articleAudio version

Introduction

In this problem, we are given a 2D grid and an integer x.

We can perform one operation where we either:

  1. Add x to any grid element
  2. Subtract x from any grid element

Our goal is to make all elements in the grid equal using the minimum number of operations.

If making all values equal is not possible, we return -1.

This problem may initially look like a matrix manipulation question, but the actual logic is based on:

  1. Array transformation
  2. Median property
  3. Greedy optimization

# Problem Link

Problem Statement

You are given:

  1. A 2D integer grid of size m × n
  2. An integer x

You can perform operations where you add or subtract x from any cell.

A grid becomes uni-value when all elements become equal.

Return the minimum number of operations needed.

If impossible, return -1.

Example

Example 1

Input:
grid = [[2,4],[6,8]]
x = 2

Output:
4

Explanation:

We can make every element equal to 4.

  1. 2 → 4 (1 operation)
  2. 6 → 4 (1 operation)
  3. 8 → 4 (2 operations)

Total = 4 operations.

Key Observation

Before solving the problem, we must understand one important rule.

If we can add or subtract only x, then:

All numbers must belong to the same remainder group when divided by x.

Meaning:

value % x must be same for every element

Why?

Because if two numbers have different remainders, they can never become equal using only +x or -x operations.

Intuition

We need to convert all numbers into a single target value.

But what target value gives minimum operations?

The answer is:

Median

For minimizing total absolute distance, median gives the optimal answer.

Since every operation changes value by x, we can:

  1. Flatten grid into a list
  2. Sort the list
  3. Pick median as target
  4. Calculate operations required

Why Median Works?

Median minimizes:

Sum of absolute differences

For example:

Numbers = [1, 2, 3, 10]

If target = 2

|1-2| + |2-2| + |3-2| + |10-2| = 10

If target = 5

|1-5| + |2-5| + |3-5| + |10-5| = 14

Median gives minimum total distance.

Approach 1: Brute Force

We can try every possible number as target.

For each target:

  1. Calculate operations required
  2. Store minimum answer

Time Complexity

O(N²)

Where N = total grid elements

This is slow for large constraints.

Approach 2: Optimal Median Approach

This is the best approach.

Steps

Step 1: Flatten Grid

Convert 2D grid into 1D array.

Step 2: Sort Array

Sorting helps us find median.

Step 3: Check Validity

All values must have same remainder when divided by x.

value % x must match

Otherwise return -1.

Step 4: Pick Median

Median minimizes operations.

Step 5: Count Operations

For every element:

operations += abs(value - median) / x

Java Solution

class Solution {
public int minOperations(int[][] grid, int x) {
List<Integer> lis = new ArrayList<>();

for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
lis.add(grid[i][j]);
}
}

Collections.sort(lis);

int mid = lis.size() / 2;
int remainder = lis.get(0) % x;

for (int value : lis) {
if (value % x != remainder) {
return -1;
}
}

int ans = 0;

for (int value : lis) {
int diff = Math.abs(lis.get(mid) - value);
ans += diff / x;
}

return ans;
}
}

Code Explanation

Step 1: Flatten Matrix

lis.add(grid[i][j]);

We convert grid into list.

Step 2: Sort List

Collections.sort(lis);

Sorting allows median selection.

Step 3: Check Possibility

if(value % x != remainder)

If remainders differ, answer becomes impossible.

Step 4: Select Median

int mid = lis.size()/2;

Median becomes target value.

Step 5: Calculate Operations

ans += diff/x;

Difference divided by x gives operations.

Dry Run

Input:

grid = [[2,4],[6,8]]
x = 2

Flatten:

[2,4,6,8]

Sort:

[2,4,6,8]

Median:

6

Operations:

2 → 6 = 2 operations
4 → 6 = 1 operation
6 → 6 = 0 operation
8 → 6 = 1 operation

Total:

4 operations

Time Complexity

Flatten Grid

O(N)

Sorting

O(N log N)

Traverse Array

O(N)

Total Complexity

O(N log N)

Where:

N = m × n

Space Complexity

We store all elements in list.

O(N)

Common Mistakes

1. Forgetting Mod Check

Many people directly calculate operations.

But without checking:

value % x

answer may become invalid.

2. Choosing Average Instead of Median

Average does not minimize absolute distance.

Median is required.

3. Not Sorting Before Finding Median

Median requires sorted array.

4. Forgetting Division by x

Operations are not direct difference.

Correct formula:

abs(target - value) / x

Edge Cases

Case 1

All values already equal.

Answer = 0

Case 2

Different modulo values.

Return -1

Case 3

Single cell grid.

No operation needed

FAQs

Q1. Why do we use median?

Median minimizes total absolute difference.

Q2. Why not average?

Average minimizes squared distance, not absolute operations.

Q3. Why modulo condition is important?

Because we can only move by multiples of x.

Q4. Can we solve without sorting?

Sorting is easiest way to get median.

Alternative median-finding algorithms exist but are unnecessary here.

Interview Insight

Interviewers ask this problem to test:

  1. Greedy thinking
  2. Median property
  3. Mathematical observation
  4. Array flattening
  5. Optimization logic

Conclusion

LeetCode 2033 is a great problem that combines math with greedy logic.

The most important learning points are:

  1. Flatten the grid
  2. Validate modulo condition
  3. Use median as target
  4. Calculate operations using difference divided by x

This approach is optimal and easy to implement.

Once you understand why median works, this problem becomes very straightforward.

Related Articles

LeetCode 462: Minimum Moves to Equal Array Elements II | Java Solution Explained (Median Approach)

LeetCode 462: Minimum Moves to Equal Array Elements II | Java Solution Explained (Median Approach)

Learn how to solve LeetCode 462 Minimum Moves to Equal Array Elements II using Java. Understand intuition, multiple approaches, median logic, dry run, complexity, FAQs, and optimized solution.

Read Article
Maximum Absolute Sum of Any Subarray

Maximum Absolute Sum of Any Subarray

LeetCode Question 1749 Medium

Read Article
Find Peak Element – Binary Search Explained with Java Solution (LeetCode 162)

Find Peak Element – Binary Search Explained with Java Solution (LeetCode 162)

Learn how to efficiently find a peak element in an array using binary search. This guide explains the problem clearly, builds intuition step-by-step, and walks through multiple approaches with a clean O(log n) solution.

Read Article
Search in Rotated Sorted Array II – Binary Search with Duplicates Explained (LeetCode 81)

Search in Rotated Sorted Array II – Binary Search with Duplicates Explained (LeetCode 81)

Learn how to search an element in a rotated sorted array that may contain duplicate values. This guide explains the intuition, challenges caused by duplicates, and a clean Java solution using modified binary search.

Read Article
Ai Assistant Kas