Minimum Moves to Equal Array Elements II

Medium
479.

Minimum Moves to Equal Array Elements II

Minimum Moves to Equal Array Elements II is a medium coding problem on arrays, math and sorting, asked in Amazon, Google and Myntra interviews.

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] <= 1000000000
  • The answer fits in a 32-bit integer.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var minMoves2 = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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] <= 1000000000
  • The answer fits in a 32-bit integer.

Hints for Minimum Moves to Equal Array Elements II

  1. Hint 1

    The cost of choosing target t is sum |nums[i] - t|. Which t minimises that?

  2. Hint 2

    Pair the smallest with the largest: any t between them costs the same, and any t outside costs more.

  3. 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

  1. Sort a copy of nums.
  2. Take med = sorted[n / 2] (integer division — either middle works when n is even).
  3. 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