LogoKode$word
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)

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.

10 views
0
0
MathMedianMediumLeetCodeJavaArrayTwo PointerSorting
Github icon
Github icon
Listen to articleAudio version

Introduction

LeetCode 462 is a classic mathematical and greedy problem.

We are given an integer array where each operation allows us to:

  1. Increment an element by 1
  2. Decrement an element by 1

Our task is to make all numbers equal while using the minimum number of moves.

At first glance, this may look like a simple array problem.

But the hidden concept behind this question is:

  1. Median property
  2. Greedy optimization
  3. Absolute difference minimization

This problem is extremely popular in coding interviews because it tests logical thinking more than coding complexity.

# Problem Link

Problem Statement

You are given an integer array nums.

In one move:

  1. You can increase an element by 1
  2. Or decrease an element by 1

You must make all array elements equal.

Return the minimum number of operations required.

Example 1

Input:
nums = [1,2,3]

Output:
2

Explanation:

[1,2,3]
→ [2,2,3]
→ [2,2,2]

Total operations = 2

Example 2

Input:
nums = [1,10,2,9]

Output:
16

Key Observation

We need to choose one target value such that all numbers move toward it.

Question:

Which target gives minimum total moves?

Answer:

Median

Median minimizes the sum of absolute differences.

Why Median Works?

Suppose:

nums = [1,2,3,10]

If target = 2

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

If target = 5

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

Median gives minimum moves.

Approach 1: Brute Force

In this approach, we try every possible value as target.

For each target:

  1. Calculate total operations needed
  2. Store minimum answer

Algorithm

  1. Find minimum and maximum element
  2. Try every value between them
  3. Compute total moves
  4. Return minimum

Java Code (Brute Force)

class Solution {
public int minMoves2(int[] nums) {
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;

for (int num : nums) {
min = Math.min(min, num);
max = Math.max(max, num);
}

int result = Integer.MAX_VALUE;

for (int target = min; target <= max; target++) {
int moves = 0;

for (int num : nums) {
moves += Math.abs(num - target);
}

result = Math.min(result, moves);
}

return result;
}
}

Time Complexity

O(N × Range)

Very slow for large values.

Approach 2: Sorting + Median (Optimal)

This is the best and most commonly used approach.

Idea

  1. Sort array
  2. Pick median element
  3. Calculate total absolute difference

Steps

Step 1: Sort Array

Sorting helps us easily find median.

Step 2: Pick Median

Median index = n / 2

Step 3: Calculate Moves

For every element:

moves += abs(median - value)

Optimal Java Solution

class Solution {
public int minMoves2(int[] nums) {
Arrays.sort(nums);

int mid = nums.length / 2;
int ans = 0;

for (int i = 0; i < nums.length; i++) {
int diff = Math.abs(nums[mid] - nums[i]);
ans += diff;
}

return ans;
}
}

Code Explanation

Step 1: Sort Array

Arrays.sort(nums);

Sorting allows median calculation.

Step 2: Get Median

int mid = nums.length / 2;

Middle element becomes target.

Step 3: Compute Difference

Math.abs(nums[mid] - nums[i])

Find distance from median.

Step 4: Add All Moves

ans += diff;

Store total moves.

Approach 3: Two Pointer Optimization

After sorting, we can use two pointers.

Instead of calculating absolute difference manually, we can pair smallest and largest values.

Idea

After sorting:

moves += nums[right] - nums[left]

Because both numbers will meet toward median.

Java Code (Two Pointer)

class Solution {
public int minMoves2(int[] nums) {
Arrays.sort(nums);

int left = 0;
int right = nums.length - 1;
int moves = 0;

while (left < right) {
moves += nums[right] - nums[left];
left++;
right--;
}

return moves;
}
}

Why Two Pointer Works?

Because:

Median minimizes total distance

Pairing smallest and largest values gives direct movement cost.

Dry Run

Input:

nums = [1,10,2,9]

Sort:

[1,2,9,10]

Median:

9

Operations:

|1-9| = 8
|2-9| = 7
|9-9| = 0
|10-9| = 1

Total:

16

Time Complexity

Sorting

O(N log N)

Traversing

O(N)

Total

O(N log N)

Space Complexity

O(1)

Ignoring sorting stack.

Common Mistakes

1. Using Average Instead of Median

Many people think average gives minimum.

Wrong.

Average minimizes squared difference.

Median minimizes absolute difference.

2. Forgetting Sorting

Median requires sorted order.

3. Overflow Issue

Values can be large.

Sometimes use:

long ans

for safer calculation.

4. Using Wrong Median Index

Correct:

n / 2

Edge Cases

Case 1

Single element array.

Answer = 0

Case 2

All elements already equal.

Answer = 0

Case 3

Negative numbers.

Algorithm still works.

FAQs

Q1. Why median gives minimum moves?

Median minimizes total absolute difference.

Q2. Can average work?

No.

Average does not minimize absolute distance.

Q3. Is sorting necessary?

Yes.

Sorting helps us easily find median.

Q4. Which approach is best?

Sorting + median approach.

Interview Insight

Interviewers ask this problem to test:

  1. Median property understanding
  2. Greedy optimization
  3. Mathematical thinking
  4. Array manipulation

Conclusion

LeetCode 462 is one of the most important median-based interview questions.

The major learning is:

  1. Median minimizes total absolute difference
  2. Sorting makes finding median easy
  3. Sum of distances gives answer

Once you understand why median works, this question becomes very simple.

Related Articles

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.

Read Article
Find First and Last Position in Sorted Array – From Brute Force to Binary Search (LeetCode 34)

Find First and Last Position in Sorted Array – From Brute Force to Binary Search (LeetCode 34)

Optimizing from O(n) Linear Scan to O(log n) Binary Search

Read Article
Find Minimum in Rotated Sorted Array – Binary Search Explained | LeetCode Medium 153

Find Minimum in Rotated Sorted Array – Binary Search Explained | LeetCode Medium 153

LeetCode 153 – Find the minimum element in a rotated sorted array in O(log n) time.

Read Article
LeetCode 1855 Maximum Distance Between Pair of Values | Two Pointer Java Solution

LeetCode 1855 Maximum Distance Between Pair of Values | Two Pointer Java Solution

Learn how to solve LeetCode 1855 using the two-pointer technique. Includes intuition, dry run, optimized Java code, and alternative approaches.

Read Article
Ai Assistant Kas