Minimum Moves to Equal Array Elements III

Difficulty: Easy | Acceptance: 81.70% | Paid: No Topics: Array, Math

You are given an integer array nums and an integer k. In one operation, you can increment or decrement an element by 1. You are allowed to perform a special operation at most k times: choose an index i and set nums[i] to any value. Return the minimum number of moves required to make all elements equal.

• Examples
• Constraints
• Brute Force (Sorting)
• Prefix Sum Optimization

Examples

Example 1

Input: nums = [1,2,3,4], k = 1
Output: 2
Explanation: We can change the last element 4 to 2 (special operation). 
The array becomes [1, 2, 3, 2]. 
We then need 1 move to change 1 to 2 and 1 move to change 3 to 2. 
Total moves = 2.

Example 2

Input: nums = [1,10,10,10], k = 1
Output: 0
Explanation: We can change the first element 1 to 10 (special operation). 
The array becomes [10, 10, 10, 10]. 
No moves needed.

Constraints

- 1 <= nums.length <= 100
- 1 <= nums[i] <= 100

Brute Force (Sorting)

Intuition If we can change k elements to any value for free, we effectively need to find a subset of n - k elements that are already close to each other. The cost to make a set of numbers equal is minimized when the target value is the median of that set. We can sort the array and check every possible window of size n - k.

Steps

• Sort the array nums.
• Calculate the window size m = n - k.
• Iterate through every possible window of size m in the sorted array.
• For each window, find the median (the middle element).
• Calculate the sum of absolute differences between all elements in the window and the median.
• Track the minimum sum found.

class Solution:
    def minMoves3(self, nums: list[int], k: int) -> int:
        nums.sort()
        n = len(nums)
        m = n - k
        if m <= 0:
            return 0
        
        min_cost = float('inf')
        
        # Iterate over all windows of size m
        for l in range(k + 1):
            r = l + m - 1
            mid = (l + r) // 2
            median = nums[mid]
            
            cost = 0
            # Calculate cost for this window
            for i in range(l, r + 1):
                cost += abs(nums[i] - median)
            
            min_cost = min(min_cost, cost)
            
        return min_cost

Complexity

• Time: O(n²) - In the worst case, we iterate through O(n) windows and sum O(n) elements for each.
• Space: O(1) or O(n) depending on the sorting implementation.
• Notes: Simple to implement but may time out for large inputs (n > 10⁴).

Prefix Sum Optimization

Intuition To optimize the calculation of the sum of absolute differences for each window, we can use a prefix sum array. This allows us to compute the sum of any subarray in O(1) time. The cost to equalize a window to its median can be broken down into the sum of elements to the left of the median and the sum of elements to the right of the median.

Steps

• Sort the array nums.
• Compute a prefix sum array prefix where prefix[i] is the sum of the first i elements.
• Iterate through every window of size m = n - k.
• For each window [l, r], find the median index mid.
• Calculate the sum of elements on the left of the median: left_sum = median * (mid - l) - (prefix[mid] - prefix[l]).
• Calculate the sum of elements on the right of the median: right_sum = (prefix[r + 1] - prefix[mid + 1]) - median * (r - mid).
• Total cost is left_sum + right_sum. Track the minimum.

class Solution:
    def minMoves3(self, nums: list[int], k: int) -> int:
        nums.sort()
        n = len(nums)
        m = n - k
        if m <= 0:
            return 0
        
        # Build prefix sum array
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i + 1] = prefix[i] + nums[i]
        
        min_cost = float('inf')
        
        for l in range(k + 1):
            r = l + m - 1
            mid = (l + r) // 2
            median = nums[mid]
            
            # Sum of elements to the left of median
            # median * count - actual_sum
            left_sum = median * (mid - l) - (prefix[mid] - prefix[l])
            
            # Sum of elements to the right of median
            # actual_sum - median * count
            right_sum = (prefix[r + 1] - prefix[mid + 1]) - median * (r - mid)
            
            total = left_sum + right_sum
            min_cost = min(min_cost, total)
            
        return min_cost

Complexity

• Time: O(n log n) - Sorting dominates the time complexity. The sliding window iteration is O(n).
• Space: O(n) - For the prefix sum array.
• Notes: This is the optimal approach for large input sizes.