Code Implementation

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

class Solution {
public:
    int minMoves2(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int median = nums[nums.size() / 2];
        int moves = 0;
        for (int num : nums) {
            moves += abs(num - median);
        }
        return moves;
    }
};
      

class Solution {
    public int minMoves2(int[] nums) {
        Arrays.sort(nums);
        int median = nums[nums.length / 2];
        int moves = 0;
        for (int num : nums) {
            moves += Math.abs(num - median);
        }
        return moves;
    }
}
      

var minMoves2 = function(nums) {
    nums.sort((a, b) => a - b);
    const median = nums[Math.floor(nums.length / 2)];
    let moves = 0;
    for (let num of nums) {
        moves += Math.abs(num - median);
    }
    return moves;
};
      

Problem Description

You are given an integer array nums. In one move, you can increment or decrement any element by 1 (i.e., increase or decrease its value by 1). The goal is to make all the elements in the array equal using the minimum number of moves.

Each move can be applied to any element as many times as needed, but you must minimize the total number of moves across all elements. There is always at least one valid solution.

Constraints:

• 1 ≤ nums.length ≤ 10⁵
• -10⁹ ≤ nums[i] ≤ 10⁹

Thought Process

At first glance, this problem seems to require trying all possible values to which we can make the array elements equal, and for each possibility, calculating the total number of moves. This brute-force approach would be too slow for large arrays.

The key insight is to realize that the cost to make all numbers equal to a target value is the sum of their absolute differences from that target. We need to find the target value that minimizes this sum. This is a classic problem in statistics: the minimum sum of absolute differences is achieved by the median of the array.

So, instead of brute-forcing every possible value, we can focus on the median of the array. This observation greatly simplifies and speeds up our solution.

Solution Approach

• Step 1: Sort the Array
  • Sorting is needed to efficiently find the median value of nums.
• Step 2: Find the Median
  • The median is the middle value if the array length is odd, or either of the two middle values if even (both give the same result for this problem).
  • Using the median minimizes the sum of absolute differences between all elements and the target value.
• Step 3: Calculate the Total Moves
  • For each element in nums, calculate abs(num - median) and sum these values.
  • This total is the minimum number of moves needed to equalize the array.

We use sorting because it allows us to find the median in O(n log n) time, and then a single pass (O(n)) to compute the moves. This is efficient even for large arrays.

Example Walkthrough

Let's consider the input nums = [1, 2, 3].

• Sort the array: [1, 2, 3]
• Find the median: 2 (middle value)
• Compute moves:
  • |1 - 2| = 1
  • |2 - 2| = 0
  • |3 - 2| = 1
  Total moves = 1 + 0 + 1 = 2

So, the minimum number of moves required is 2. If we tried to make all elements equal to 1 or 3, the total moves would be higher (3 in both cases). Thus, choosing the median minimizes the total moves.

Time and Space Complexity

• Brute-force approach:
  • For each possible target value (between min and max of nums), calculate the sum of absolute differences. This is O(n * k), where k is the range of possible values. This is not feasible for large inputs.
• Optimized approach (using the median):
  • Sorting the array: O(n log n)
  • Finding the median: O(1) after sorting
  • Summing absolute differences: O(n)
  • Total time complexity: O(n log n)
  • Space complexity: O(1) if sorting in place, otherwise O(n) if extra space is used for sorting

Summary

The problem asks us to minimize the number of moves needed to make all elements in an array equal, where each move increments or decrements an element by 1. The optimal solution is to make all elements equal to the median of the array, as this minimizes the sum of absolute differences. By sorting the array and calculating the total moves to the median, we achieve an efficient O(n log n) solution. This approach leverages a key mathematical insight, making the solution both elegant and practical for large inputs.