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 of the array when it is sorted in non-decreasing order. If there are two choices for a median, the larger of the two values is taken.

Examples

Example 1

1
2
3
4
5
6
7
8
9


Input: nums = [2,5,6,8,5], k = 4

Output: 2

Explanation:

We can subtract one from `nums[1]` and `nums[4]` to obtain `[2, 4, 6, 8, 4]`.
The median of the resulting array is equal to `k`.

Example 2

1
2
3
4
5
6
7
8
9


Input: nums = [2,5,6,8,5], k = 7

Output: 3

Explanation:

We can add one to `nums[1]` twice and add one to `nums[2]` once to obtain `[2,
7, 7, 8, 5]`.

Example 3

1
2
3
4
5
6
7
8


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

Output: 0

Explanation:

The median of the array is already equal to `k`.

Constraints

  • 1 <= nums.length <= 2 * 10^5
  • 1 <= nums[i] <= 10^9
  • 1 <= k <= 10^9

Solution

Method 1 – Sorting & Greedy

Intuition

To make the median equal to k, we only need to change the value at the median index to k. The minimum number of operations is the sum of absolute differences between k and the current median value. For an odd-length array, the median is the middle element after sorting; for even-length, it’s the larger of the two middle elements.

Approach

  1. Sort the array.
  2. Find the median index: (n-1)//2 if n is odd, n//2 if n is even (since the larger is taken).
  3. The minimum operations is abs(nums[median_index] - k).
  4. Edge case: If the median is already k, answer is 0.

Code

1
2
3
4
5
6
7
8
9

class Solution {
public:
    int minOperations(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int m = n / 2;
        return abs(nums[m] - k);
    }
};
1
2
3
4
5
6
7
8

func minOperations(nums []int, k int) int {
    sort.Ints(nums)
    m := len(nums) / 2
    if nums[m] > k {
        return nums[m] - k
    }
    return k - nums[m]
}
1
2
3
4
5
6
7

class Solution {
    public int minOperations(int[] nums, int k) {
        Arrays.sort(nums);
        int m = nums.length / 2;
        return Math.abs(nums[m] - k);
    }
}
1
2
3
4
5
6
7

class Solution {
    fun minOperations(nums: IntArray, k: Int): Int {
        nums.sort()
        val m = nums.size / 2
        return kotlin.math.abs(nums[m] - k)
    }
}
1
2
3
4
5

class Solution:
    def minOperations(self, nums: list[int], k: int) -> int:
        nums.sort()
        m = len(nums) // 2
        return abs(nums[m] - k)
1
2
3
4
5
6
7

impl Solution {
    pub fn min_operations(mut nums: Vec<i32>, k: i32) -> i32 {
        nums.sort();
        let m = nums.len() / 2;
        (nums[m] - k).abs()
    }
}
1
2
3
4
5
6
7

class Solution {
    minOperations(nums: number[], k: number): number {
        nums.sort((a, b) => a - b);
        const m = Math.floor(nums.length / 2);
        return Math.abs(nums[m] - k);
    }
}

Complexity

  • ⏰ Time complexity: O(n log n) — Sorting the array dominates the runtime.
  • 🧺 Space complexity: O(1) — Sorting can be done in-place, no extra space proportional to input size.