algoadvance

Leetcode 462. Minimum Moves to Equal Array Elements II

Problem Statement

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.

Example

Input: nums = [1,2,3]
Output: 2
Explanation:
Only two moves are needed (2 moves from 3 to 1 or from 1 to 3).

Clarifying Questions

  1. Q: Can I assume the input array will always contain at least one element? A: Yes, you can assume that the array will have at least one element.

  2. Q: Is the input array guaranteed to contain only integers? A: Yes, the array will contain only integer values.

  3. Q: Are there any constraints on the values of the integers in the input array? A: There are no explicit constraints mentioned, so we assume typical constraints for integers in a programming context.

  4. Q: Can the elements of the array be negative? A: Yes, elements can be negative as well as positive or zero.

Strategy

To minimize the number of moves to make all array elements equal, we need to equalize all elements to a central value. The optimal strategy is to make all the elements equal to the median of the array. This is because the median minimizes the sum of absolute deviations, which corresponds to the minimum number of moves.

Steps

  1. Sort the array.
  2. Find the median of the array.
  3. Calculate the total moves required to make all elements equal to the median.

Code

Here is the C++ implementation of the approach:

#include <vector>
#include <algorithm>

class Solution {
public:
    int minMoves2(std::vector<int>& nums) {
        // Step 1: Sort the array
        std::sort(nums.begin(), nums.end());
        
        // Step 2: Find the median
        int median = nums[nums.size() / 2];
        
        // Step 3: Calculate the total moves required to make all elements equal to the median
        int moves = 0;
        for(int num : nums) {
            moves += std::abs(num - median);
        }
        
        return moves;
    }
};

Time Complexity

  1. Sorting the array: (O(n \log n))
  2. Finding the median: (O(1)) (after sorting)
  3. Calculating the total moves: (O(n))

Hence, the overall time complexity is dominated by the sorting step, so it is (O(n \log n)).

By minimizing the sum of absolute deviations using the median, we ensure that the number of moves is as small as possible.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI