Skip to main content

Minimum Moves to Equal Array Elements II

LeetCode 462 | Difficulty: Medium​

Medium

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 of the array by 1.

Test cases are designed so that the answer will fit in a 32-bit integer.

Example 1:

Input: nums = [1,2,3]
Output: 2
Explanation:
Only two moves are needed (remember each move increments or decrements one element):
[1,2,3]  =>  [2,2,3]  =>  [2,2,2]

Example 2:

Input: nums = [1,10,2,9]
Output: 16

Constraints:

- `n == nums.length`

- `1 <= nums.length <= 10^5`

- `-10^9 <= nums[i] <= 10^9`

Topics: Array, Math, Sorting

Approach​

Mathematical​

Look for mathematical patterns or formulas. Consider: modular arithmetic, GCD/LCM, prime factorization, combinatorics, or geometric properties.

When to use

Problems with clear mathematical structure, counting, number properties.

Sorting​

Sort the input to bring related elements together or enable binary search. Consider: does sorting preserve the answer? What property does sorting give us?

When to use

Grouping, finding closest pairs, interval problems, enabling two-pointer or binary search.

Solutions​

Solution 1: C# (Best: 151 ms)​

MetricValue
Runtime151 ms
Memory39.2 MB
Date2022-02-09
Solution
public class Solution {
    public int MinMoves2(int[] nums) {
        Array.Sort(nums);
    int len = nums.Length;
    int median = (len%2==0) ? (nums[len/2]+nums[len/2-1])/2 : nums[len/2];
    int moves = 0;
    for(int i = 0;i<len;i++)
    {
        moves += Math.Abs(median-nums[i]);  
    }
    return moves;
    }
}

Complexity Analysis​

ApproachTimeSpace
Sort + Process$O(n log n)$$O(1) to O(n)$

Interview Tips​

Key Points
  • Discuss the brute force approach first, then optimize. Explain your thought process.