# Minimum Operations to Make Median of Array Equal to K
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-operations-to-make-median-of-array-equal-to-k)
Canonical: https://scaleengineer.com/dsa/problems/minimum-operations-to-make-median-of-array-equal-to-k
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [IBM](https://scaleengineer.com/companies/ibm)
---
## Problem
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
## Sorting-Based Approach
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`.
**Time:** O(N log N) · **Space:** O(log N) or O(N)
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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`.

## Linear Time Approach using Selection Algorithm
A more optimal approach avoids the O(N log N) cost of a full sort. By using a selection algorithm like Quickselect, we can find the median element and partition the array in O(N) time on average. After partitioning, the elements are arranged such that the median is in its correct sorted position. We can then apply the same logic as the sorting approach to calculate the operations on the partially sorted array.
**Time:** O(N) on average · **Space:** O(log N)
**Pros:** Asymptotically faster with O(N) average time complexity.; More efficient for very large datasets where the log N factor from sorting would be significant.
**Cons:** More complex to implement correctly compared to sorting.; A naive Quickselect has a worst-case time complexity of O(N^2), though this is rare with good pivot selection. A guaranteed O(N) version (e.g., Introselect) is even more complex.
### Explanation
This approach improves upon the first one by replacing the full sort with a faster selection algorithm. The goal is to find the median element and partition the array around it without sorting the entire array.

An algorithm like Quickselect can find the k-th smallest element in an array in average linear time, `O(N)`. We use it to find the element that would be at the median index `m = n / 2`.

This operation rearranges the array `nums` such that `nums[m]` holds the true median value, all elements at indices less than `m` are less than or equal to `nums[m]`, and all elements at indices greater than `m` are greater than or equal to `nums[m]`. Once the array is partitioned this way, the logic is identical to the sorting-based approach:

- If `nums[m] < k`, we iterate through the second half of the (now partitioned) array (from index `m` to `n-1`) and sum the costs `k - nums[i]` for any `nums[i] < k`.
- If `nums[m] > k`, we iterate through the first half (from index `m` down to `0`) and sum the costs `nums[i] - k` for any `nums[i] > k`.

This method achieves a better time complexity, which can be significant for very large inputs. While Java's standard library does not provide a direct `nth_element` function, implementing Quickselect is a common way to achieve this linear time performance.

```java
import java.util.concurrent.ThreadLocalRandom;

class Solution {
    public long minOperationsToMakeMedianK(int[] nums, int k) {
        int n = nums.length;
        int medianIndex = n / 2;
        
        // Partition the array using Quickselect to find the median element
        quickSelect(nums, 0, n - 1, medianIndex);
        
        long operations = 0;
        int medianValue = nums[medianIndex];

        if (medianValue > k) {
            for (int i = 0; i <= medianIndex; i++) {
                if (nums[i] > k) {
                    operations += (long)nums[i] - k;
                }
            }
        } else if (medianValue < k) {
            for (int i = medianIndex; i < n; i++) {
                if (nums[i] < k) {
                    operations += (long)k - nums[i];
                }
            }
        }
        return operations;
    }

    // Iterative Quickselect to find the k-th smallest element
    private void quickSelect(int[] nums, int left, int right, int k) {
        while (left < right) {
            int pivotIndex = partition(nums, left, right);
            if (pivotIndex == k) {
                return;
            } else if (pivotIndex < k) {
                left = pivotIndex + 1;
            } else {
                right = pivotIndex - 1;
            }
        }
    }

    private int partition(int[] nums, int left, int right) {
        int pivotIndex = ThreadLocalRandom.current().nextInt(left, right + 1);
        int pivotValue = nums[pivotIndex];
        swap(nums, pivotIndex, right);
        int storeIndex = left;
        for (int i = left; i < right; i++) {
            if (nums[i] < pivotValue) {
                swap(nums, storeIndex, i);
                storeIndex++;
            }
        }
        swap(nums, right, storeIndex);
        return storeIndex;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
```
### Algorithm
- Find the median index `m = nums.length / 2`.
- Use a selection algorithm (like Quickselect) to partition the array `nums` around the `m`-th element. After this operation, `nums[m]` holds the true median value, all elements at indices `< m` are less than or equal to `nums[m]`, and all elements at indices `> m` are greater than or equal to `nums[m]`.
- Initialize `operations = 0L`.
- If `nums[m] > k`, iterate from `i = 0` to `m`. For each `nums[i] > k`, add `nums[i] - k` to `operations`.
- If `nums[m] < k`, iterate from `i = m` to `n-1`. For each `nums[i] < k`, add `k - nums[i]` to `operations`.
- Return `operations`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long minOperationsToMakeMedianK(vector<int> &nums, int k) {
    sort(nums.begin(), nums.end());
    int n = nums.size();
    int m = n >> 1;
    long long ans = 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;
  }
};

```

### Python

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

```