Minimum Moves to Equal Array Elements II
MedPrompt
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] <= 109
Approaches
3 approaches with complexity analysis and trade-offs.
This approach considers every possible integer value between the minimum and maximum elements of the array as a potential target to which all elements could be made equal. For each potential target, it calculates the total number of moves required and keeps track of the minimum moves found.
Algorithm
- Find the minimum (
minVal) and maximum (maxVal) values in the input arraynums. - Initialize a variable
minMovesto a very large number (e.g.,Long.MAX_VALUE). - Loop through each integer
targetfromminValtomaxVal. - Inside the loop, calculate the
currentMovesby summing up the absolute differences|num - target|for everynuminnums. - Update
minMoves = Math.min(minMoves, currentMoves). - After the loop finishes,
minMoveswill hold the minimum number of moves.
Walkthrough
The core idea is that the optimal target value must lie within the range of the array's elements, i.e., between min(nums) and max(nums). If we choose a target outside this range, we can always find a better target within the range that requires fewer moves. Therefore, we can iterate through every integer from the minimum value to the maximum value present in the array. For each of these integers, we treat it as the target and calculate the sum of absolute differences from all elements in nums. The minimum of these sums is the answer. This method is straightforward but highly inefficient due to the potentially vast range of values between the minimum and maximum elements.
class Solution { public int minMoves2(int[] nums) { if (nums == null || nums.length == 0) { return 0; } int minVal = Integer.MAX_VALUE; int maxVal = Integer.MIN_VALUE; for (int num : nums) { minVal = Math.min(minVal, num); maxVal = Math.max(maxVal, num); } long minMoves = Long.MAX_VALUE; // This will time out due to large range of minVal to maxVal for (long target = minVal; target <= maxVal; target++) { long currentMoves = 0; for (int num : nums) { currentMoves += Math.abs(num - target); } minMoves = Math.min(minMoves, currentMoves); } return (int) minMoves; }}Complexity
Time
O(R * N), where N is the number of elements in `nums` and R is the range `max(nums) - min(nums)`. The outer loop runs R times, and for each iteration, we iterate through all N elements. Given the constraints, R can be up to 2 * 10^9, making this approach infeasible.
Space
O(1), as we only use a few variables to store the min/max values and the running sum of moves.
Trade-offs
Pros
Simple to understand and implement.
Cons
Extremely inefficient and will time out for large ranges of input values.
Performs a lot of redundant calculations.
A more efficient approach is based on the mathematical insight that the sum of absolute differences is minimized when the target value is the median of the array. This approach first sorts the array. Instead of explicitly calculating the median, it uses a two-pointer technique on the sorted array to sum the differences between symmetric elements, which is equivalent to summing the absolute differences from the median.
Algorithm
- Sort the input array
numsin non-decreasing order. - Initialize a variable
movesto 0. - Initialize two pointers,
i = 0andj = nums.length - 1. - While
i < j:- Add the difference
nums[j] - nums[i]tomoves. - Increment
iand decrementj.
- Add the difference
- Return the total
moves.
Walkthrough
The problem of minimizing sum(|nums[i] - x|) is a classic one, and the optimal value for x is the median of the elements in nums. After sorting the array, we can find the median and sum the absolute differences. However, a more elegant calculation is possible. Consider the sorted array. The total moves is sum(|nums[i] - median|). This can be rewritten by pairing the smallest element with the largest, the second smallest with the second largest, and so on. For each pair (nums[i], nums[n-1-i]), the number of moves to make them both equal to the median is (median - nums[i]) + (nums[n-1-i] - median) = nums[n-1-i] - nums[i]. Summing this over all such pairs gives the total minimum moves. This can be implemented efficiently using two pointers, one starting from the beginning (i) and one from the end (j) of the sorted array, moving inwards.
import java.util.Arrays; class Solution { public int minMoves2(int[] nums) { Arrays.sort(nums); long moves = 0; int i = 0, j = nums.length - 1; while (i < j) { moves += nums[j] - nums[i]; i++; j--; } return (int) moves; }}Complexity
Time
O(N log N), where N is the number of elements in the array. The dominant operation is sorting the array. The subsequent two-pointer traversal takes O(N) time.
Space
O(log N) to O(N), depending on the implementation of the sorting algorithm. In Java, `Arrays.sort()` for primitive types uses a variant of Quicksort which requires O(log N) space on average for the recursion stack, but can take O(N) in the worst case.
Trade-offs
Pros
Much more efficient than the brute-force approach.
Relatively easy to implement using standard library functions.
Guaranteed to find the optimal solution.
The two-pointer implementation is clean and efficient.
Cons
The O(N log N) time complexity is not the absolute best possible, as sorting the entire array is more work than is strictly necessary.
This is the most optimal approach in terms of average-case time complexity. Instead of sorting the entire array to find the median, we can use a selection algorithm like Quick-select to find the median (the k-th smallest element, where k = n/2) in linear time on average. Once the median is found, the total moves are calculated as before.
Algorithm
- Define a function
quickSelect(nums, k)to find the k-th smallest element. This function will partition the array and recursively call itself on the correct partition. - Call
quickSelect(nums, nums.length / 2)to find the median. - Once the median is found, calculate the sum of absolute differences:
sum(|num - median|)for allnuminnums. - Return the calculated sum.
Walkthrough
The Quick-select algorithm is a selection algorithm to find the k-th smallest element in an unordered list. It is related to the Quicksort sorting algorithm. Like Quicksort, it uses a pivot to partition the array into two parts: elements smaller than the pivot and elements larger than the pivot. However, instead of recursing into both sides, it only recurses into the side that contains the k-th element. This reduces the average complexity from O(N log N) to O(N). The steps are:
- Find the median element using Quick-select. The median is the element that would be at index
n/2in a sorted array. - Once the median is identified, iterate through the array one more time to sum up the absolute differences from this median. This avoids the cost of a full sort.
class Solution { public int minMoves2(int[] nums) { int median = findKthSmallest(nums, nums.length / 2); long moves = 0; // Use long to prevent potential overflow for (int num : nums) { moves += Math.abs(num - median); } return (int) moves; } // Helper function to find the (k)-th smallest element (k-th index) private int findKthSmallest(int[] nums, int k) { int left = 0, right = nums.length - 1; while (left < right) { int pivotIndex = partition(nums, left, right); if (pivotIndex == k) { return nums[pivotIndex]; } else if (pivotIndex < k) { left = pivotIndex + 1; } else { right = pivotIndex - 1; } } return nums[left]; } private int partition(int[] nums, int left, int right) { // A simple pivot selection (last element). Can be improved. int pivotValue = nums[right]; int storeIndex = left; for (int i = left; i < right; i++) { if (nums[i] < pivotValue) { swap(nums, storeIndex, i); storeIndex++; } } swap(nums, storeIndex, right); return storeIndex; } private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; }}Complexity
Time
O(N) on average. The Quick-select algorithm has a linear time complexity on average. The recurrence is T(N) = T(N/2) + O(N), which resolves to O(N). In the worst case (due to poor pivot selection), it can degrade to O(N^2). The final summation step is O(N).
Space
O(1) for an iterative implementation of Quick-select as shown. A recursive implementation would take O(log N) space on average for the call stack, and O(N) in the worst case.
Trade-offs
Pros
The most time-efficient approach on average.
Avoids the overhead of a full sort.
Cons
More complex to implement correctly compared to the sorting approach.
Has a worst-case time complexity of O(N^2), although this is rare in practice with good pivot strategies.
Solutions
Solution
class Solution {public int minMoves2(int[] nums) { Arrays.sort(nums); int k = nums[nums.length >> 1]; int ans = 0; for (int v : nums) { ans += Math.abs(v - k); } return ans; }}class Solution {public: int minMoves2(vector<int> &nums) { sort(nums.begin(), nums.end()); int k = nums[nums.size() >> 1]; int ans = 0; for (int &v : nums) ans += abs(v - k); return ans; }};class Solution: def minMoves2(self, nums: List[int]) -> int: nums . sort() k = nums[len(nums) >> 1] return sum(abs(v - k) for v in nums)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.