Watch 10 video solutions for Minimum Moves to Equal Array Elements II, a medium level problem involving Array, Math, Sorting. This walkthrough by Algorithms Made Easy has 18,042 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given an integer array nums of size n, return the minimum number of moves required to make all array elements equal.
In one move, you can increment or decrement an element of the array by 1.
Test cases are designed so that the answer will fit in a 32-bit integer.
Example 1:
Input: nums = [1,2,3] Output: 2 Explanation: Only two moves are needed (remember each move increments or decrements one element): [1,2,3] => [2,2,3] => [2,2,2]
Example 2:
Input: nums = [1,10,2,9] Output: 16
Constraints:
n == nums.length1 <= nums.length <= 105-109 <= nums[i] <= 109Problem Overview: You are given an integer array where one move allows incrementing or decrementing a single element by 1. The goal is to make all elements equal using the minimum number of moves. The challenge is choosing the optimal target value that minimizes the total distance from every element.
Approach 1: Median as Optimal Point (Sorting + Math) (Time: O(n log n), Space: O(1) or O(n) depending on sorting)
The key insight comes from math: the sum of absolute differences |a[i] − x| is minimized when x is the median of the array. Start by sorting the array using a sorting algorithm. Once sorted, pick the middle element as the median. Then iterate through the array and accumulate abs(num - median) for each value. This works because moving values toward the median minimizes total movement compared with choosing the mean or any other value.
This approach is straightforward and reliable in interviews. Sorting costs O(n log n) time, while the final pass to compute moves takes O(n). Extra space is constant if the language sorts in place.
Approach 2: Two Pointers Technique (Sorted Array Pair Balancing) (Time: O(n log n), Space: O(1))
After sorting the array, you can compute the same result without explicitly calculating the median. Use two pointers: one at the start and one at the end of the array. Each pair contributes nums[right] - nums[left] moves because both numbers will eventually meet at the median. Move the pointers inward until they meet. The accumulated difference across all pairs equals the minimum moves required.
This works because every pair of elements symmetrically approaches the median during optimal adjustments. Sorting groups values so the smallest and largest converge step by step. The two‑pointer scan runs in O(n) time after sorting and uses constant extra space.
The problem is fundamentally about minimizing absolute distance in an array. Both methods rely on the same mathematical property of medians. The difference lies in implementation style: explicitly computing the median versus aggregating pair differences.
Recommended for interviews: The median insight is what interviewers want to see. Explaining why the median minimizes absolute distance demonstrates algorithmic reasoning. Implementing the two‑pointer version afterward shows you understand how the sorted structure leads to the same result efficiently.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Median as Optimal Point | O(n log n) | O(1) | General case; easiest implementation when you directly compute the median |
| Two Pointers on Sorted Array | O(n log n) | O(1) | When the array is already sorted or when you prefer pair balancing logic |