Problem Description

You have an integer array nums and a non-negative integer k. Your goal is to make the median of the array equal to k by performing operations. In each operation, you can increase or decrease any element by 1.

The median is defined as the middle element when the array is sorted in non-decreasing order. For arrays with an even number of elements, the median is the larger of the two middle values.

You need to find the minimum number of operations required to achieve a median of k.

For example, if you have nums = [1, 2, 3, 4, 5] and k = 3, the median is already 3, so you need 0 operations. But if k = 6, you would need to increase some elements to make the median equal to 6.

The strategy involves sorting the array first to identify the median position. Then:

• If the current median is greater than k, you need to decrease it to k and also ensure elements to its left that are greater than k are decreased to k (to maintain the median property)
• If the current median is less than k, you need to increase it to k and also ensure elements to its right that are less than k are increased to k (to maintain the median property)

The solution counts the total number of unit changes needed across all affected elements to achieve the target median of k.

Intuition

The key insight is understanding what happens to the median when we modify array elements. After sorting the array, the median is at position m = n // 2. For the median to remain at this position and have value k, we need to maintain a specific order relationship.

Think about it this way: if we want the median to be k, then:

• All elements to the left of the median position should be ≤ k
• All elements to the right of the median position should be ≥ k

Why? Because if any element on the left is greater than k, when we sort the array, that larger value might shift to the median position or push our desired k value away from the median position. Similarly, if any element on the right is less than k, it could interfere with k being the median.

This leads to our greedy approach:

1. First, change the current median to k - this costs |nums[m] - k| operations
2. If the original median was greater than k, we need to check leftward. Any element to the left that's still greater than k must be reduced to exactly k to prevent it from becoming the new median
3. If the original median was less than or equal to k, we need to check rightward. Any element to the right that's still less than k must be increased to exactly k

The brilliance of this approach is that we don't need to over-adjust any element. Making elements on the left exactly k (not less) and elements on the right exactly k (not more) is optimal because it uses the minimum operations while guaranteeing k stays as the median.

Learn more about Greedy and Sorting patterns.

Solution Approach

The implementation follows a greedy approach with sorting:

1. Sort the array: First, we sort nums to easily identify the median position. After sorting, the median is at index m = n >> 1 (equivalent to n // 2).

2. Calculate initial operations: We start by calculating the operations needed to change the current median to k: ans = abs(nums[m] - k).

3. Handle two cases based on median value:

   Case 1: When nums[m] > k

   • We need to ensure all elements to the left of position m are at most k
   • Iterate from position m - 1 down to 0:
     • If nums[i] <= k, we can stop (all remaining elements to the left are already ≤ k due to sorting)
     • Otherwise, add nums[i] - k to our answer (operations needed to reduce nums[i] to k)

   Case 2: When nums[m] <= k

   • We need to ensure all elements to the right of position m are at least k
   • Iterate from position m + 1 to n - 1:
     • If nums[i] >= k, we can stop (all remaining elements to the right are already ≥ k due to sorting)
     • Otherwise, add k - nums[i] to our answer (operations needed to increase nums[i] to k)

The algorithm's efficiency comes from:

• Only modifying elements that violate the median constraint
• Using early termination when we encounter elements that already satisfy the condition
• Leveraging the sorted order to know that once we find a valid element, all elements beyond it in that direction are also valid

Time complexity: O(n log n) due to sorting, where n is the length of the array. Space complexity: O(1) if we don't count the sorting space, otherwise O(log n) for the sorting algorithm's recursion stack.

Example Walkthrough

Let's walk through an example with nums = [2, 5, 6, 8, 9] and k = 4.

Step 1: Sort the array The array is already sorted: [2, 5, 6, 8, 9]

Step 2: Find the median position With n = 5, the median position is m = 5 // 2 = 2 Current median value: nums[2] = 6

Step 3: Calculate initial operations We need to change the median from 6 to 4:

• Operations needed: |6 - 4| = 2
• Running total: ans = 2

Step 4: Determine which direction to check Since nums[m] = 6 > k = 4, we need to check elements to the left.

Step 5: Check and adjust elements to the left We want all elements left of position 2 to be ≤ 4:

• Position 1: nums[1] = 5
  • Since 5 > 4, we need to decrease it to 4
  • Operations: 5 - 4 = 1
  • Running total: ans = 2 + 1 = 3
• Position 0: nums[0] = 2
  • Since 2 ≤ 4, we stop here (no adjustment needed)

Final Result After 3 operations, our array becomes [2, 4, 4, 8, 9]:

• Changed position 2 from 6 to 4 (2 operations)
• Changed position 1 from 5 to 4 (1 operation)

When sorted, this array has median = 4, which equals our target k.

The key insight: We only needed to adjust elements that violated the median constraint (elements on the left that were greater than k). Elements on the right (8 and 9) didn't need adjustment because they're already ≥ k, which is what we want for elements right of the median.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n)

The time complexity is dominated by the sorting operation nums.sort(), which takes O(n × log n) time where n is the length of the array. After sorting, the algorithm performs a single pass through at most half of the array (either from index m-1 to 0 or from index m+1 to n-1), which takes O(n) time in the worst case. Since O(n × log n) + O(n) = O(n × log n), the overall time complexity is O(n × log n).

Space Complexity: O(log n)

The space complexity comes from the sorting algorithm. Python's sort() method uses Timsort, which requires O(log n) space for its recursive call stack in the worst case. The algorithm itself only uses a constant amount of extra space for variables like n, m, and ans, which is O(1). Therefore, the total space complexity is O(log n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Misunderstanding the Median Definition for Even-Length Arrays

A critical pitfall is incorrectly handling the median for even-length arrays. The problem states that for even-length arrays, the median is the larger of the two middle values (upper median), not the average or the smaller value.

Incorrect assumption:

# Wrong: Using lower median for even-length arrays
median_index = (n - 1) // 2  # This gives the lower middle element

# Wrong: Using average of two middle elements
median_index = n // 2
median_value = (nums[median_index - 1] + nums[median_index]) / 2

Correct approach:

# Correct: For both odd and even length arrays
median_index = n // 2
# For odd length: this gives the middle element
# For even length: this gives the upper middle element (larger of the two)

2. Not Maintaining the Sorted Order Property

Another pitfall is only changing the median element without considering that after operations, the array must still have k as its median when sorted. Simply changing the median position element to k doesn't guarantee it remains the median.

Incorrect approach:

def minOperationsToMakeMedianK(self, nums: List[int], k: int) -> int:
    nums.sort()
    median_index = len(nums) // 2
    # Wrong: Only changing the median element
    return abs(nums[median_index] - k)

Why this fails: If nums = [1, 2, 5, 6, 7] and k = 3, just changing 5 to 3 gives [1, 2, 3, 6, 7], which is correct. But if nums = [1, 4, 5, 6, 7] and k = 2, changing 5 to 2 gives [1, 4, 2, 6, 7]. When re-sorted, this becomes [1, 2, 4, 6, 7], and the median is 4, not 2!

Correct approach: Ensure all elements to the left of the median position are ≤ k, and all elements to the right are ≥ k:

# After setting median to k, fix neighboring elements
if nums[median_index] > k:
    # Fix left side - make all elements > k equal to k
    for i in range(median_index - 1, -1, -1):
        if nums[i] <= k:
            break
        total_operations += nums[i] - k
else:
    # Fix right side - make all elements < k equal to k  
    for i in range(median_index + 1, n):
        if nums[i] >= k:
            break
        total_operations += k - nums[i]

3. Modifying the Original Array During Iteration

While the current solution doesn't actually modify the array (it only calculates operations), a common mistake when implementing similar problems is to modify array elements while iterating, which can lead to incorrect calculations.

Incorrect pattern:

# Wrong: Modifying array while calculating
for i in range(median_index - 1, -1, -1):
    if nums[i] > k:
        total_operations += nums[i] - k
        nums[i] = k  # Modifying the array - not needed!

Correct approach: Just calculate the operations without modifying:

# Correct: Only calculate operations
for i in range(median_index - 1, -1, -1):
    if nums[i] <= k:
        break
    total_operations += nums[i] - k
    # No modification needed - we're just counting operations