Minimum Operations to Make Median of Array Equal to K

Problem Description

So, you think you can just throw a bunch of numbers into an array and expect them to behave? Well, think again! The problem at hand is to make the median of an array equal to a specific number k with the least amount of effort (or operations, in this case). Imagine you’re at a party, and everyone is dancing to different tunes. You want to get them all to groove to your favorite song, but you can only change a few of their dance moves. That’s basically what we’re doing here!

In simpler terms, given an array of integers, you need to figure out how many operations it takes to make the median equal to k. An operation consists of either increasing or decreasing the elements of the array.

Code Solution


class Solution:
    def minOperationsToMakeMedianK(self, nums: list[int], k: int) -> int:
        n = len(nums)
        ans = 0

        nums.sort()

        for i in range(n // 2 + 1):
            ans += max(0, nums[i] - k)

        for i in range(n // 2, n):
            ans += max(0, k - nums[i])

        return ans

Approach Explanation

The approach is as straightforward as it gets. First, we sort the array because, let’s face it, no one likes chaos. Then, we calculate how many operations are needed to adjust the first half of the sorted array to be less than or equal to k and the second half to be greater than or equal to k. The total number of operations gives us the answer.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n log n) due to the sorting step.
Space Complexity	O(1) since we are using a constant amount of extra space.

Real-World Example

Imagine you’re a teacher trying to adjust the grades of your students so that the median grade is a solid B (let’s say that’s a 75). You can either bump up the grades of the underperformers or bring down the overachievers. The goal is to find the least number of grade changes needed to achieve that median.