We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Moves to Equal Array Elements II

Number: 462

Difficulty: Medium

Paid? No

Companies: Myntra, Google, Microsoft, Adobe

Problem Description

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 by 1.

Key Insights

  • The optimal target value to minimize total moves is the median of the array.
  • Sorting the array helps in finding the median easily.
  • The sum of absolute differences between each element and the median gives the minimum moves.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting
Space Complexity: O(n) (or O(1) if sorting is done in-place)

Solution

We first sort the array to locate the median. The median minimizes the sum of absolute differences from all elements, which means aligning all elements to the median will yield the fewest moves. After determining the median, we iterate through the array, summing the absolute differences between each element and the median. This summation gives the minimum moves necessary. Note that when the array has an even number of elements, any number between the two central elements serves as an optimal pivot.

Code Solutions

# Python solution for Minimum Moves to Equal Array Elements II

def minMoves2(nums):
    # Sort the array to find the median
    nums.sort()
    n = len(nums)
    # The median is the middle element in the sorted array
    median = nums[n // 2]
    # Calculate the sum of moves required to make all elements equal to the median
    moves = sum(abs(num - median) for num in nums)
    return moves

# Example usage:
if __name__ == "__main__":
    nums = [1, 2, 3]
    print(minMoves2(nums))  # Output: 2
← Back to All Questions