Watch 10 video solutions for Minimum Operations to Make Median of Array Equal to K, a medium level problem involving Array, Greedy, Sorting. This walkthrough by Aryan Mittal has 2,351 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |