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.
Example 1:
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:
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:
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 * 1051 <= nums[i] <= 1091 <= k <= 109Problem Overview: You are given an integer array and a target value k. In one operation you can increment or decrement any element by 1. The goal is to make the median of the array exactly k using the minimum number of operations.
Approach 1: Sorting and Direct Manipulation (Time: O(n log n), Space: O(1))
Sort the array so the median index becomes deterministic at mid = n // 2. If nums[mid] == k, no work is needed. When the median is smaller than k, you must increase the median and any elements to its right that are still below k; otherwise the median would remain too small after sorting. Iterate from the median toward the right and accumulate k - nums[i] for every element smaller than k. When the median is larger than k, iterate left from the median and accumulate nums[i] - k for elements greater than k. This works because only values affecting the median position matter after sorting, making it a greedy adjustment. The algorithm relies on sorting and a simple array traversal.
Approach 2: Binary Search on Median Boundary (Time: O(n log n), Space: O(1))
After sorting, you can use binary search to locate the boundary where values cross k. For the case where the median must increase, binary search finds the first element greater than or equal to k on the right side. Every element between the median index and that boundary contributes k - nums[i] operations. If the median must decrease, binary search finds the last element less than or equal to k on the left side and sums nums[i] - k for the affected range. Binary search avoids scanning unnecessary elements and highlights the monotonic property created by sorting. This approach combines sorting with a greedy cost calculation.
Recommended for interviews: The sorting and direct manipulation approach is what interviewers typically expect. It shows you understand how the median behaves in a sorted array and which elements actually influence it. The binary search variant is a clean optimization and demonstrates deeper control over ordered data, but the greedy scan is usually sufficient and easier to reason about under interview pressure.
This approach involves sorting the array to identify the median and then calculating the number of operations needed to convert it to k. By sorting the array, we can easily fetch the median. Depending on whether the median is greater than or less than k, we calculate the total operations required by simply subtracting k from the median value.
First, sort the array nums. Determine the median index by using integer division on the length of the list minus one. Find the median from the sorted array and calculate the number of operations required to convert the median to k by taking the absolute difference.
Time Complexity: O(n log n) due to the sorting operation.
Space Complexity: O(1) since sorting is done in-place.
This approach optimizes the search by leveraging binary search methods to locate the median directly without a complete sort. It relies on partition methodology to determine the suitable pivot where the median lies.
The code attempts to find the median through partitioning that behaves akin to quickselect, a deterministic variant of quicksort. Instead of full sorting, it targets the section where the middle element resides. The computation focus is on adapting the middle value directly for needed operations.
Python
JavaScript
Time Complexity: Average O(n) using partition-based median location (Quickselect).
Space Complexity: O(1) with in-place data manipulation.
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|.
Next, we discuss in two cases:
nums[m] > k, then all elements to the right of m are greater than or equal to k. We only need to reduce the elements greater than k on the left of m to k.nums[m] \le k, then all elements to the left of m are less than or equal to k. We only need to increase the elements less than k on the right of m to k.The time complexity is O(n times log n), and the space complexity is O(log n). Here, n is the length of the array nums.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Sorting and Direct Manipulation | Time Complexity: O(n log n) due to the sorting operation. Space Complexity: O(1) since sorting is done in-place. |
| Binary Search on Median | Time Complexity: Average O(n) using partition-based median location (Quickselect). Space Complexity: O(1) with in-place data manipulation. |
| Greedy + Sorting | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting and Direct Manipulation | O(n log n) | O(1) | Best general solution. Simple greedy scan after sorting. |
| Binary Search on Median Boundary | O(n log n) | O(1) | Useful when you want to quickly find the range of elements that must be adjusted. |
3107. Minimum Operations to Make Median of Array Equal to K | Adhoc | Sorting • Aryan Mittal • 2,351 views views
Watch 9 more video solutions →Practice Minimum Operations to Make Median of Array Equal to K with our built-in code editor and test cases.
Practice on FleetCode