Make Maximum Number of Elements Equal with K Updates

Make Maximum Elements Equal with K Updates asks: with a budget of k total increments, how many array elements can you make equal? It is a clean example of the sort + sliding window pattern, where the window cost is computed from a running sum.

The slow way first

You could try every possible target value and, for each one, greedily pick the cheapest elements to raise up to it. But matching elements to targets without a plan leads to checking far too many combinations — an O(n²) scan at best, and messy to reason about.

The question to ask: which elements should share a target? Since increments only go up, you would never raise an element past a smaller neighbor unnecessarily. After sorting, the elements you make equal are always a contiguous block, and the cheapest shared target for that block is its largest member — the right end.

The idea: sort, then slide a window to the right end

Sort the array. Consider a window from l to r. To make every element in it equal, raise them all to nums[r] (the biggest). The cost is:

cost = nums[r] * (r − l + 1) − sum(window)

That is "what we want them all to be" minus "what they already total." Slide r rightward, adding to a running sum. Whenever the cost exceeds k, shrink from the left until it fits. The widest window that ever fits is the answer.

The cost formula only needs the window length, the right-end value, and the running sum — all O(1) to maintain — so the whole scan is one pass after sorting.

Walk through it

Step through the animation. The window [l, r] grows as r advances. The cost label shows nums[r] * len − sum. At r = 4 the window [1, 2, 4, 4, 5] costs 9, over budget, so l advances and drops the 1. The widest affordable window has size 4.

Pseudocode

sort nums ascending
l = 0, total = 0, best = 0
for r from 0 to n-1:
    total += nums[r]                       # add new right element to sum
    while nums[r] * (r - l + 1) - total > k:
        total -= nums[l]                   # too costly: shrink from left
        l += 1
    best = max(best, r - l + 1)            # widest valid window so far
return best

The Python solution

def max_equal(nums, k):
    nums.sort()
    l = total = best = 0
    for r in range(len(nums)):
        total += nums[r]
        while nums[r] * (r - l + 1) - total > k:
            total -= nums[l]; l += 1
        best = max(best, r - l + 1)
    return best

• nums.sort() makes the elements we equalize a contiguous block whose cheapest target is the right end.
• l, total, best track the window left edge, the running window sum, and the best width found.
• total += nums[r] extends the window to include the new right element.
• The while line is the cost check: nums[r] * window_len - total is the increments needed to lift everyone to nums[r]. If it exceeds k, we drop nums[l] and advance l.
• best = max(best, r - l + 1) records the widest window that stayed within budget.

Complexity

Sorting costs O(n log n); the window scan is linear because l and r each only move forward across the array. Beyond the sort, no extra space is needed.

When this pattern shows up

Practice