Micro-questions over the sliding window pattern. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.


A. Why it exists

1. What does the naive approach cost, and why is that wasteful?

Answer

— each query recomputes the same sliding sums over and over from scratch.

2. State the fix.

Answer

Compute the first window’s sum once, then slide it one step at a time, adding the new element and subtracting the one that falls out.

3. Why is the result ?

Answer

Each element enters and leaves the window at most once.

4. What does Codility call this?

Answer

The caterpillar method — same technique, a front and back index each only ever moving forward.


B. The vocabulary

5. Define a sliding window.

Answer

A contiguous subarray or substring that moves one element at a time, maintaining a fixed or variable size — a camera panning across a scene.

6. Fixed-size versus variable-size?

Answer

Fixed: size is constant; slide by removing the element that falls out the back and adding the one entering the front. Variable: the window grows and shrinks depending on a condition.

7. Give an example of each.

Answer

Fixed: a 3-day moving average. Variable: longest substring without repeating characters.


C. Fixed-size windows

8. Write the update step.

Answer
window_sum += nums[i] - nums[i - k]   # add new, drop oldest — O(1)

9. Trace [2,1,5,1,3,2], .

Answer

[2,1,5] = 8 → [1,5,1] = 7 → [5,1,3] = 9 (best) → [1,3,2] = 6.

10. Does it still work with negative numbers?

Answer

Yes. new_sum = old_sum - nums[i-k] + nums[i] is valid regardless of sign — the algorithm does not assume positivity.


D. Variable-size windows

11. Describe the longest-substring-without-repeats loop.

Answer

Expand the right edge each iteration; while the constraint is violated, shrink from the left, removing characters from seen. Record the best length each step.

12. Why is it despite the nested while inside the for?

Answer

Each character is added to seen at most once and removed at most once across the whole run — total operations bounded by , not .

13. What familiar analysis is that?

Answer

The same amortised argument as dynamic array resizing — the loop looks nested, but the total work across the run is linear.

14. Describe minimum window substring.

Answer

Track a need counter of required characters and a missing count. Expand right; whenever missing == 0 the window is valid, so record it and shrink from the left until it stops being valid.


E. When the aggregate is not invertible

15. Why can sliding window maximum not use add-one-drop-one?

Answer

Max is not invertible. Knowing the old max and the element that left tells you nothing about the new max if the departing element was the max.

16. What structure does it use instead?

Answer

A monotonic deque storing indices with decreasing values.

17. Describe its two while loops.

Answer
  1. Pop from the front any index that has fallen out of the window.
  2. Pop from the back any index whose value is the incoming one — it can never be the max again.

18. Where is the answer at each step?

Answer

nums[dq[0]] — the front of the deque, once the window is full.


F. Trade-offs

19. What is the fixed-size window’s precondition?

Answer

An invertible aggregate. Sum and count work; max, min and median do not.

20. When should you use prefix sums instead?

Answer

When the problem requires checking every possible window — e.g. “find all subarrays with sum equals ”. A window cannot help there, especially with negative values, because shrinking is no longer monotone.

21. Summarise the pattern in one sentence.

Answer

Maintain a contiguous span and update it incrementally as it moves — linear because every element enters and leaves exactly once, however nested the loops look.


Scorecard

PassDateGot itCloseBlankQuestions missed
1
2
3

↑ Back to LeetCode Patterns — University-Style Teaching Notes