Skip to main content
Talentd

Minimum Operations to Make Median of Array Equal to K - Solution & Explanation

MediumArrayGreedySorting13 min readAsked at: IBM
Practice this problem

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 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

Approach Overview

Problem 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 1: Sorting and Direct Manipulation

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.

Code

PythonJavaScriptCC++JavaC#

Python

JavaScript

C

C++

Java

C#

Complexity

Time Complexity: O(n log n) due to the sorting operation.

Space Complexity: O(1) since sorting is done in-place.

Try this approach in the editor →

Approach 2: Binary Search on Median

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.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: Average O(n) using partition-based median location (Quickselect).

Space Complexity: O(1) with in-place data manipulation.

Try this approach in the editor →

Approach 3: 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|.

Next, we discuss in two cases:

  • If 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.
  • If 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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sorting and Direct ManipulationO(n log n)O(1)Best general solution. Simple greedy scan after sorting.
Binary Search on Median BoundaryO(n log n)O(1)Useful when you want to quickly find the range of elements that must be adjusted.

Video Solution

3107. Minimum Operations to Make Median of Array Equal to K | Adhoc | Sorting • Aryan Mittal • 2,388 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Minimum Operations to Make Median of Array Equal to K easy or hard?
This problem is typically classified as Medium difficulty. The challenge comes from recognizing that only elements affecting the median after sorting matter. Once that insight is clear, the greedy adjustment becomes straightforward.
Minimum Operations to Make Median of Array Equal to K Python/Java solution
Implementations in Python, Java, C++, or JavaScript follow the same steps: sort the array, compute the median index, and accumulate the difference between elements and k depending on whether the median must increase or decrease. The logic remains identical across languages with O(n log n) time complexity.
How to solve Minimum Operations to Make Median of Array Equal to K in O(n)?
A strict O(n) solution is difficult because determining the median typically requires sorting or selection. Most implementations sort the array in O(n log n) and then adjust elements around the median. If a linear-time median selection algorithm is used, the adjustment phase can run in O(n), but this is rarely required in interviews.
What is the best approach for Minimum Operations to Make Median of Array Equal to K?
The most common solution sorts the array and directly adjusts elements affecting the median. After sorting, check the middle index and either increase elements on the right or decrease elements on the left until the median becomes k. This greedy approach runs in O(n log n) time due to sorting and uses O(1) extra space.
Is Minimum Operations to Make Median of Array Equal to K asked at Google/Amazon/Meta?
Median manipulation and greedy adjustment problems appear frequently in interviews at companies like Amazon, Google, and Meta. Variations involving medians, cost minimization, and sorted arrays are common because they test understanding of ordering properties and greedy reasoning.
What data structure is used in Minimum Operations to Make Median of Array Equal to K?
The primary data structure is a simple array. The algorithm relies on sorting the array and then iterating from the median index. No additional structures like heaps or hash maps are required for the optimal approach.
What is the time complexity of Minimum Operations to Make Median of Array Equal to K?
The optimal solution runs in O(n log n) time because the array must be sorted first. After sorting, a single linear scan from the median outward computes the required operations, which takes O(n). Space complexity is O(1) if sorting is done in-place.

Ready to solve this problem?

Practice Minimum Operations to Make Median of Array Equal to K with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find Median from Data Stream

Next

Sliding Window Median