Maximize median after doing k addition operation

JavaView on GFG

Intuition

Maximize median of array after adding 1 to k elements. Binary search on answer.

Algorithm

1Binary search on target median value m. Greedy: count how many elements need incrementing to be >= m. If <= k: feasible.

Common Pitfalls

•Binary search on answer. Sort array. Count elements < m and determine if k additions suffice to bring median >= m.

Maximize median after doing k addition operation.java

Java

// Approach: Binary search on target median value. Check feasibility with greedy increments.
// Time: O(n log(max)) Space: O(1)
import java.util.*;

class Solution {
    public int maximizeMedian(int[] arr, int k) {
        int n = arr.length;
        Arrays.sort(arr);
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        int i = 0;
        if (n % 2 == 0)
            i = (n / 2) - 1;
        else
            i = n / 2;

        while (i < n) {
            pq.add(arr[i]);
            i++;
        }

        while (k > 0) {
            int elem = pq.poll();
            pq.add(elem + 1);
            k--;
        }
        if (n % 2 == 0)
            return (pq.poll() + pq.poll()) / 2;
            
        return pq.poll();
    }
}

Was this solution helpful?