Generated by Codex with GPT-5

Quick facts

What the problem is really asking

Given an array of positive integers and a budget k, one operation lets us increase one element by 1. The goal is to make some value appear as many times as possible after using at most k total increments.

The important restriction is that values can only go up. We cannot decrease a large value to match smaller values. That means if several numbers are going to become equal, it is natural to choose one of the larger numbers as the target and raise smaller numbers up to it.

For example, with sorted numbers [1, 2, 4] and k = 5, we can raise 1 to 4 using 3 operations and raise 2 to 4 using 2 operations. That makes all three numbers equal to 4, so the answer is 3.

The key idea

Sort the array first. After sorting, any group of numbers we want to turn into the same value should be a contiguous window.

Why contiguous? Suppose the target is the rightmost value in a sorted group. If we include a smaller number on the left, then every number between that smaller number and the target is at least as cheap to raise to the same target. Skipping the middle numbers would never help us get a larger frequency.

So the problem becomes:

“What is the longest sorted window that can be raised so every value equals the window’s rightmost value?”

For a window from left to right, the target value is nums[right]. If the window length is window_size and the sum of the current values is window_sum, then the cost to raise every value in the window to the target is:

nums[right] * window_size - window_sum

If that cost is at most k, the window is feasible. If it is too expensive, move left rightward until the window becomes feasible again.

Why the sliding window works

Once the array is sorted, extending the right edge only keeps the same target or increases it. That can make the current window more expensive, but shrinking from the left always removes one of the smallest values, which is the most expensive kind of value to raise.

This gives a clean two-pointer loop:

  1. Sort the numbers.
  2. Move right across the array.
  3. Add the new value to the running window sum.
  4. While the window costs more than k, remove values from the left.
  5. After the window is valid, update the best length.

Each element enters the window once and leaves the window at most once, so the scan after sorting is linear.

Python solution

from typing import List, Sequence


def increments_needed_to_match_target(
    target_value: int,
    window_size: int,
    window_sum: int,
) -> int:
    """Return the cost to raise every value in a window to target_value."""
    return target_value * window_size - window_sum


def max_frequency_after_increments(numbers: Sequence[int], max_increments: int) -> int:
    """
    Return the largest possible frequency after at most max_increments increases.

    The algorithm sorts the values, then keeps the largest window that can be
    raised to match its rightmost value within the operation budget.
    """
    if not numbers:
        return 0
    if max_increments < 0:
        raise ValueError("max_increments must be non-negative")

    sorted_numbers = sorted(numbers)
    left = 0
    window_sum = 0
    best_frequency = 1

    for right, target_value in enumerate(sorted_numbers):
        window_sum += target_value

        while left <= right:
            window_size = right - left + 1
            required_increments = increments_needed_to_match_target(
                target_value=target_value,
                window_size=window_size,
                window_sum=window_sum,
            )

            if required_increments <= max_increments:
                break

            # Remove the smallest current value. In a sorted array this is the
            # leftmost value, and it costs the most to raise to target_value.
            window_sum -= sorted_numbers[left]
            left += 1

        best_frequency = max(best_frequency, right - left + 1)

    return best_frequency


class Solution:
    def maxFrequency(self, nums: List[int], k: int) -> int:
        return max_frequency_after_increments(
            numbers=nums,
            max_increments=k,
        )

Correctness and complexity

The cost formula is exact because making every value in the window equal to target requires adding target - value for each value. Summing that over the window gives target * window_size - window_sum.

The sorted-window choice is safe because the final target must be one of the values at or above the chosen elements. For any target value in the sorted array, the cheapest elements to raise to it are the closest values immediately to its left. Therefore the best group for a fixed target is always some contiguous window ending at that target.

The sliding window checks those candidate windows efficiently. Whenever the current window is too expensive, removing the leftmost value is the right repair because that value is the smallest in the window and contributes the largest gap to the target. Once the window is valid again, every shorter suffix ending at the same target is also valid, and the current valid window is the longest one for that right.

Sorting costs O(n log n). The two-pointer scan costs O(n) because each pointer only moves forward. The total time is O(n log n), and the extra space is O(n) for the sorted copy. If modifying the input is allowed, the array can be sorted in place.

Interview follow-ups

Could this be solved with binary search instead of a sliding window?

Yes. After sorting, binary search the answer length m. For each candidate length, scan every length-m window and use prefix sums to compute the cost of raising that window to its rightmost value. If any window costs at most k, then length m is feasible; otherwise it is not.

This works because feasibility is monotonic. If a frequency of m is possible, every smaller frequency is also possible. The tradeoff is that binary search adds a log n factor to the post-sort scan, giving O(n log n) after sorting rather than the sliding window’s O(n) scan. Since sorting already costs O(n log n), both are acceptable, but the sliding window is simpler and tighter.

Why is it enough to target an existing value?

If a group can be raised to some value that is not already in the group, lowering that target down to the largest original value in the group only reduces the number of increments needed and keeps the same frequency. Since the goal is frequency, not the final value itself, there is no benefit to overshooting past the largest included number.

That is why the sorted algorithm uses the rightmost value of each window as the target. It represents the cheapest useful target for that group.

What if the operation allowed both incrementing and decrementing?

The target would no longer have to be the rightmost value. With both directions allowed, the cheapest value to make a group equal is its median, not its maximum. The window idea can still be useful after sorting, but the cost formula changes to the sum of distances from the median.

For a fixed window, prefix sums can compute the cost to move the left half up to the median and the right half down to the median. The usual solution then searches for the largest valid window using either sliding-window-style maintenance or binary search on the window length. The complexity is still typically dominated by sorting.

What if the input stream is too large to sort in memory?

The exact solution fundamentally needs order information, because it depends on groups of numerically close values. If all values are from a small bounded range, a counting array or histogram can replace sorting and allow a range-based sliding window. That trades memory proportional to the value range for avoiding an explicit sort.

If the value range is huge and the stream cannot fit in memory, an exact one-pass solution is not realistic under ordinary memory limits. The practical approach would be external sorting, database-style ordered aggregation, or an approximate sketch if an approximate answer is acceptable.

Can this return the actual value and indices, not just the frequency?

Yes. Track the best left and right window whenever best_frequency improves. The target value is then sorted_numbers[best_right], and the values in that sorted window are the elements to raise.

Returning original indices requires preserving each number’s original position before sorting, for example by sorting pairs (value, index). The algorithm and cost formula stay the same, but the implementation carries indices along so it can report which original elements belong to the best window.

Practical takeaway

The main move is to sort first so the one-way nature of increments becomes visible. Once the values are ordered, the best candidates are contiguous windows, and the operation cost is just “target total minus current total.” That turns a problem that looks like arbitrary editing into a straightforward sliding-window scan.