Minimum Operations to Make Median of Array Equal to K

Medium
860.

Minimum Operations to Make Median of Array Equal to K

Minimum Operations to Make Median of Array Equal to K is a medium coding problem on arrays, sorting and greedy, asked in Amazon, Google and CRED interviews.

One operation increases or decreases any element by 1. The median is the middle element after sorting; with an even length it is the larger of the two middles.

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

Example 1

Input
nums = [2,5,6,8,5], k = 4
Output
2
Explanation
Sorted it is [2,5,5,6,8] with median 5; lowering both 5s to 4 costs 2.

Example 2

Input
nums = [2,5,6,8,5], k = 7
Output
3
Explanation
Raise 5 to 7 and 6 to 7.

Example 3

Input
nums = [1,2,3,4,5,6], k = 4
Output
0
Explanation
The median is already 4.

Constraints

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 1000000
  • 1 <= k <= 1000000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var minOperationsToMakeMedianK = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Operations to Make Median of Array Equal to K Solution

Minimum Operations to Make Median of Array Equal to K solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Minimum Operations to Make Median of Array Equal to K is a medium coding problem on arrays, sorting and greedy, asked in Amazon, Google and CRED interviews.

  • Difficulty: Medium
  • Topics: Arrays, Sorting, Greedy
  • Asked at: Amazon, Google, CRED
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

One operation increases or decreases any element by 1. The median is the middle element after sorting; with an even length it is the larger of the two middles.

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

Example 1

Input: nums = [2,5,6,8,5], k = 4
Output: 2
Explanation: Sorted it is [2,5,5,6,8] with median 5; lowering both 5s to 4 costs 2.

Example 2

Input: nums = [2,5,6,8,5], k = 7
Output: 3
Explanation: Raise 5 to 7 and 6 to 7.

Example 3

Input: nums = [1,2,3,4,5,6], k = 4
Output: 0
Explanation: The median is already 4.

Constraints

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 1000000
  • 1 <= k <= 1000000

Hints for Minimum Operations to Make Median of Array Equal to K

  1. Hint 1

    Sort first; the median sits at index n / 2 (integer division).

  2. Hint 2

    If the median is above k, every element from there leftwards that exceeds k must come down to k.

  3. Hint 3

    If it is below k, every element from there rightwards that is below k must come up.

How to solve Minimum Operations to Make Median of Array Equal to K

Only the elements around the median position need to move, and only far enough to put k at that position. Sorting makes the affected run contiguous, and each element's cost is its distance to k.

Approach

  1. Sort a copy and let m = n / 2.
  2. If a[m] > k, walk left from m while the value exceeds k, adding a[i] - k.
  3. If a[m] < k, walk right from m while the value is below k, adding k - a[i].

Why it works

To place k at index m of the sorted array, at least m + 1 elements must be at most k and at least n - m must be at least k. When the median is too high, the cheapest way to satisfy the first requirement is to pull down exactly the elements at indices m, m-1, … that exceed k — they are the closest to k among those that must move. The other direction is symmetric, and elements already on the right side of k cost nothing.

Complexity

  • Time — O(n log n)
  • Space — O(n)

Pitfalls

  • With an even length the median is the upper middle, so m = n / 2, not n / 2 - 1.
  • Elements already past k in the right direction must not be moved — the walk stops at the first one.
  • The total reaches about 10^9 at the stated limits.

Reference solution

Python

from typing import List

def minOperationsToMakeMedianK(nums: List[int], k: int) -> int:
    a = sorted(nums)
    n = len(a)
    m = n // 2
    ops = 0
    if a[m] > k:
        i = m
        while i >= 0 and a[i] > k:
            ops += a[i] - k
            i -= 1
    else:
        i = m
        while i < n and a[i] < k:
            ops += k - a[i]
            i += 1
    return ops

Java

public static int minOperationsToMakeMedianK(int[] nums, int k) {
    int[] a = nums.clone();
    Arrays.sort(a);
    int n = a.length, m = n / 2;
    long ops = 0;
    if (a[m] > k) {
        for (int i = m; i >= 0 && a[i] > k; i--) ops += a[i] - k;
    } else {
        for (int i = m; i < n && a[i] < k; i++) ops += k - a[i];
    }
    return (int) ops;
}

C++

int minOperationsToMakeMedianK(vector<int>& nums, int k) {
    vector<int> a = nums;
    sort(a.begin(), a.end());
    int n = (int) a.size(), m = n / 2;
    long long ops = 0;
    if (a[m] > k) {
        for (int i = m; i >= 0 && a[i] > k; i--) ops += a[i] - k;
    } else {
        for (int i = m; i < n && a[i] < k; i++) ops += k - a[i];
    }
    return (int) ops;
}

JavaScript

var minOperationsToMakeMedianK = function(nums, k) {
    var a = nums.slice().sort(function(x, y) { return x - y; });
    var n = a.length;
    var m = Math.floor(n / 2);
    var ops = 0, i;
    if (a[m] > k) {
        for (i = m; i >= 0 && a[i] > k; i--) ops += a[i] - k;
    } else {
        for (i = m; i < n && a[i] < k; i++) ops += k - a[i];
    }
    return ops;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms