Minimum Operations to Make All Array Elements Equal

Minimum Operations to Make All Array Elements Equal - Problem

You are given an array nums consisting of positive integers.

You are also given an integer array queries of size m. For the ith query, you want to make all of the elements of nums equal to queries[i]. You can perform the following operation on the array any number of times:

Increase or decrease an element of the array by 1.

Return an array answer of size m where answer[i] is the minimum number of operations to make all elements of nums equal to queries[i].

Note: After each query the array is reset to its original state.

Input & Output

Example 1 — Basic Case

$ Input: nums = [2,4,6,8], queries = [3,1,5]

› Output: [4,14,8]

💡 Note: Query 3: |2-3|+|4-3|+|6-3|+|8-3| = 1+1+3+5 = 10. Query 1: |2-1|+|4-1|+|6-1|+|8-1| = 1+3+5+7 = 16. Query 5: |2-5|+|4-5|+|6-5|+|8-5| = 3+1+1+3 = 8

Example 2 — Single Element

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

› Output: [4]

💡 Note: Only one element: |1-5| = 4 operations needed

Example 3 — Target in Array

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

› Output: [4]

💡 Note: Target 2 exists: |1-2|+|2-2|+|3-2|+|4-2| = 1+0+1+2 = 4

Constraints

1 ≤ nums.length ≤ 10⁵
1 ≤ nums[i], queries[i] ≤ 10⁹
1 ≤ queries.length ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input

Array [2,4,6,8] and queries [3,1,5]

Process

Calculate |nums[i] - query| for each element

Output

Total operations needed: [10,16,8]

Key Takeaway

🎯 Key Insight: Sorting the array enables efficient prefix sum calculations to avoid recalculating operations for each query

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The key insight is that sorting the array enables efficient calculation using prefix sums and binary search. For each query, we find the insertion position and calculate operations for left and right parts separately. Best approach is prefix sum with sorting: Time O(n log n + m log n), Space O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n × m)	O(1)	For each query, calculate operations needed for every element individually
Prefix Sum with Sorting	O(n log n + m log n)	O(n)	Sort array and use prefix sums to efficiently calculate range operations

Brute Force — Algorithm Steps

For each query q
Sum |nums[i] - q| for all i
Add sum to result array

Visualization

Tap to expand

Step-by-Step Walkthrough

Query Target

Pick a target value from queries

Calculate Differences

Sum |nums[i] - target| for all elements

Store Result

Add total operations to result array

Code -

solution.c — C

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

int* parseArray(char* str, int* size) {
    int* arr = malloc(1000 * sizeof(int));
    *size = 0;
    char* token = strtok(str, "[],");
    while (token != NULL) {
        arr[(*size)++] = atoi(token);
        token = strtok(NULL, "[],");
    }
    return arr;
}

long long* solution(int* nums, int numsSize, int* queries, int queriesSize) {
    long long* result = malloc(queriesSize * sizeof(long long));
    for (int i = 0; i < queriesSize; i++) {
        long long operations = 0;
        for (int j = 0; j < numsSize; j++) {
            operations += abs(nums[j] - queries[i]);
        }
        result[i] = operations;
    }
    return result;
}

int main() {
    char line1[10000], line2[10000];
    fgets(line1, sizeof(line1), stdin);
    fgets(line2, sizeof(line2), stdin);
    
    int numsSize, queriesSize;
    int* nums = parseArray(line1, &numsSize);
    int* queries = parseArray(line2, &queriesSize);
    
    long long* result = solution(nums, numsSize, queries, queriesSize);
    
    printf("[");
    for (int i = 0; i < queriesSize; i++) {
        printf("%lld", result[i]);
        if (i < queriesSize - 1) printf(",");
    }
    printf("]\n");
    
    free(nums);
    free(queries);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × m)

For each of m queries, we iterate through n elements

✓ Linear Growth

Space Complexity

O(1)

Only using variables, result array doesn't count as extra space

✓ Linear Space

23.4K Views

Medium Frequency

~25 min Avg. Time

847 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

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler