Minimum Moves to Equal Array Elements II — Solution
Minimum Moves to Equal Array Elements II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Minimum Moves to Equal Array Elements II is a medium coding problem on arrays, math and sorting, asked in Amazon, Google and Myntra interviews.
- Difficulty: Medium
- Topics: Arrays, Math, Sorting
- Asked at: Amazon, Google, Myntra
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an integer array nums of size n, return the minimum number of moves required to make all elements equal.
In one move you may increment or decrement a single element by 1.
Example 1
Input: nums = [1,2,3]
Output: 2
Explanation: Move both 1 and 3 to 2: one move each.
Example 2
Input: nums = [1,10,2,9]
Output: 16
Example 3
Input: nums = [1,0,0,8,6]
Output: 14
Constraints
1 <= nums.length <= 100000-1000000000 <= nums[i] <= 1000000000The answer fits in a 32-bit integer.
Hints for Minimum Moves to Equal Array Elements II
Hint 1
The cost of choosing target
tissum |nums[i] - t|. Whichtminimises that?Hint 2
Pair the smallest with the largest: any
tbetween them costs the same, and anytoutside costs more.Hint 3
Peeling pairs inward leaves the median as the optimal target.
How to solve Minimum Moves to Equal Array Elements II
The cost function f(t) = Σ|nums[i] - t| is minimised at the median, not the mean. Sorting exposes it directly.
Approach
- Sort a copy of
nums. - Take
med = sorted[n / 2](integer division — either middle works whennis even). - Return
Σ |nums[i] - med|.
Why it works
Match the smallest element with the largest. Any target between them costs exactly their difference; any target outside costs more. Removing that pair leaves the same subproblem, so the optimum is squeezed to the middle element(s) — the median.
Complexity
- Time —
O(n log n) - Space —
O(n) for the sorted copy
Pitfalls
- Using the mean is wrong:
[1,0,0,8,6]has mean 3 (cost 15) but median 1 (cost 14). - With values up to 1e9 the running total overflows 32 bits — accumulate in 64 bits.
- Sorting the caller's array in place is fine here, but the two-pointer form
Σ (sorted[n-1-i] - sorted[i])avoids picking a median at all.
Reference solution
Python
from typing import List
def minMoves2(nums: List[int]) -> int:
s = sorted(nums)
med = s[len(s) // 2]
return sum(abs(x - med) for x in s)Java
public static int minMoves2(int[] nums) {
int[] s = nums.clone();
Arrays.sort(s);
int med = s[s.length / 2];
long total = 0;
for (int x : s) total += Math.abs((long) x - med);
return (int) total;
}C++
int minMoves2(vector<int>& nums) {
vector<int> s = nums;
sort(s.begin(), s.end());
long long med = s[s.size() / 2];
long long total = 0;
for (int x : s) total += llabs((long long) x - med);
return (int) total;
}JavaScript
var minMoves2 = function(nums) {
const s = nums.slice().sort(function(a, b) { return a - b; });
const med = s[Math.floor(s.length / 2)];
let total = 0;
for (let i = 0; i < s.length; i++) total += Math.abs(s[i] - med);
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms