Scale Engineer

Minimum Operations to Make Median of Array Equal to K

Med
#2760Time: O(N log N)Space: O(log N) or O(N)1 company
Patterns
Greedy
Algorithms
Sorting
Data structures
Array
Companies
IBM

Prompt

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 * 105
  • 1 <= nums[i] <= 109
  • 1 <= k <= 109

Approaches

2 approaches with complexity analysis and trade-offs.

A straightforward approach is to first sort the array. Once sorted, the median is at a fixed position. We can then calculate the minimum operations by iterating through the relevant half of the array and summing up the differences needed to make elements satisfy the median condition with respect to k.

Algorithm

  • Sort the input array nums in non-decreasing order.
  • Determine the size of the array, n, and find the median index, m = n / 2.
  • Initialize a long variable operations to 0 to accumulate the total cost.
  • If the element at the median index, nums[m], is greater than k:
    • Iterate from the beginning of the array up to the median index (i from 0 to m).
    • For each element nums[i] that is greater than k, add the difference nums[i] - k to operations.
  • If nums[m] is less than k:
    • Iterate from the median index to the end of the array (i from m to n-1).
    • For each element nums[i] that is less than k, add the difference k - nums[i] to operations.
  • If nums[m] is equal to k, no operations are needed, and the loops will correctly result in 0 operations.
  • Return the total operations.

Walkthrough

The core idea is that to change the median to k, we only need to modify one half of the array.

First, sort the input array nums. The median is the element at index m = n / 2 (0-indexed), where n is the length of the array. This is because the problem defines the median as the larger of the two middle elements for even-sized arrays, which corresponds to the element at index n/2.

  • If the current median nums[m] is already equal to k, no operations are needed.
  • If nums[m] is less than k, we need to increase the median. To do this with minimum operations, we must increase nums[m] and any subsequent elements that are also less than k. We iterate from the median index m to the end of the array. For each element nums[i] < k, we add k - nums[i] to our total operations count. This ensures that at least half of the elements are k or greater, making k the new median.
  • If nums[m] is greater than k, we need to decrease the median. Symmetrically, we must decrease nums[m] and any preceding elements that are greater than k. We iterate from the median index m down to the beginning. For each element nums[i] > k, we add nums[i] - k to the total operations. This ensures at least half of the elements are k or smaller.

The total sum of these adjustments gives the minimum number of operations. A long should be used for the operations count to prevent potential overflow.

import java.util.Arrays; class Solution {    public long minOperationsToMakeMedianK(int[] nums, int k) {        Arrays.sort(nums);        long operations = 0;        int n = nums.length;        int medianIndex = n / 2;         if (nums[medianIndex] > k) {            // Decrease elements in the lower half (including median) that are > k            for (int i = medianIndex; i >= 0; i--) {                if (nums[i] > k) {                    operations += (long)nums[i] - k;                } else {                    break; // Array is sorted, no more elements will be > k                }            }        } else if (nums[medianIndex] < k) {            // Increase elements in the upper half (including median) that are < k            for (int i = medianIndex; i < n; i++) {                if (nums[i] < k) {                    operations += (long)k - nums[i];                } else {                    break; // Array is sorted, no more elements will be < k                }            }        }                return operations;    }}

Complexity

Time

O(N log N)

Space

O(log N) or O(N)

Trade-offs

Pros

  • Simple to understand and implement.

  • Leverages standard, well-tested library functions for sorting.

Cons

  • The time complexity of O(N log N) is not optimal for this problem, as a linear time solution exists.

Solutions

class Solution {public  long minOperationsToMakeMedianK(int[] nums, int k) {    Arrays.sort(nums);    int n = nums.length;    int m = n >> 1;    long ans = Math.abs(nums[m] - k);    if (nums[m] > k) {      for (int i = m - 1; i >= 0 && nums[i] > k; --i) {        ans += nums[i] - k;      }    } else {      for (int i = m + 1; i < n && nums[i] < k; ++i) {        ans += k - nums[i];      }    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem