Get started

Minimum Operations to Make Median of Array Equal to K — Medium Problem & Solution

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…

  • Difficulty: Medium
  • Topics: Arrays, Greedy, Sorting
  • 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

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

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue