algoadvance

You are 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.

Clarifying Questions:

  1. Q: Is there a constraint on the size of the array? A: The array size n can be large, but typically will be up to 50,000 as per common constraints.

  2. Q: What range can the elements of the array nums take? A: They can be any integer value, including negative integers.

  3. Q: What does a move exactly entail? A: In one move, you can increase or decrease an element by 1. For example, moving an element value from 5 to 10 would take 5 moves.

Strategy:

The problem is about minimizing the sum of absolute differences to a chosen value. This is a common median problem:

  1. Sort the array.
  2. The minimum number of moves to make all elements equal is to convert all elements to the median element’s value. This is because the median minimizes the sum of absolute deviations.

Steps to implement:

  1. Sort the array.
  2. Calculate the median (for even-sized arrays, either of the middle elements will work because absolute differences to both are the same for all elements).
  3. Sum up the absolute differences of all elements to this median value.

Time Complexity:

Sorting takes (O(n \log n)) and traversing the array takes (O(n)). Thus, the overall time complexity is dominated by the sorting step, making it (O(n \log n)).

Code:

def minMoves2(nums):
    nums.sort()
    median = nums[len(nums) // 2]
    return sum(abs(num - median) for num in nums)

# Example Usage
print(minMoves2([1,2,3]))   # Output: 2, since we can make 1 and 3 both equal to 2
print(minMoves2([1,10,2,9]))# Output: 16, since we can make 1, 2, and 9 all equal to 10 or vice-versa

In this implementation, we first sort the array to find the median. Then, we calculate the sum of absolute differences to the median. This ensures that we get the minimum number of moves required to make all elements equal.

Try our interview co-pilot at AlgoAdvance.com