Maximum Frequency with K Increments

Problem Overview

Increments only raise values, so the target value should be one that already exists, and the cheapest numbers to raise are the ones just below it.

Intuition

Increments only raise values, so the target value should be one that already exists, and the cheapest numbers to raise are the ones just below it. After sorting, those numbers form a window that ends at the target. Making the whole window equal to its right end costs the right value times the window size minus the window sum. A sliding window keeps that cost within k, and because only the best size matters, the window never needs to shrink.

Algorithm

1Sort the array.
2Move the right end forward one element at a time and add it to the window sum.
3If the right value times the window size minus the sum is more than k, drop the leftmost element so the window slides forward without shrinking.
4Use a long for the cost, because the product can exceed the int range.
5Return the array length minus the final left index, which is the largest window that ever fit.

Example Walkthrough

Input: arr = [1,4,8,13], k = 5

1. Raising 4 to 8 costs 4, so the window 4, 8 fits with size 2.
2. Adding 13 would cost 13 times 3 minus 25, which is 14, too much.
3. The window 8, 13 costs 5 and also has size 2, and no window of size 3 fits.

Output: 2

Common Pitfalls

• Only increments are allowed, so raise smaller numbers toward the largest one in the window.
• Compute the cost with a long. A large value times a large window can overflow an int.
• The window size never goes down, so the final size is the answer and no separate maximum is needed.
• Sorting dominates the running time. The window itself takes linear time.

Maximum Frequency with K Increments.java

Java

// Approach: Increments only raise values, so the best target is an existing
// value, and the cheapest elements to raise are the closest ones below it.
// After sorting, a window ending at right can all become arr[right] for
// arr[right] * size - windowSum operations. The window never shrinks: when
// the cost exceeds k it slides forward by one, so its size only grows when a
// larger valid window exists, and the final size is the answer.
// Complexity: O(n log n) time for the sort, O(1) extra space beyond sorting.
import java.util.Arrays;

class Solution {
    public int maxFrequency(int[] arr, int k) {
        Arrays.sort(arr);
        int left = 0;
        long sum = 0;
        for (int right = 0; right < arr.length; right++) {
            sum += arr[right];
            if ((long) arr[right] * (right - left + 1) - sum > k)
                sum -= arr[left++];
        }
        return arr.length - left;
    }
}

Was this solution helpful?