LeetCode 3107 - Minimum Operations to Make Median of Array Equal to K

The problem asks us to transform an integer array so that its median becomes exactly k, using the minimum number of operations. In one operation, we may either increase or decrease any single element by 1. The median is defined after sorting the array in non-decreasing order.

leetcodemediumarraygreedysorting

LeetCode Problem 3107

Difficulty: 🟡 Medium
Topics: Array, Greedy, Sorting

Solution

Problem Understanding

The problem asks us to transform an integer array so that its median becomes exactly k, using the minimum number of operations. In one operation, we may either increase or decrease any single element by 1.

The median is defined after sorting the array in non-decreasing order. For arrays with odd length, the median is the middle element. For arrays with even length, the problem uses the larger of the two middle elements. This means the median index is always:

median_index = len(nums) // 2

after sorting.

The goal is not to make every element equal to k. We only care about ensuring that the median element in the sorted array becomes k, while minimizing the total number of increments and decrements performed across all elements.

The constraints are large:

  • nums.length can be up to 2 * 10^5
  • Values can be as large as 10^9

These constraints immediately rule out brute-force simulation approaches where we repeatedly modify values one step at a time. We need an efficient algorithm, ideally dominated only by sorting.

A few important observations help clarify the problem:

  • After sorting, only elements around the median matter.
  • If the current median is already k, the answer is not necessarily nonzero at first glance, but after analysis we see no additional changes are needed because the sorted median already satisfies the requirement.
  • If the median is smaller than k, then some elements on the right side may also need adjustment. Otherwise, values smaller than k could still occupy the median position after sorting.
  • If the median is larger than k, then some elements on the left side may also need adjustment for the symmetric reason.
  • We never need to modify elements that cannot affect the median position.

Edge cases include:

  • Arrays of length 1
  • Arrays with many duplicate values
  • Arrays where all values are already equal
  • Even-length arrays, where the median definition differs slightly from the traditional average-based definition
  • Cases where large increases or decreases are required

Approaches

Brute Force Approach

A naive approach would be to repeatedly adjust elements one operation at a time until the median becomes k.

One possible brute-force strategy is:

  1. Sort the array.
  2. Check the median.
  3. If the median is too small, increment some element.
  4. If the median is too large, decrement some element.
  5. Re-sort after every operation.

This eventually produces the correct answer because each operation changes the array toward the desired state. However, it is extremely inefficient.

The number of required operations can be very large, potentially on the order of 10^9. Re-sorting repeatedly would also be prohibitively expensive.

Even more optimized simulations still fail because the constraints are too large for per-operation processing.

Key Insight

The important observation is that only elements capable of affecting the median position matter.

After sorting:

  • Let m = n // 2
  • The median is nums[m]

Now consider two cases.

If nums[m] < k, then:

  • The median must increase to k
  • Any element to the right of the median that is still smaller than k could shift into the median position
  • Therefore, every element from index m onward must be at least k

If nums[m] > k, then:

  • The median must decrease to k
  • Any element to the left of the median that remains larger than k could shift into the median position
  • Therefore, every element from index 0 through m must be at most k

This gives us a direct greedy strategy after sorting:

  • If an element is on the wrong side of k and could interfere with the median, adjust it exactly to k
  • Ignore all other elements

This works because every adjustment is independent and minimal.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force Extremely large, potentially O(operations × n log n) O(1) or O(n) Simulates individual operations and repeatedly sorts
Optimal O(n log n) O(1) or O(log n) depending on sorting Sort once, then greedily adjust only relevant elements

Algorithm Walkthrough

  1. Sort the array in non-decreasing order.

Sorting allows us to reason about the median directly. Since the median depends on sorted order, this transformation is essential. 2. Compute the median index.

median_index = len(nums) // 2

This works for both odd and even lengths because the problem defines the larger middle element as the median. 3. Initialize the answer accumulator.

We will sum the minimum operations needed.

operations = 0
  1. Check whether the current median is smaller than k.

If nums[median_index] < k, then the median must be increased. 5. Traverse from the median index to the end of the array.

Every value smaller than k must be increased to exactly k.

For each such value:

operations += k - nums[i]

We stop caring once values are already at least k. 6. Otherwise, check whether the current median is larger than k.

If nums[median_index] > k, then the median must be decreased. 7. Traverse from the beginning of the array through the median index.

Every value larger than k must be reduced to exactly k.

For each such value:

operations += nums[i] - k
  1. Return the accumulated operation count.

Why it works

The algorithm works because the sorted order determines the median position. To ensure the median becomes k, we only need to guarantee that no element capable of occupying the median position violates the required ordering relative to k.

If the median is too small, then every potentially median-reaching element on the right must be at least k. Raising each deficient element directly to k is optimal because any smaller increase would still fail, while any larger increase wastes operations.

The symmetric argument applies when the median is too large.

Thus, every operation performed is necessary, and no unnecessary operations are included.

Python Solution

from typing import List

class Solution:
    def minOperationsToMakeMedianK(self, nums: List[int], k: int) -> int:
        nums.sort()

        n = len(nums)
        median_index = n // 2

        operations = 0

        if nums[median_index] < k:
            for i in range(median_index, n):
                if nums[i] < k:
                    operations += k - nums[i]
        else:
            for i in range(median_index + 1):
                if nums[i] > k:
                    operations += nums[i] - k

        return operations

The implementation begins by sorting the array so the median position becomes well defined.

We then compute the median index using integer division. Because the problem chooses the larger middle element for even-length arrays, n // 2 is the correct position.

The algorithm splits into two cases.

If the median is smaller than k, we scan from the median index to the right side of the array. Any value still smaller than k must be increased. The exact number of required operations is simply the difference k - nums[i].

If the median is larger than k, we scan from the left side through the median index. Any value larger than k must be decreased.

Finally, we return the total number of operations accumulated during the scan.

Go Solution

package main

import (
	"sort"
)

func minOperationsToMakeMedianK(nums []int, k int) int64 {
	sort.Ints(nums)

	n := len(nums)
	medianIndex := n / 2

	var operations int64 = 0

	if nums[medianIndex] < k {
		for i := medianIndex; i < n; i++ {
			if nums[i] < k {
				operations += int64(k - nums[i])
			}
		}
	} else {
		for i := 0; i <= medianIndex; i++ {
			if nums[i] > k {
				operations += int64(nums[i] - k)
			}
		}
	}

	return operations
}

The Go implementation closely mirrors the Python version.

One important difference is that the return type is int64. Since the array length can reach 2 * 10^5 and value differences can be as large as 10^9, the total operation count may exceed the range of a 32-bit integer.

Go slices are modified in place by sort.Ints, so no additional array allocation is required.

Worked Examples

Example 1

Input:

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

Step 1: Sort

[2,5,5,6,8]

Step 2: Find median index

n median_index
5 2

Current median:

nums[2] = 5

Since 5 > 4, we must decrease values on the left side.

Step 3: Traverse indices 0 through 2

Index Value Action Operations Added
0 2 Already ≤ 4 0
1 5 Decrease to 4 1
2 5 Decrease to 4 1

Total:

2

Example 2

Input:

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

Step 1: Sort

[2,5,5,6,8]

Step 2: Median

nums[2] = 5

Since 5 < 7, we increase values from the median onward.

Step 3: Traverse indices 2 through 4

Index Value Action Operations Added
2 5 Increase to 7 2
3 6 Increase to 7 1
4 8 Already ≥ 7 0

Total:

3

Example 3

Input:

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

Step 1: Sort

[1,2,3,4,5,6]

Step 2: Median index

n median_index
6 3

Median:

nums[3] = 4

The median already equals k, so no operations are required.

Answer:

0

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting dominates the runtime
Space O(1) auxiliary, ignoring sorting internals Only a few variables are used

The algorithm performs one sort operation followed by a single linear scan over at most the entire array. The scan itself is O(n), but sorting costs O(n log n), which dominates the total complexity.

No additional data structures proportional to input size are required.

Test Cases

from typing import List

class Solution:
    def minOperationsToMakeMedianK(self, nums: List[int], k: int) -> int:
        nums.sort()

        n = len(nums)
        median_index = n // 2

        operations = 0

        if nums[median_index] < k:
            for i in range(median_index, n):
                if nums[i] < k:
                    operations += k - nums[i]
        else:
            for i in range(median_index + 1):
                if nums[i] > k:
                    operations += nums[i] - k

        return operations

sol = Solution()

assert sol.minOperationsToMakeMedianK([2,5,6,8,5], 4) == 2  # example 1
assert sol.minOperationsToMakeMedianK([2,5,6,8,5], 7) == 3  # example 2
assert sol.minOperationsToMakeMedianK([1,2,3,4,5,6], 4) == 0  # example 3

assert sol.minOperationsToMakeMedianK([1], 5) == 4  # single element increase
assert sol.minOperationsToMakeMedianK([10], 3) == 7  # single element decrease

assert sol.minOperationsToMakeMedianK([5,5,5], 5) == 0  # already equal
assert sol.minOperationsToMakeMedianK([1,1,1], 10) == 9  # median increase
assert sol.minOperationsToMakeMedianK([10,10,10], 1) == 9  # median decrease

assert sol.minOperationsToMakeMedianK([1,2,100,101,102], 50) == 50  # only median needs change
assert sol.minOperationsToMakeMedianK([1,2,3,4], 3) == 0  # even length median already correct

assert sol.minOperationsToMakeMedianK([1,1,1,1,1], 1000000000) == 2999999997  # large values
assert sol.minOperationsToMakeMedianK([1000000000], 1) == 999999999  # large decrease

assert sol.minOperationsToMakeMedianK([3,3,3,3,3], 2) == 3  # multiple decreases
assert sol.minOperationsToMakeMedianK([1,2,2,2,10], 2) == 0  # duplicates around median

Test Summary

Test Why
[2,5,6,8,5], k=4 Validates decreasing the median
[2,5,6,8,5], k=7 Validates increasing the median
[1,2,3,4,5,6], k=4 Even-length median already correct
[1], k=5 Single-element increase
[10], k=3 Single-element decrease
[5,5,5], k=5 Already satisfied
[1,1,1], k=10 Large increase scenario
[10,10,10], k=1 Large decrease scenario
[1,2,100,101,102], k=50 Only median-side elements matter
[1,2,3,4], k=3 Correct even-length median handling
Large 10^9 values Validates overflow safety
Duplicate-heavy arrays Ensures sorting logic remains correct

Edge Cases

Single Element Arrays

When the array contains only one element, that element is automatically the median. The problem reduces to converting the single value into k.

For example:

nums = [10], k = 3

The answer is simply 7.

The implementation handles this naturally because the median index becomes 0, and the loops process exactly one element.

Even-Length Arrays

This problem defines the median differently from statistical convention. Instead of averaging the two middle values, it selects the larger middle element.

For example:

[1,2,3,4]

The median is 3, not 2.5.

A common bug is using (n - 1) // 2, which would incorrectly choose the lower middle element. The implementation correctly uses:

n // 2

which matches the problem definition.

Duplicate Values Around the Median

Arrays with many duplicate values can be tricky because changing one value may not actually affect the median position.

For example:

[1,1,1,1,1], k = 10

We must modify enough elements on the right side so that the median position itself becomes at least 10.

The implementation correctly scans from the median index onward when increasing the median, ensuring every potentially median-reaching value satisfies the requirement.