Phase 1: The Problem — Why Nested Loops Are a Trap for Subarray Questions
Take a question that sounds almost too simple to matter: given an array of numbers, find the maximum sum of any five consecutive elements. Nearly everyone’s first instinct is the same, and it’s not a bad instinct — for every possible starting position, sum up the next five elements, and keep track of the best sum seen so far. It’s correct. It’s also, in a way that isn’t obvious until you actually sit with it, doing a huge amount of unnecessary work.
Here’s what’s actually happening under the hood of that instinct. If the array has n elements, there are roughly n possible starting positions, and for each one you’re summing 5 elements — so the total work is proportional to n times 5. That constant factor of 5 feels harmless. But generalize the question slightly — find the maximum sum of any k consecutive elements, where k is passed in as a parameter, potentially large — and the same nested-loop instinct now does work proportional to n times k, which degrades toward O(n²) as k grows toward the size of the array itself. On an array of 100,000 elements with k in the thousands, that’s now hundreds of millions of operations for what feels like it should be an almost trivial computation.
The deeper issue, once you actually look at why this is slow, is genuinely illuminating: the brute-force approach is redoing work it already did. When you slide from the window starting at index 0 to the window starting at index 1, four of the five elements in that window are literally the same four elements as before — you’re re-summing numbers you already summed one step ago, purely because the nested-loop structure has no memory of the previous window’s result. This is the exact same category of inefficiency you’d notice if someone asked you to compute a running total by, at every single step, re-adding every number from the very beginning instead of just adding the one new number to the running total you already have.
This observation — that consecutive windows over an array share almost all of their elements, and only differ by what’s entering on one side and leaving on the other — is the entire seed of the sliding window pattern. It’s not a clever trick pulled from nowhere; it’s the direct, natural consequence of noticing that brute force is wastefully recomputing shared work, and asking the obvious follow-up question: if 80% of the work is identical between one window and the next, why are we redoing all of it?
Historically, this pattern became one of the most heavily emphasized topics in technical interviews precisely because it separates candidates who pattern-match “subarray problem, therefore nested loop” from candidates who actually notice the redundant computation and eliminate it — and because the exact same underlying idea, generalized slightly, shows up constantly in real production code dealing with streams, logs, and time-series data, well beyond the interview room.
Phase 2: The Mental Model — A Physical Window Sliding Across a Ruler
The name “sliding window” is unusually literal, and leaning into that literalness is the fastest way to build real intuition rather than memorizing a template.
Picture the array laid out in a row, like marks on a ruler. Now imagine a physical rectangular window — a fixed-size cutout — placed over the leftmost portion of that ruler, covering exactly k consecutive marks. You can see, and know the sum of, whatever falls inside that window. Now, instead of picking the window up and placing it down somewhere else (which is what the brute-force nested loop effectively does — throwing away all prior information and recomputing from scratch), you slide it one position to the right. Sliding, as opposed to picking-up-and-placing, has an important physical consequence: one mark at the left edge of the window disappears from view, and exactly one new mark at the right edge comes into view. Everything else the window was covering a moment ago is still covered.
This physical sliding action maps directly onto the algorithmic insight from Phase 1: instead of recomputing the sum of everything inside the window from scratch at every position, you maintain a running sum and update it incrementally — subtract the value of the mark that just left the window on the left, add the value of the mark that just entered on the right. That’s it. That’s the entire computational savings: turning an O(k) recomputation at every step into an O(1) update at every step, purely by exploiting the fact that sliding, unlike jumping, only changes the window’s contents at its two edges.
There’s a second, equally important idea hiding inside this mental model, and it’s the one that separates a genuinely fluent understanding of the pattern from a shallow “I memorized the fixed-size template” understanding: the window doesn’t always have to be a fixed size. Sometimes the actual question being asked requires the window to grow and shrink dynamically based on some condition — think of it not as a rigid rectangular cutout of fixed width, but as a rubber band stretched between two fingers on the ruler, where one finger (the right edge) generally moves forward to include more elements, and the other finger (the left edge) moves forward independently whenever the current stretch of the rubber band violates some rule you care about (too large a sum, too many repeated characters, whatever the specific problem defines). This variable-size variant is genuinely a different flavor of the same underlying idea, and Phase 3 treats it as its own distinct case, because conflating the two is exactly where most learners get tripped up.
Phase 3: Internal Working Deep Dive — Fixed-Size and Variable-Size Windows, Mechanically
3.1 Recognizing When Sliding Window Applies At All
Before the mechanics, it’s worth being explicit about the recognition signal, since that’s actually the harder skill in practice — implementing the pattern once you know it applies is comparatively easy. Sliding window is the right tool specifically when a problem asks about a contiguous subarray or substring (not an arbitrary subset — contiguity is non-negotiable, because it’s exactly what guarantees consecutive windows share most of their elements), and the property being computed or checked can be incrementally updated as the window moves — meaning you can cheaply account for one element leaving and one element entering, rather than needing to look at the whole window’s contents again from scratch to answer the question. Sum, count of distinct characters, count of a specific condition being met, and maximum/minimum (with an auxiliary structure, covered in 3.4) all satisfy this. A property that genuinely requires re-examining the entire window’s full contents in a way that can’t be incrementally maintained is a signal that sliding window either doesn’t apply cleanly or needs a more sophisticated auxiliary structure layered on top of it.
3.2 The Fixed-Size Window — Mechanically
For the “maximum sum of any k consecutive elements” problem from Phase 1, the mechanics are genuinely simple once stated precisely. First, compute the sum of the very first window — elements at indices 0 through k-1 — the ordinary way, since there’s no prior window to slide from yet. Store this as both the current window sum and the best sum seen so far.
Then, for every subsequent position, slide the window forward by exactly one index: subtract the element that’s now leaving the window (the one at the position the window’s left edge just moved past) and add the element that’s now entering (the one at the window’s new right edge). Compare the updated current sum against the best sum seen so far, updating if needed. Repeat until the window’s right edge reaches the end of the array.
The entire algorithm does a fixed, small amount of work — one subtraction, one addition, one comparison — at each of roughly n positions, for a total cost proportional to n, regardless of how large k is. This is the direct payoff of the incremental-update insight from Phase 2: the cost of maintaining the window no longer depends on the window’s size at all, only on how many times it slides.
3.3 The Variable-Size Window — Mechanically
Consider a genuinely different question: given an array of positive numbers and a target sum, find the length of the shortest contiguous subarray whose sum is at least the target. Here, there’s no fixed k given up front — the window’s size is precisely what you’re trying to figure out, which immediately rules out the fixed-size mechanics from 3.2.
This is handled with two independently-moving pointers, typically called left and right, both starting at index 0. The right pointer advances through the array one step at a time, and at each step, the element it now points to gets added into the current window’s running sum — this is the “growing” half of the rubber band from Phase 2’s mental model. After each expansion, a check runs: does the current window’s sum now meet or exceed the target? If yes, this is a candidate valid window — but rather than immediately moving on, the algorithm tries to shrink the window from the left, repeatedly, for as long as the sum still meets the target after removing the leftmost element. Each successful shrink is a chance to record a shorter valid window length than any found before, since a shorter valid window is strictly more useful information than a longer one for this specific question. Once shrinking from the left would drop the sum below the target, shrinking stops, and the right pointer resumes advancing to grow the window again.
The subtlety worth naming explicitly here, because it’s the thing that makes people nervous about this pattern’s time complexity at first glance: it looks like there might be a nested loop happening — an outer loop advancing right, and an inner loop advancing left — which seems like it should be O(n²) again. But the crucial observation is that the left pointer, across the entire execution of the algorithm, never moves backward and never resets — it only ever advances forward, and it can advance at most n total steps across the whole run, not n steps per position of the right pointer. The same is true of the right pointer. Because both pointers each move forward at most n times in total, summed across the entire algorithm rather than per-iteration, the total work is O(n), not O(n²) — a genuinely non-obvious fact the first time you encounter it, and one worth actually convincing yourself of by tracing through a small example by hand, rather than taking on faith.
3.4 When the Window Needs to Answer “What’s the Max/Min Inside It Right Now”
A harder variant, and a genuinely instructive extension of the core pattern: what if the question requires knowing the maximum (or minimum) value currently inside the window at every position, as the window slides — for example, “find the maximum value in every window of size k across the array”? A naive approach would scan the entire window to find its max every time it slides, which reintroduces exactly the O(n·k) cost the whole pattern exists to avoid.
The fix is maintaining an auxiliary data structure alongside the window — typically a double-ended queue (deque) that stores, at all times, only the candidates that could possibly be the current window’s maximum, in decreasing order, and critically, discards from the back of the queue any element that’s smaller than the element currently being added, because a smaller element positioned before a larger one can never become the window’s maximum for as long as that larger element remains in the window — it’s permanently and provably irrelevant the moment a larger, more-recent element enters. Elements also get removed from the front of the queue once they slide out of the window’s left edge entirely. Because every element is added to and removed from this deque at most once across the whole algorithm — the same “each element does a bounded, constant amount of total work” argument from 3.3 — the overall cost stays O(n), even though answering “what’s the max right now” at every single window position would, naively, seem to require re-scanning the window each time.
This specific technique — the monotonic deque — is worth understanding on its own merits beyond this one problem, because it shows up as a recurring building block anywhere a sliding structure needs fast access to an extremum, not just in this exact windowed-maximum problem.
Phase 4: Engineering Implementation — Fixed, Variable, and Monotonic-Deque Windows
The following reflects the mechanics from Phase 3, with the reasoning behind each decision made explicit.
def max_sum_fixed_window(nums, k):
# Fixed-size window (3.2): compute the first window directly,
# then slide by subtracting what leaves and adding what enters —
# never re-summing the whole window from scratch.
window_sum = sum(nums[:k])
best = window_sum
for i in range(k, len(nums)):
window_sum += nums[i] - nums[i - k]
best = max(best, window_sum)
return best
def shortest_subarray_at_least_target(nums, target):
# Variable-size window (3.3): right pointer grows the window,
# left pointer shrinks it whenever the current window is valid,
# trying to find a strictly shorter valid window each time.
left = 0
window_sum = 0
best_length = float('inf')
for right in range(len(nums)):
window_sum += nums[right]
# Shrink from the left as long as the window is still valid —
# each shrink is a chance at a shorter answer. The left
# pointer only ever moves forward, which is what keeps this
# O(n) overall rather than O(n^2) despite the nested-looking loops.
while window_sum >= target:
best_length = min(best_length, right - left + 1)
window_sum -= nums[left]
left += 1
return best_length if best_length != float('inf') else 0
from collections import deque
def max_in_every_window(nums, k):
# Monotonic deque (3.4): store only elements that could still
# possibly be a future window's maximum, in decreasing order.
dq = deque() # stores indices, not values
result = []
for i, num in enumerate(nums):
# Any smaller element before a larger one can never become
# the max while the larger one is still in the window —
# it's permanently irrelevant, so drop it now.
while dq and nums[dq[-1]] < num:
dq.pop()
dq.append(i)
# The front of the deque holds the current window's max
# candidate — but only if it hasn't slid out of the window.
if dq[0] <= i - k:
dq.popleft()
if i >= k - 1:
result.append(nums[dq[0]])
return result
The most common implementation mistake with the variable-size window in particular isn’t the shrinking logic itself once it’s understood — it’s forgetting that the while loop for shrinking needs to run repeatedly, not just once, at each position of the right pointer. A single if instead of a while will shrink the window by at most one element per step even when multiple shrinks are actually valid, silently producing an answer that’s correct-looking but not actually optimal, and the bug is genuinely easy to miss in casual testing because it often still produces a valid answer — just not the best one.
Phase 5: Real-World Systems — Where This Shows Up Outside Interview Prep
Network rate limiting — a mechanism that caps how many requests a client can make in a given time period — is one of the most direct production instances of the sliding window pattern, specifically the fixed-size variant applied over time rather than over an array. A “100 requests per minute” rate limiter conceptually maintains a window covering the last 60 seconds of request timestamps, sliding continuously as time passes, and the same incremental-update insight from Phase 2 applies directly: rather than re-scanning the full request history on every incoming request, well-implemented rate limiters maintain a running count that updates incrementally as old requests fall outside the window and new ones enter it — a technique commonly called the sliding window log or sliding window counter algorithm in networking and API-gateway literature.
Streaming analytics and monitoring systems — think a dashboard showing “average CPU usage over the last 5 minutes” that updates continuously as new metric samples arrive — face exactly the same problem as the array-based version of this pattern, just with a continuous, unbounded stream instead of a fixed array. Recomputing the average from scratch over the full 5-minute window at every new sample would be wasteful in exactly the way Phase 1 describes; production monitoring systems instead maintain the running aggregate incrementally, adding the newest sample and subtracting whatever sample just aged out of the window.
TCP’s sliding window protocol, despite sharing the name, deserves a specific and important clarification: it solves flow control (how much unacknowledged data a sender can have in flight at once) rather than a subarray-computation problem, but the conceptual core — a window of “currently relevant” items that grows and shrinks as items enter (new data sent) and leave (acknowledgments received) — is recognizably the same underlying idea, which is a genuinely interesting case of the same abstract pattern independently proving useful in a completely different corner of computer science, decades before it became a staple algorithms-interview topic.
Log and anomaly-detection systems frequently need to answer questions like “have there been more than N error events in any 10-second span” — structurally identical to the shortest-subarray-meeting-a-condition problem from Phase 3.3, just applied to a live stream of log events with timestamps instead of a static array, using the exact same grow-and-shrink two-pointer logic to avoid re-scanning the recent event history on every new incoming log line.
Phase 6: AI-Era Relevance — Windows Inside Attention and Streaming Inference
The sliding window pattern connects to modern AI systems in a more literal way than most classic DSA topics, because “window” shows up as an actual, named architectural concept in transformer models, not just as a loose metaphor.
Sliding window attention is a real, widely-used technique for making transformer models efficient over long sequences. Standard self-attention requires every token to attend to every other token, which costs O(n²) in sequence length — a direct structural cousin of the brute-force O(n·k) problem from Phase 1, just in a different domain. Sliding window attention restricts each token to attending only to a fixed-size neighborhood of nearby tokens rather than the entire sequence, which is precisely the fixed-size window from Phase 3.2, applied to attention computation instead of array sums — trading some ability to directly relate very distant tokens for a dramatic and necessary reduction in computational cost, making very long context windows computationally viable at all. Models designed for long-context efficiency frequently combine sliding window attention with occasional full-attention layers, specifically to recover some of the long-range connectivity that a pure sliding window would otherwise sacrifice.
Streaming LLM inference and speech recognition systems face a directly analogous problem to the streaming monitoring case from Phase 5: audio or token input arrives continuously, and the system needs to maintain a relevant, bounded “window” of recent context to make decisions (the next predicted token, the next transcribed word) without re-processing the entire history from scratch at every single new input — the same incremental-update principle from Phase 2, now applied to real-time inference latency rather than array computation.
Context window management in agentic systems, touched on in earlier articles in this series, is worth reconnecting here specifically: an agent juggling a long-running task with a bounded context budget is, structurally, maintaining a variable-size window over its own conversation and action history — expanding as new information comes in, and needing a principled strategy (summarization, dropping old tool outputs, prioritizing recent and relevant turns) for what to evict when the window would otherwise overflow, echoing the exact grow-and-shrink logic from Phase 3.3, just with a considerably fuzzier, less mathematically clean “is this window still valid” condition than a simple sum comparison.
The throughline: “sliding window” in AI infrastructure isn’t a coincidental reuse of interview vocabulary — it’s the same underlying insight (nearby, overlapping windows share most of their content; exploit that instead of recomputing from scratch) independently proving necessary again at a completely different layer of the stack.
Phase 7: Advantages, Limitations, and Honest Trade-offs
Advantage — it turns O(n·k) or O(n²) brute-force solutions into O(n) solutions, often with no additional memory cost beyond a few tracking variables. This is the core payoff established in Phase 1, and it’s worth being precise about why it’s such a clean win: for the fixed-size and simple variable-size cases (3.2 and 3.3), the pattern requires no auxiliary data structure at all — just a running sum or count and two index variables — which means the algorithmic improvement comes essentially for free in terms of space complexity, a genuinely rare combination.
Limitation — the pattern only applies cleanly when the tracked property can be incrementally updated. As noted in 3.1, this is the actual gatekeeping condition, and it’s easy to misapply the pattern to a problem that superficially resembles a “contiguous subarray” question but where the relevant property (say, the median of the window, rather than its sum) can’t be cheaply updated by just accounting for one element entering and one leaving — the median specifically requires an auxiliary structure (like two balanced heaps) layered on top of the sliding window idea, and pretending a plain running-variable approach will handle it is a common, subtle mistake.
Trade-off — the monotonic deque extension (3.4) adds real implementation complexity in exchange for maintaining O(n) performance on max/min queries. This is a genuine complexity cost, not a free lunch: the deque-based solution is meaningfully harder to get right on a first attempt than the plain running-sum version, and teams building production log or metrics systems that need windowed max/min tracking have to weigh that added implementation and maintenance complexity against simply accepting a less optimal but simpler approach if the data volume doesn’t actually demand the optimization.
Limitation — sliding window fundamentally requires contiguity, and doesn’t generalize to problems about arbitrary (non-contiguous) subsequences. A question asking about the best non-contiguous subsequence satisfying some property is a structurally different problem — typically requiring dynamic programming instead — and recognizing that boundary (contiguous subarray versus arbitrary subsequence) is precisely the recognition skill from 3.1 that separates correctly identifying this pattern from forcing it onto a problem it doesn’t actually fit.
Phase 8: Career Impact — Why This Pattern Is a Recurring Interview Staple
Sliding window questions are asked constantly, at nearly every level of seniority, and it’s worth understanding what’s actually being evaluated: not whether you can recite the two-pointer template, but whether you can look at a brute-force O(n²) solution, correctly identify why it’s wasteful (redundant recomputation across overlapping windows), and derive the incremental-update optimization yourself, out loud, as part of the conversation — because that reasoning process transfers directly to real system design questions in a way that a memorized template doesn’t. Interviewers commonly escalate a base sliding-window question into the harder variants covered in this article specifically to see whether a candidate can distinguish “this needs a fixed window” from “this needs a variable window” from “this needs a monotonic deque,” rather than pattern-matching every subarray question to the same fixed template regardless of fit.
Beyond interviews, the underlying skill — recognizing when overlapping, incremental computation can replace repeated from-scratch computation — is a genuinely transferable systems-design instinct, and it shows up in the real-world contexts covered in Phase 5 and Phase 6: rate limiters, streaming analytics dashboards, and increasingly, the efficiency techniques underlying long-context AI inference. An engineer who’s internalized this pattern deeply tends to notice, in code review, when a colleague has written an accidentally-quadratic solution to what’s structurally a sliding window problem — a genuinely common and often costly class of production performance bug that’s invisible on small test inputs and only surfaces once data volume grows.
What to learn next, if this area is interesting: work through the variable-size window problems in the practice set below until the shrink-condition logic feels automatic rather than something you have to re-derive each time, and separately, study the monotonic stack pattern (a close cousin of the monotonic deque from 3.4) since it generalizes the same “discard permanently irrelevant candidates early” insight to a wider family of problems beyond windowed max/min.
Phase 9: Conclusion — The General Lesson Hiding Inside a Specific Trick
Sliding window is often taught as one item in a long list of named algorithmic patterns to memorize, and that framing undersells what’s actually going on. The real idea underneath it is much more general than arrays and subarrays: whenever a computation involves overlapping, evolving pieces of a larger structure — nearby windows in an array, recent events in a stream, a moving band of tokens a model attends over, unacknowledged packets in flight across a network — there is almost always an opportunity to stop treating each piece as an independent, from-scratch computation and start treating it as a small, incremental update to the piece that came just before it.
That reframing — from “recompute” to “update” — is the entire engineering content of the sliding window pattern, and it’s precisely why the same conceptual shape keeps reappearing across such different corners of computing, from TCP congestion control designed decades ago to sliding window attention inside the transformer architectures being trained today. Once you’ve genuinely internalized that reframing, rather than just the two-pointer template that implements it, you’ll start noticing “this is secretly a sliding window problem” in places far beyond the algorithms textbook — which is a much more durable and valuable thing to walk away with than the template alone.
10 Practice Problems
Work through these roughly in order — they’re sequenced to build from fixed-size windows through variable-size windows to the monotonic-deque extension.
- Maximum Sum Subarray of Size K — Given an array and an integer k, find the maximum sum of any contiguous subarray of size k. (Fixed-size window; the direct application of 3.2.)
- Average of All Subarrays of Size K — Given an array and an integer k, return the average of every contiguous subarray of size k. (Fixed-size window; practice applying the same incremental-update logic to a slightly different aggregate.)
- Longest Substring Without Repeating Characters — Given a string, find the length of the longest substring with no repeated characters. (Variable-size window; the shrink condition is “a duplicate character has entered the window.”)
- Minimum Size Subarray Sum — Given an array of positive integers and a target, find the length of the shortest contiguous subarray whose sum is greater than or equal to the target, or 0 if none exists. (Variable-size window; the direct application of 3.3.)
- Longest Substring with At Most K Distinct Characters — Given a string and an integer k, find the length of the longest substring containing at most k distinct characters. (Variable-size window; the shrink condition depends on a count of distinct characters rather than a sum.)
- Fruit Into Baskets — Given an array representing fruit types on trees in a row, find the length of the longest contiguous subarray containing at most two distinct fruit types. (A relabeled version of problem 5 — good for confirming you’re recognizing the underlying pattern rather than the surface wording.)
- Permutation in String — Given two strings, determine whether the second string contains a contiguous substring that is a permutation of the first. (Fixed-size window, where the window size equals the length of the first string, tracked using a character-frequency map instead of a simple sum.)
- Maximum Number of Vowels in a Substring of Given Length — Given a string and an integer k, find the maximum number of vowels in any substring of length k. (Fixed-size window; a direct warm-up variant of problem 1 using a count instead of a sum.)
- Sliding Window Maximum — Given an array and an integer k, return the maximum value in every contiguous window of size k as it slides across the array. (The monotonic deque technique from 3.4 — the hardest problem in this set, and worth returning to after the others feel comfortable.)
- Subarrays with K Different Integers — Given an array and an integer k, count the number of contiguous subarrays with exactly k distinct integers. (A genuinely trickier variable-size window problem, often solved by computing “at most k distinct” minus “at most k-1 distinct” — a good test of whether you can adapt the core pattern to a question that isn’t a direct min/max-length ask.)
Solutions
Try each problem yourself before reading its solution — the value of this pattern comes from deriving the shrink/grow condition yourself, not from reading it.
1. Maximum Sum Subarray of Size K
def max_sum_subarray(nums, k):
window_sum = sum(nums[:k])
best = window_sum
for i in range(k, len(nums)):
window_sum += nums[i] - nums[i - k]
best = max(best, window_sum)
return best
Compute the first window directly, then slide: add the entering element, subtract the leaving one. O(n) time, O(1) space.
2. Average of All Subarrays of Size K
def averages_of_subarrays(nums, k):
result = []
window_sum = sum(nums[:k])
result.append(window_sum / k)
for i in range(k, len(nums)):
window_sum += nums[i] - nums[i - k]
result.append(window_sum / k)
return result
Identical structure to problem 1 — only the final reported value (sum ÷ k instead of raw sum) differs, which is the point: recognizing the same fixed-size template under different wording.
3. Longest Substring Without Repeating Characters
def length_of_longest_substring(s):
last_seen = {}
left = 0
best = 0
for right, char in enumerate(s):
if char in last_seen and last_seen[char] >= left:
# Jump left past the previous occurrence instead of
# shrinking one step at a time — still O(n) overall.
left = last_seen[char] + 1
last_seen[char] = right
best = max(best, right - left + 1)
return best
The shrink condition is “the incoming character already exists inside the current window.” Rather than shrinking one element at a time, jump left directly past the duplicate’s last position — a common, valid optimization on the standard variable-window shrink loop.
4. Minimum Size Subarray Sum
def min_subarray_len(nums, target):
left = 0
window_sum = 0
best_length = float('inf')
for right in range(len(nums)):
window_sum += nums[right]
while window_sum >= target:
best_length = min(best_length, right - left + 1)
window_sum -= nums[left]
left += 1
return best_length if best_length != float('inf') else 0
This is the worked example from Phase 4 — grow with right, shrink with left as long as the window stays valid, recording the shortest valid length at each successful shrink.
5. Longest Substring with At Most K Distinct Characters
from collections import defaultdict
def longest_substring_k_distinct(s, k):
counts = defaultdict(int)
left = 0
best = 0
for right, char in enumerate(s):
counts[char] += 1
while len(counts) > k:
counts[s[left]] -= 1
if counts[s[left]] == 0:
del counts[s[left]]
left += 1
best = max(best, right - left + 1)
return best
The shrink condition swaps from “sum too large” to “too many distinct characters” — same grow/shrink skeleton as problem 4, different validity check.
6. Fruit Into Baskets
def total_fruit(fruits):
return longest_substring_k_distinct(fruits, 2)
Exactly problem 5 with k fixed at 2 — confirms the two problems are the same pattern under different wording.
7. Permutation in String
from collections import Counter
def check_inclusion(s1, s2):
need = Counter(s1)
window = Counter(s2[:len(s1)])
if window == need:
return True
for i in range(len(s1), len(s2)):
window[s2[i]] += 1
left_char = s2[i - len(s1)]
window[left_char] -= 1
if window[left_char] == 0:
del window[left_char]
if window == need:
return True
return False
Fixed-size window (size = len(s1)), tracked with a character-frequency counter instead of a numeric sum. Sliding still costs O(1) amortized per step since only one character enters and leaves at a time.
8. Maximum Number of Vowels in a Substring of Given Length
def max_vowels(s, k):
vowels = set('aeiou')
count = sum(1 for c in s[:k] if c in vowels)
best = count
for i in range(k, len(s)):
count += (s[i] in vowels) - (s[i - k] in vowels)
best = max(best, count)
return best
Same fixed-size template as problem 1, with a boolean “is this a vowel” check standing in for a raw numeric value.
9. Sliding Window Maximum
from collections import deque
def max_sliding_window(nums, k):
dq = deque() # stores indices, values decreasing left to right
result = []
for i, num in enumerate(nums):
while dq and nums[dq[-1]] < num:
dq.pop()
dq.append(i)
if dq[0] <= i - k:
dq.popleft()
if i >= k - 1:
result.append(nums[dq[0]])
return result
This is the monotonic deque from Phase 3.4 — each index enters and leaves the deque at most once, keeping the whole algorithm O(n) despite answering a max-query at every window position.
10. Subarrays with K Different Integers
def subarrays_with_k_distinct(nums, k):
def at_most_k_distinct(k):
if k < 0:
return 0
counts = defaultdict(int)
left = 0
total = 0
for right, num in enumerate(nums):
counts[num] += 1
while len(counts) > k:
counts[nums[left]] -= 1
if counts[nums[left]] == 0:
del counts[nums[left]]
left += 1
# Every subarray ending at `right` and starting at any
# index from left..right has at most k distinct values —
# that's (right - left + 1) valid subarrays ending here.
total += right - left + 1
return total
return at_most_k_distinct(k) - at_most_k_distinct(k - 1)
The “exactly k” count is derived as “at most k” minus “at most k-1” — both computed with the same variable-window helper from problem 5’s pattern. The key insight enabling the count-in-one-pass trick is that every window [left, right] with at most k distinct values contributes right - left + 1 valid subarrays (one for each possible start point from left to right), not just one.
