The Problem
Given
numslist andkoperations, where one operation increments one element by 1, find the maximum possible frequency of any value after at mostkoperations.
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)).
-
numsof 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 makexelements equal, using at mostkoperations?"
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:
| x | best window | cost | can(x)? |
|---|---|---|---|
| 1 | any element | 0 | ✅ |
| 2 |
[1, 4], target 4 |
8 − 5 = 3 | ✅ |
| 3 |
[1, 4, 8], target 8 |
24 − 13 = 11 | ❌ |
| 4 |
[1, 4, 8, 13], target 13 |
52 − 26 = 26 | ❌ |
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.
| target | window | cost for x=2 |
|---|---|---|
| 4 (in-group) | [1, 4] |
3 |
| 8 (outside group) | [1, 4] → [8, 8] |
7+4=11 |
| 13 (outside group) | [1, 4] → [13, 13] |
12+9=21 |
Cost only goes up. Two conclusions:
- Target
≥group's max (can't shrink values). - 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 ]
| group | cost = 7×3 − sum |
|---|---|
[2, 5, 7] (scattered — skips 4, includes 2) |
21 − 14 = 7 |
[4, 5, 7] (contiguous — closest 3 to target) |
21 − 16 = 5 |
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:
| target | cost = target×3 − 16 |
|---|---|
| 7 (window's own max) | 21 − 16 = 5 |
| 9 (higher, forced) | 27 − 16 = 11 |
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
| Move | Target | Window |
|---|---|---|
expand_left() |
same | grows by one on the left |
move_left() |
shifts | slides one step left |
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
| Step | Cost |
|---|---|
| Sort | O(N log N) |
| Window traversal (each element touched O(1) times) | O(N) |
| Total | O(N log N) |
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.
- Sorted order → optimal group is always contiguous.
- 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.
Top comments (0)