Minimum Moves to Equal Array Elements II - Practice Coding Problems

Minimum Moves to Equal Array Elements II - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,2,3]

› Output: 2

💡 Note: Only two moves are needed (remember that it is an array): [1,2,3] => [2,2,3] => [2,2,2]

Example 2 — Single Element

$ Input: nums = [1,10,2,9]

› Output: 16

💡 Note: Sort to [1,2,9,10]. Median is 2 or 9, both give same result. Using median approach: target could be any value between 2 and 9, let's use 5.5 rounded to 6: |1-6| + |2-6| + |9-6| + |10-6| = 5+4+3+4 = 16. Actually optimal is median 2: |1-2| + |2-2| + |9-2| + |10-2| = 1+0+7+8 = 16

Example 3 — All Equal

$ Input: nums = [5,5,5]

› Output: 0

💡 Note: All elements are already equal, so no moves needed

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input Array

Given array with different values

Find Target

Median minimizes total moves

Calculate Moves

Sum absolute differences to median

Key Takeaway

🎯 Key Insight: The median of a sorted array minimizes the sum of absolute deviations

Asked in

G Google 15 f Facebook 12 M Microsoft 8 a Amazon 6

The key insight is that the median minimizes the sum of absolute deviations. Sort the array and use the median as target, or use two pointers to pair elements from ends. Best approach is median-based with Time: O(n log n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Sort and Find Median	O(n log n)	O(1)	Sort array and use median as optimal target to minimize total moves
Try All Target Values	O(range × n)	O(1)	Test every possible target value from min to max and find minimum moves
Two Pointers from Ends	O(n log n)	O(1)	Use two pointers from ends of sorted array to calculate moves efficiently

Sort and Find Median — Algorithm Steps

Sort the array
Find median (middle element)
Calculate sum of absolute differences from median

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort Array

Arrange elements: [1,3,3,4]

Find Median

Middle element at index 2: value=3

Calculate Moves

Sum distances to median: 2+0+0+1=3

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int abs_val(int x) {
    return x < 0 ? -x : x;
}

int solution(int* nums, int numsSize) {
    if (numsSize == 0) return 0;
    
    qsort(nums, numsSize, sizeof(int), compare);
    int median = nums[numsSize / 2];
    
    int moves = 0;
    for (int i = 0; i < numsSize; i++) {
        moves += abs_val(nums[i] - median);
    }
    
    return moves;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int numsSize = 0;
    
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%d\n", solution(nums, numsSize));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting takes O(n log n), calculating moves takes O(n)

⚡ Linearithmic

Space Complexity

O(1)

Only using constant extra space for variables

✓ Linear Space

125.0K Views

Medium Frequency

~15 min Avg. Time

1.9K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sort and Find Median — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler