I Didn't "Learn" Sliding Window — I Got Cornered Into It

The Problem

Given nums list and k operations, where one operation increments one element by 1, find the maximum possible frequency of any value after at most k operations.

Example: nums = [1, 4, 8, 13], k = 5. Best you can do: turn [1, 4] into [4, 4] (cost 3), then you've got 2 operations left over — not enough to reach 8. Answer: 2.

1. Approach 1 — Brute Force

Crux idea: I have k identical operations and N slots (elements). Distribute the k operations among the N slots in every possible way, measure the frequency each distribution gives, keep the best.

def maxFrequency(self, nums, k):
    if k == 0:
        return max(Counter(nums).values())

    m_freq = 0
    for j in range(len(nums)):
        new_list = nums.copy()
        new_list[j] += 1
        m_freq = max(m_freq, self.maxFrequency(new_list, k - 1))

    return m_freq

• N choices per operation, k operations → O(N^(k+1)).
• nums of length 10, k = 10 → ~10¹⁰ states. Dead on arrival.

The lesson: I was tracking which distribution produced the answer. The problem never asked for that — only the resulting number. Wrong problem, right answer eventually.

2. Approach 2 — Binary Search on the Answer

The thing I actually want is a frequency, and a frequency has a hard range:

low  = max frequency already present in nums
high = len(nums)

For nums = [1, 4, 8, 13]: low = 1, high = 4. Nothing outside [1, 4] is even meaningful.

A number confined to a known range, with a cheap yes/no check → binary search. So the whole problem becomes one boolean predicate:

can(x) = "Can I make x elements equal, using at most k operations?"

Claim: binary search over x is valid.
Property (Monotonicity): can(x) = True ⟹ can(x - 1) = True.
Argument: take any window that hits can(x) at cost C ≤ k. Drop one element from it — same target, less to raise, cost only falls. Still ≤ k. So can(x-1) holds.

Worked example, nums = [1, 4, 8, 13], k = 5:

True, True, False, False — flips once, never back. That's the shape binary search needs: probe the middle, discard a whole half.

3. What can(x) Actually Needs

Pick x elements — for what target? I guessed. Took a group, set the target to one of its own values, then nudged the target up and re-checked cost for the same x.

Cost only goes up. Two conclusions:

1. Target ≥ group's max (can't shrink values).
2. Target > group's max is pure waste (buys nothing).

So: cheapest target = the group's own maximum. And restricting the target to "one of the elements already in the group" loses nothing — I pick the group, so I pick the target too.

Sort the array, and one more thing falls out for free: the best x elements for a target are never scattered. Here's the detail, with numbers.

4. Why the Best Group Is Always Contiguous

Cost formula for a window [a, b, c] with target c (its own max):

cost = (c-a) + (c-b) + (c-c) = 3*c - (a+b+c)

# general form
cost = target * window_size - window_sum

Let say the input list is [ 1, 2, 4, 5, 7, 9 ]

Contiguous costs less. 2 is farther from 7 than 4 is, so swapping it in wastes budget for nothing.

Claim: for a fixed target, the optimal group of x elements is always contiguous in the sorted array, ending exactly at the target.
Argument: suppose an optimal group skips a larger b for a smaller a, where a ≤ b ≤ target. Swap them. Target unchanged. Cost for that slot drops from target − a to target − b (since b ≥ a) — in the example, swapping 2 for 4 drops that slot's cost from 5 to 3. Repeat for every such gap until none remain → contiguous block, same or lower total cost.

[ 1, 2, 4, 5, 7, 9 ]
        [ 4, 5, 7 ]   ← optimal 3-element group

Not "usually." Always — any gap can be swapped away, so a gapped group was never optimal to begin with.

That still leaves one open question: contiguous ending where? Try the same window [4, 5, 7] against a higher target, 9, instead of 7:

Cost more than doubles for the same three elements. That's because pushing the target above the window's own max buys nothing — it can't include a bigger element it doesn't have, it just makes every existing element travel further.

Claim: for a fixed contiguous window, the cheapest valid target is its own last (largest) element.
Argument: window [a₁, ..., aₓ], target t ≥ aₓ (can't shrink). Cost:

cost(t) = x·t − Σaᵢ

Linear in t, positive slope → minimized at the smallest feasible t, which is t = aₓ. ∎

BEST WINDOW = contiguous
BEST TARGET = window's last element

5. Why Keep Re-Scanning?

can(x) works: sort, slide a size-x window, check cost. Binary search over x.

It passed. It still bothered me — every new x meant sliding the same window over the same array again, from scratch:

can(3): [1,2,4] [2,4,5] [4,5,7] ...
can(4): [1,2,4,5] [2,4,5,7] ...
can(5): [1,2,4,5,7] ...

"Can't I keep ONE window and just expand or relax it?"

That question is the entire sliding window technique.

6. Approach 3 — One Window That Remembers

Consecutive windows overlap. Don't re-sum from scratch:

new_sum = old_sum - element_leaving + element_entering

Keep state (sum, size, boundaries). Update incrementally. That's the whole trick.

7. Don't Fix the Size Either

if cost <= k:
    # achievable — try to expand
if cost > k:
    # too expensive — relax / move

One pass, no separate scan per x.

8. Why Right to Left?

Largest element = most generous target (everything to its left is a candidate). Start there, narrow only when the budget forces it.

[1, 2, 4, 5, 7]
              ^ target
Everything left of it is candidate space.

9. Two Moves, One Window

Every step of the algorithm is one of these two moves. Nothing else happens.

10. The Window Class

class Window:
    def __init__(self, nums):
        self.data = nums
        self.ws = len(nums) - 1
        self.we = self.ws
        self.size = 1
        self.window_sum = self.data[self.ws]

    def _update_size(self):
        self.size = self.ws - self.we + 1

    def move_left(self):
        if self.we == 0:
            return False
        self.window_sum = (
            self.window_sum - self.data[self.ws] + self.data[self.we - 1]
        )
        self.ws -= 1
        self.we -= 1
        self._update_size()
        return True

    def expand_left(self):
        if self.we == 0:
            return False
        self.window_sum += self.data[self.we - 1]
        self.we -= 1
        self._update_size()
        return True

    def cost(self):
        return self.data[self.ws] * self.size - self.window_sum

11. The Final Algorithm

class Solution:
    def maxFrequency(self, nums: List[int], k: int) -> int:
        window = Window(sorted(nums))
        max_freq = 0

        while True:
            if window.cost() > k:
                if not window.move_left():
                    break
            else:
                max_freq = max(max_freq, window.size)
                if not window.expand_left():
                    break

        return max_freq

• Too expensive → slide left.
• Affordable → record it, try to grow.
• Nothing moves → done.

12. What It Costs

Started at O(N^(k+1)). That's not a small win.

13. The Whole Chain

graph TD
    subgraph A1["Approach 1 — Brute Force"]
        A1a["Distribute k things among N elements — try every distribution"]
        A1b["Cost: O(N^(k+1))"]
        A1a --> A1b
    end

    A1b --> R1["I care about the resulting frequency, not which distribution produced it."]

    subgraph A2["Approach 2 — Binary Search on the Answer"]
        A2a["Answer has a definite range: [max_freq(nums), len(nums)]"]
        A2b["Ask can(x) instead of enumerating distributions"]
        A2c["Sort the array"]
        A2d["Best group for a target is always contiguous"]
        A2e["Window cost = target × size − sum"]
        A2a --> A2b --> A2c --> A2d --> A2e
    end

    R1 --> A2a
    A2e --> R2["I'm rescanning the same array for every x."]

    subgraph A3["Approach 3 — Sliding Window"]
        A3a["Maintain window_sum + boundaries incrementally"]
        A3b["Let window size grow naturally, no fixed x"]
        A3c["Start from largest target, sweep right to left"]
        A3d["Window class: expand_left / move_left"]
        A3e["Cost: O(N log N)"]
        A3a --> A3b --> A3c --> A3d --> A3e
    end

    R2 --> A3a

    classDef approach fill:#4f46e5,stroke:#4f46e5,color:#fff,rx:6,ry:6;
    classDef insight fill:#fef3c7,stroke:#f59e0b,color:#92400e,rx:6,ry:6;
    class A1a,A1b,A2a,A2b,A2c,A2d,A2e,A3a,A3b,A3c,A3d,A3e approach;
    class R1,R2 insight;

14. What I Actually Learned

Not "spot the pattern, apply sliding window." It was: notice repeated work, refuse to redo it.

1. Sorted order → optimal group is always contiguous.
2. Contiguous group → optimal target is always its own last element.

Those two facts turn "maximize a frequency" into "manage a window" — and a window slides.

If you've solved this a different way, or my exchange argument hand-waves somewhere — tell me in the comments.