Minimum Operations to Make Subarray Elements Equal

Minimum Operations to Make Subarray Elements Equal - Problem

Array Hash Table Math Sliding Window Heap (Priority Queue) Medium

You are given an integer array nums and an integer k. You can perform the following operation any number of times:

Increase or decrease any element of nums by 1.

Return the minimum number of operations required to ensure that at least one subarray of size k in nums has all elements equal.

Input & Output

Example 1 — Basic Case

$ Input: nums = [4,2,5,3], k = 3

› Output: 3

💡 Note: Subarray [4,2,5]: make all equal to 4 → |4-4|+|2-4|+|5-4| = 0+2+1 = 3 operations. Subarray [2,5,3]: make all equal to 3 → |2-3|+|5-3|+|3-3| = 1+2+0 = 3 operations. Minimum is 3.

Example 2 — All Same Elements

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

› Output: 0

💡 Note: Any subarray of size 2 already has all elements equal (both are 1), so 0 operations needed.

Example 3 — Minimum Size

$ Input: nums = [10,12], k = 2

› Output: 1

💡 Note: Only one subarray [10,12]. To make equal: target 11 needs |10-11|+|12-11| = 1+1 = 2 ops, target 10 needs |10-10|+|12-10| = 0+2 = 2 ops. Optimal target is median which gives 1 operation.

Constraints

2 ≤ nums.length ≤ 10⁵
1 ≤ k ≤ nums.length
1 ≤ nums[i] ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input

Array nums=[4,2,5,3] and k=3 (need subarray of size 3)

Process

Check each subarray of size k, find optimal target (median)

Output

Return minimum operations needed across all subarrays

Key Takeaway

🎯 Key Insight: The median of any subarray minimizes the total operations needed to make all elements equal

Asked in

G Google 25 M Microsoft 20 a Amazon 15

The key insight is that the median of any set minimizes the sum of absolute deviations. For each subarray of size k, we find the median and calculate operations needed. Best approach uses sliding window with median optimization achieving O(n·k log k) time, O(k) space.

Common Approaches

Approach	Time	Space	Notes
✓ Optimized Sliding Window with Heaps	O(n log k)	O(k)	Use two heaps to efficiently track median in sliding window
Brute Force - Try All Targets	O(n³)	O(1)	For each subarray, try every possible target value
Sliding Window with Median	O(n·k log k)	O(k)	Use sliding window and find median as optimal target for each subarray

Optimized Sliding Window with Heaps — Algorithm Steps

Use two heaps to maintain median efficiently
Slide window and update heaps incrementally
Get median from heap tops in O(1)
Calculate operations for current median

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize Heaps

Max heap for lower half, min heap for upper half

Slide Window

Add new element, remove old element, rebalance

Get Median

Median from heap tops in O(1) time

Code -

solution.c — C

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

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

int solution(int* nums, int numsSize, int k) {
    int minOps = INT_MAX;
    int* temp = (int*)malloc(k * sizeof(int));
    
    for (int i = 0; i <= numsSize - k; i++) {
        for (int j = 0; j < k; j++) {
            temp[j] = nums[i + j];
        }
        qsort(temp, k, sizeof(int), compare);
        int median = temp[k / 2];
        
        int ops = 0;
        for (int j = i; j < i + k; j++) {
            ops += abs(nums[j] - median);
        }
        if (ops < minOps) {
            minOps = ops;
        }
    }
    
    free(temp);
    return minOps;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(n log k)

O(n) windows × O(log k) heap operations per window

⚡ Linearithmic

Space Complexity

O(k)

Two heaps storing up to k elements total

✓ Linear Space

28.4K Views

Medium Frequency

~25 min Avg. Time

856 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

Optimized Sliding Window with Heaps — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler