Minimum Operations to Make Median of Array Equal to K

Minimum Operations to Make Median of Array Equal to K - Problem

You are given an integer array nums and a non-negative integer k. In one operation, you can increase or decrease any element by 1.

Return the minimum number of operations needed to make the median of nums equal to k.

The median of an array is defined as the middle element when the array is sorted in non-decreasing order. If there are two choices for a median, the larger of the two values is taken.

Input & Output

Example 1 — Basic Case

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

› Output: 2

💡 Note: Sort array to [1,2,3,4]. Median is at index 2 with value 3. Need 3-2=1 operation to make median 2. Element at index 3 is 4 > 2, need 4-2=2 more operations. Total: 1+2=3 operations. Wait, let me recalculate: sorted [1,2,3,4], median index n//2 = 2, so median is 3. Need |3-2|=1 operation. No violations. Actually total is 1.

Example 2 — Already Optimal

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

› Output: 0

💡 Note: Sort array to [1,2,3]. Median is 2 which equals k. All elements satisfy median property: 1 ≤ 2 and 3 ≥ 2. No operations needed.

Example 3 — Large Adjustment

$ Input: nums = [1,5,6], k = 3

› Output: 4

💡 Note: Sort array to [1,5,6]. Median is 5. Need |5-3|=2 operations to make median 3. Element 6 < 3 is false (6 ≥ 3), so no additional operations. Total: 2 operations.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

Array [2,1,3,4] and target k=2

Sort & Identify

Sort to [1,2,3,4], median is 3 at index 2

Greedy Adjust

Change median 3→2 (1 operation), no other violations

Key Takeaway

🎯 Key Insight: Sort first to identify median, then greedily adjust median and ensure surrounding elements maintain sorted order properties

Asked in

G Google 15 f Meta 12 a Amazon 10 M Microsoft 8

The key insight is to sort the array first to identify the median position, then use a greedy strategy: adjust the median to target k, ensure all elements before median are ≤ k, and all elements after median are ≥ k. Best approach is Greedy with Time: O(n log n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Sort and Greedy Adjustment	O(n log n)	O(1)	Sort array first, then greedily adjust median and surrounding elements
Brute Force - Try All Operations	O(2^(n×m))	O(n)	Try all possible sequences of increment/decrement operations until median equals k
Optimal Greedy Strategy	O(n log n)	O(1)	Sort array and use greedy approach to minimize operations by adjusting median and necessary surrounding elements

Sort and Greedy Adjustment — Algorithm Steps

Sort the array to find current median position
Identify which elements need adjustment
Calculate minimum operations greedily

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort Array

Sort to find median position

Identify Median

Find median index and current value

Greedy Adjust

Adjust median and surrounding elements optimally

Code -

solution.c — C

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

void sortArray(int* arr, int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

int solution(int* nums, int numsSize, int k) {
    sortArray(nums, numsSize);
    int operations = 0;
    
    int medianIdx = numsSize / 2;
    
    if (nums[medianIdx] == k) {
        for (int i = 0; i < medianIdx; i++) {
            if (nums[i] > k) {
                operations += nums[i] - k;
            }
        }
        
        for (int i = medianIdx + 1; i < numsSize; i++) {
            if (nums[i] < k) {
                operations += k - nums[i];
            }
        }
    } else if (nums[medianIdx] < k) {
        operations += k - nums[medianIdx];
        
        for (int i = 0; i < medianIdx; i++) {
            if (nums[i] > k) {
                operations += nums[i] - k;
            }
        }
        
        for (int i = medianIdx + 1; i < numsSize; i++) {
            if (nums[i] < k) {
                operations += k - nums[i];
            }
        }
    } else {
        operations += nums[medianIdx] - k;
        
        for (int i = 0; i < medianIdx; i++) {
            if (nums[i] > k) {
                operations += nums[i] - k;
            }
        }
        
        for (int i = medianIdx + 1; i < numsSize; i++) {
            if (nums[i] < k) {
                operations += k - nums[i];
            }
        }
    }
    
    return operations;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting dominates the time complexity

⚡ Linearithmic

Space Complexity

O(1)

Only using constant extra space for calculations

✓ Linear Space

23.4K Views

Medium Frequency

~25 min Avg. Time

890 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 Greedy Adjustment — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler