#3107

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Minimum Operations to Make Median of Array Equal to K

The problem involves minimizing operations to make the median of an array equal to a given value k using a greedy approach.

array greedy sorting

Problem Statement

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 is the middle element in the sorted array, and if there are two middle values, the larger one is chosen.

Examples

Example 1

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

Output: 2

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

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

Output: 3

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

Example 3

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

Output: 0

The median of the array is already equal to k .

Constraints

1 <= nums.length <= 2 * 105
1 <= nums[i] <= 109
1 <= k <= 109

Solution Approach

Sort the Array

First, sort the array to ensure that we can easily access the median position. This allows us to focus only on the elements that directly affect the median.

Greedy Choice at Median

Next, calculate the minimum number of operations required by adjusting elements that influence the median. Depending on whether we need to increase or decrease the value at the median, we apply operations accordingly.

Validate the Invariant

Ensure that after adjusting the median element, the operations do not affect the sorted order of the array, maintaining the invariant that the median is always the middle element of the array.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity primarily depends on sorting the array, which is O(n log n). After sorting, the number of operations is linear in nature, O(n), making the overall complexity O(n log n). The space complexity is O(1) if sorting is done in-place.

What Interviewers Usually Probe

Candidate correctly identifies the importance of sorting the array before operating on it.
Candidate may struggle with the details of greedy selection for the median.
Check if the candidate is comfortable with modifying array elements while maintaining order.

Common Pitfalls or Variants

Common pitfalls

Not sorting the array first, leading to incorrect identification of the median.
Applying operations to elements not affecting the median.
Failing to account for the two possible middle elements in arrays with an even length.

Follow-up variants

Array with an even length where the median is ambiguous.
Test cases with very large values for k and nums[i].
Arrays that are already sorted, testing the candidate's optimization skills.

FAQ

How can I minimize the operations to make the median equal to k?

Minimize operations by sorting the array and applying a greedy approach to adjust only the elements that affect the median value.

What is the key pattern in the 'Minimum Operations to Make Median of Array Equal to K' problem?

The problem follows a greedy approach where you focus on the median and adjust elements accordingly while maintaining a sorted order.

Does sorting the array always guarantee a solution?

Yes, sorting the array ensures that you can access the median directly and apply operations to only the relevant elements.

What if the array has an even length?

If the array has an even length, the larger of the two middle elements is chosen as the median, which must also be adjusted to k.

What is the time complexity of the solution?

The time complexity is O(n log n) due to the sorting step, followed by a linear scan to apply operations to the median.

terminal

Solution

Solution 1: Greedy + Sorting

First, we sort the array $nums$ and find the position $m$ of the median. The initial number of operations we need is $|nums[m] - k|$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def minOperationsToMakeMedianK(self, nums: List[int], k: int) -> int:
        nums.sort()
        n = len(nums)
        m = n >> 1
        ans = abs(nums[m] - k)
        if nums[m] > k:
            for i in range(m - 1, -1, -1):
                if nums[i] <= k:
                    break
                ans += nums[i] - k
        else:
            for i in range(m + 1, n):
                if nums[i] >= k:
                    break
                ans += k - nums[i]
        return ans

Continue Practicing

#3111 minimum rectangles to cover points #3075 maximize happiness of selected children #3074 apple redistribution into boxes