462. Minimum Moves to Equal Array Elements II
- Array
- Math
- Sorting
TIME
O(n) expected
SPACE
O(n)
Intuition
Every element moves to a common target t, at a cost of sum(|x - t|). Picture t on the number line: shifting it one step right makes it 1 closer to every element on its right and 1 farther from every element on its left. So the total keeps falling while more elements lie on one side than on the other, and it stops at the point where both sides are equal. That point is the median.
Sorting finds the median in O(n log n), but only the median is needed, not the whole order. Quickselect finds it in expected O(n).
Approach
- Quickselect the element of rank
n // 2:- pick a random pivot and three-way partition the range into
< pivot,== pivot,> pivot; - if the target rank is in the middle band, the pivot is the median; otherwise keep only the side that holds it.
- pick a random pivot and three-way partition the range into
- Return
sum(|x - median|).
For an even n, any t between the two middle values gives the same total, so the upper middle works.
Complexity
- Time: O(n) expected (quickselect with a random pivot); O(n^2) only with vanishingly unlikely pivot choices
- Space: O(1) extra in Java (in-place partition); O(n) in Python, which partitions into new lists because list comprehensions are much faster than index swaps there
Edge Cases
- One element or all equal: 0 moves
- Many duplicates: the three-way partition keeps quickselect linear instead of degrading on runs of equal values
- Even
n: either middle element is optimal - Already sorted or reverse sorted input: the random pivot keeps the expected time linear
- A single difference can be up to
2 * 10^9, pastint, so Java sums|x - median|in along; the total fits in anintby the problem's guarantee
Code
import random
class Solution:
def minMoves2(self, nums: list[int]) -> int:
"""
462. Minimum Moves to Equal Array Elements II
Time: O(n) expected
Space: O(n)
"""
# The median minimises the sum of absolute differences. Quickselect the
# element of rank n // 2 with a random pivot and a three-way split.
arr, k = nums, len(nums) // 2
while True:
pivot = random.choice(arr)
lo = [x for x in arr if x < pivot]
if k < len(lo):
arr = lo
continue
hi = [x for x in arr if x > pivot]
eq = len(arr) - len(lo) - len(hi)
if k < len(lo) + eq:
median = pivot
break
k -= len(lo) + eq
arr = hi
return sum(abs(x - median) for x in nums)import java.util.concurrent.ThreadLocalRandom;
/**
* 462. Minimum Moves to Equal Array Elements II
* Time: O(n) expected
* Space: O(1)
*/
class Solution {
public int minMoves2(int[] nums) {
int median = select(nums, nums.length / 2);
long moves = 0;
for (int x : nums) {
moves += Math.abs((long) x - median);
}
return (int) moves;
}
// Quickselect: returns the element of rank k (0-indexed) and reorders nums in place.
// Random pivot, three-way partition so runs of equal values stay linear.
private int select(int[] nums, int k) {
ThreadLocalRandom rnd = ThreadLocalRandom.current();
int lo = 0, hi = nums.length - 1;
while (true) {
int pivot = nums[lo + rnd.nextInt(hi - lo + 1)];
// After the loop: [lo, lt) < pivot, [lt, gt] == pivot, (gt, hi] > pivot.
int lt = lo, i = lo, gt = hi;
while (i <= gt) {
if (nums[i] < pivot) {
swap(nums, lt++, i++);
} else if (nums[i] > pivot) {
swap(nums, i, gt--);
} else {
i++;
}
}
if (k < lt) {
hi = lt - 1;
} else if (k > gt) {
lo = gt + 1;
} else {
return pivot;
}
}
}
private void swap(int[] a, int i, int j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}
}