We have an array of integers and a budget of k increment operations. Each operation adds 1 to any element we choose. We want to maximize how many elements share the same value after using at most k operations.

We can only increment elements, never decrement them. So to make a group of elements equal, they must all be raised to the value of the largest element in that group. Overshooting past that largest value only wastes operations, so the target is always some value already present in the array.

The problem reduces to: pick a target value equal to one of the array elements, and find how many smaller elements we can afford to raise up to that target within the budget of k.

Sorting makes this tractable. Once the array is sorted, the elements closest in value to a target sit right next to it, and those are the cheapest to raise. The problem becomes finding the longest window in a sorted array where the cost of raising every element to the window's maximum stays within k.

Key Constraints:

Intuition

Sort the array, then for every possible target element nums[right], count how many elements to its left we can afford to raise up to that value. Iterate backward from right, accumulating the cost of each increment, and stop once the budget is exhausted.

Working backward from the target picks up the cheapest elements first, since in sorted order the elements nearest nums[right] need the fewest increments to reach it. Including those before the farther ones maximizes the count for any fixed budget.

Algorithm

Visualization and Code

For each target element, this scans backward through the array and recomputes the cost from scratch. Maintaining a running window sum and only moving the left boundary when the budget is exceeded removes that repeated work.

Intuition

After sorting, the cheapest elements to raise to any target are its immediate neighbors, so the affordable elements for a given target form a contiguous block. That maps directly onto a sliding window over the sorted array.

For a window [left, right], raising every element to nums[right] (the largest in the window) costs nums[right] * windowSize - windowSum. Each element nums[i] needs nums[right] - nums[i] increments to reach the target; summing that over the window gives nums[right] * windowSize minus the sum of the window.

The window expands right one step at a time, adding the new element to the running sum. When the cost exceeds k, it shrinks from the left by removing nums[left] from the sum and advancing left. The largest window size reached is the answer.

Algorithm

Visualization and Code

The sliding window is already O(n log n), dominated by sorting. The same time bound is reachable from a different angle: fix each right endpoint and binary search for how far left the window can extend, using prefix sums to evaluate each candidate in constant time.

Intuition

After sorting, for each index right, find the smallest index left such that the cost of making all elements in [left, right] equal to nums[right] is at most k. The window size right - left + 1 for that smallest left is the best frequency achievable with nums[right] as the target.

The cost is nums[right] * (right - left + 1) - sum(nums[left..right]). Precomputing prefix sums makes sum(nums[left..right]) an O(1) lookup. As left moves closer to right, the window holds fewer and cheaper-to-raise elements, so the cost decreases monotonically. That monotonicity allows a binary search for the smallest affordable left.

The approach builds a prefix sum array, then for each right binary searches for the farthest-left position that keeps the cost within k.

Algorithm

Visualization and Code