Sliding Window
Expanding and shrinking a window
The standard loop, and why a nested while inside a for is still linear.
Key idea
What a window is
A window is a contiguous stretch of the input described by two indexes, left and right. Unlike the converging pointers of Unit 2, both move in the same direction and neither ever goes backward.
The window carries state describing its contents: a sum, a set of what is inside, a count map. The whole technique is keeping that state correct as elements enter on the right and leave on the left.
Why it works
The standard shape
Nearly every variable window is this loop. Expand unconditionally, then shrink while the window is illegal, then record.
The sentence that makes it work: at the point where you record, the window from left to right is always legal. Everything else is machinery to keep that true.
Tip
The size of the window
With left and right both inclusive, the window holds right - left + 1 elements. The stray plus one is the single most common off-by-one in this pattern.
If you prefer half-open bounds where right is one past the end, the size is just right - left. Either convention is fine. Mixing them inside one function is not.
Cost
Why the nested loop is not quadratic
A while inside a for looks like O(n squared) and is O(n) here. The reason is the same total-work argument from the last two units: left only ever increases, and it can increase at most n times across the entire run of the outer loop.
So the outer loop does n steps, the inner loop does at most n steps in total, and the whole thing is O(n). Being able to say this out loud matters, because an interviewer who sees a nested loop will ask.
Gotcha
The shrink loop needs a floor
The left <= right guard stops the window from inverting when a single element already breaks the rule. Without it, a value larger than the limit sends left past right and the recorded size goes negative.
Whether you need the guard depends on the problem. If a single element can be illegal on its own, you need it. If the rule can always be satisfied by a one-element window, you do not. Decide which case you are in rather than adding the guard by reflex.
Edge cases
This particular loop needs non-negative values
Shrinking from the left only helps if removing an element can reduce the total. With negative values in the input that is no longer true, so the shrink loop can stop too early and the answer is wrong.
Sliding windows assume the quantity behaves monotonically as the window grows. When it does not, the problem usually wants prefix sums with a hash map instead. Checking that assumption is part of choosing the pattern.
The real question
The mechanics above are fixed. What changes between problems is the state: what the window remembers, and what makes it illegal. For the problem below, decide those two things first, then drop them into this loop.
Trace the window
Run the loop above on [2, 1, 5, 1, 3, 2] with a limit of 8. After each expansion and any shrinking, give the window total, left, and the window size. The first three steps are done for you to check against; fill in the rest.
This activity type is not wired up yet.
Window drills
Three variations on the same loop. max_sum_of_k returns the largest sum of any k consecutive values using a rolling total, not a fresh sum per window. longest_at_most_two_distinct returns the length of the longest stretch containing at most two distinct characters. count_windows_summing_to counts how many stretches of non-negative values sum to exactly the target.
Tests
print(max_sum_of_k([2, 1, 5, 1, 3, 2], 3), max_sum_of_k([1, 2], 5))
print(longest_at_most_two_distinct("eceba"), longest_at_most_two_distinct("aaaa"))
print(count_windows_summing_to([1, 2, 3], 3), count_windows_summing_to([0, 0, 3], 3))Output
Run the tests when you are ready.
Longest Substring Without Repeating Characters
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.