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.
To minimize the number of moves, the optimal strategy is to move all numbers to the median of the array. The median minimizes the sum of absolute deviations (L1 norm), which provides the least number of moves required to make all elements equal. By sorting the array and picking the middle element (or the average of two middle elements for an even-sized array), we can find the median efficiently.
The solution sorts the array and then calculates the number of moves needed by summing the absolute differences between each element and the median. The C standard library function qsort is used for sorting.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) for in-place operations aside from sort implementation.
This approach uses a two-pointer technique on a sorted version of the array to calculate the minimum moves. We initialize two pointers, one at the beginning and the other at the end of the sorted array. By incrementing the left pointer and decrementing the right pointer, we accumulate the number of moves required to make each element pair equal.
This C solution sorts the array and uses a two-pointer method to accumulate the minimum moves. The difference between the elements pointed by the pointers yields the moves required to equalize them.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1).
This problem can be abstracted to finding a point on a number line such that the sum of distances from n points to this point is minimized. The answer is the median of the n points.
The median has the property that the sum of distances from all numbers to the median is minimized.
Proof:
First, given a sorted sequence a_1, a_2, cdots, a_n, we assume x is the point that minimizes the sum of distances from a_1 to a_n. Clearly, x must lie between a_1 and a_n. Since the distances from a_1 and a_n to x are equal and both equal to a_n - a_1, we can ignore a_1 and a_n and only consider a_2, a_3, cdots, a_{n-1}. This reduces the problem to finding a point within a_2, a_3, cdots, a_{n-1} that minimizes the sum of distances. By iterating this process, we conclude that the median of a sequence minimizes the sum of distances to the other numbers.
In this problem, we can first sort the array, then find the median, and finally calculate the sum of distances from all numbers to the median.
The time complexity is O(n log n), and the space complexity is O(log n).
Similar problems:
| Approach | Complexity |
|---|---|
| Median as Optimal Point | Time Complexity: O(n log n) due to sorting. |
| Two Pointers Technique | Time Complexity: O(n log n) due to sorting. |
| Sorting + Median | — |
| 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 |
Minimum Moves to Equal Array Elements II | Live Coding with Explanation | Leetcode - 462 • Algorithms Made Easy • 18,042 views views
Watch 9 more video solutions →Practice Minimum Moves to Equal Array Elements II with our built-in code editor and test cases.
Practice on FleetCode