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] <= 109To 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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1).
| 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. |
Leetcode 462. Minimum Moves to Equal Array Elements II • Code with Alisha • 17,191 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