Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Count contiguous segments of exactly m squares whose values sum to d. Recomputing each window's sum from scratch is O(n·m). The interview answer is a fixed-size sliding window: keep a running sum, add the entering element and subtract the one that left, and count windows equal to d. That is one pass, O(n).
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you recognise a fixed-size sliding window and update a running sum in O(1) per step instead of re-summing each block, and whether you handle the off-by-one bookkeeping (when the window is full, which index leaves).
Where candidates slip
Re-summing every window in an inner loop (O(n·m)), or sliding incorrectly by subtracting the wrong departing index, which quietly poisons all later sums.
How to stand out
State the window is fixed-size, slide with one add and one subtract, and explain the two guards: count only when the window is full and subtract exactly s[i − m].
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewAggregate over contiguous blocksIs the block length fixed?NoYesExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Brute Force — Re-sum Every Window
1Hint 1Explore hintHide hint
There are n − m + 1 starting positions for a window of size m. For each, you could add up its m elements and compare to d.
2Hint 2Explore hintHide hint
Outer loop over start index i from 0 to n − m; inner loop sums s[i..i+m−1].
3Hint 3Explore hintHide hint
Increment a counter whenever the inner sum equals d. Correct, but every window re-adds m values from scratch.
A · Core idea
The most direct reading: enumerate every contiguous block of length m and total it up.
Why this is the natural starting point. The problem literally asks 'how many length-m segments sum to d', so the obvious code mirrors the question — pick each start position, sum the m elements there, compare to d. There are n − m + 1 valid start positions, and for each we run a small inner loop of m additions.
Where the waste is. Consecutive windows overlap in m − 1 elements. When the window slides from start i to start i + 1, the brute force throws away the entire previous sum and recomputes from scratch, re-adding the m − 1 elements both windows share. That repeated work is exactly the m factor in O(n·m).
Why it still passes here, and why you replace it. With the given constraints (n ≤ 100, m ≤ 12) this is at most ~1,200 operations — instant. But the interviewer wants to see that you notice the overlap and remove it. State the brute force, name the repeated summing, then slide.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
s = [1, 2, 1, 3, 2], d = 3, m = 2Interactive diagram
Every window summed independently
start 0Overlapping windows re-add their shared elements — the inefficiency the slide removes.
2C · Code with teaching comments
Reference implementation previewpublic int birthday(int[] s, int d, int m) { int count = 0; for (int i = 0; i + m <= s.length; i++) { int sum = 0; for (int j = i; j < i + m; j++) {Explore the full codeHide the full code
D · Why it works and complexityO(n·m) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
Adjacent windows share m − 1 elements. The brute force pays for that overlap every step; the sliding window reuses it. Spotting the overlap is the whole optimisation.
ComplexityO(n·m) time, O(1) space — There are about n − m + 1 windows and each inner sum costs m additions, giving O(n·m). Only a counter and a sum are stored, so O(1) space.
E · Edge cases and pitfalls3Looping i while i < length instead of i + m <= length — the last windows overrun the array.Explore edge casesHide edge cases
Pitfalls
- Looping i while i < length instead of i + m <= length — the last windows overrun the array.
- Re-summing the whole window every step — the O(m) factor you should eliminate.
- Forgetting overlapping windows both count — they are distinct segments.
Approach 2 of 2 · Optimal
Fixed-Size Sliding Window — Running Sum (Optimal)
1Hint 1Explore hintHide hint
Instead of re-summing, maintain one running total. When the window slides right by one, add the new element and subtract the element that just left.
2Hint 2Explore hintHide hint
The element leaving the window when you arrive at index i is the one m positions back: s[i − m].
3Hint 3Explore hintHide hint
Only test the sum once the window holds m elements — that first happens at index m − 1. Count each full window whose sum equals d.
A · Core idea
Carry one running sum and update it in constant time as the window slides.
The core move. Picture a window of width m sitting over the array. To advance it one step to the right, you do not rebuild the sum — you adjust it. The element entering on the right (s[i]) gets added; the element that just fell off the left (s[i − m]) gets subtracted. The m − 1 elements in the middle are untouched, which is precisely the overlap the brute force kept recomputing.
Filling the window first. For the first m indices (i from 0 to m − 1) the window is still filling up, so we only add. The subtraction kicks in starting at i = m, where s[i − m] = s[0] is the first element to leave. The guard if (i >= m) expresses exactly that.
When to count. The window is full for the first time when i reaches m − 1. From that index onward, every position represents one complete length-m window, so we compare the running sum to d and increment when they match. The guard i >= m - 1 prevents scoring half-built windows at the very start.
Why the departing index must be exact. The element leaving is s[i − m] — not s[i − m + 1] or s[i − m − 1]. Subtracting the wrong index corrupts the running sum, and because the error carries forward, every later window is wrong too. This single index is where most sliding-window bugs live.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
s = [1, 2, 1, 3, 2], d = 3, m = 2Array state
i=1
window [1,2] sum = 3 == d → count = 1
2C · Code with teaching comments
D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
A fixed window is a sum you edit, not rebuild: +s[i] − s[i−m] per step. The two guards (i >= m to start subtracting, i >= m − 1 to start counting) are just bookkeeping for when the window first fills and first loses an element.
ComplexityO(n) time, O(1) space — Each index is added once and subtracted at most once — two O(1) operations per element — so O(n) total. A single running sum and counter give O(1) space.
E · Edge cases and pitfalls6s = [4], d = 4, m = 1 — i=0: add 4, i >= m? no. i >= m−1 (0 ≥ 0) and sum == 4 → count = 1. Single-element windows work.Explore edge casesHide edge cases
Edge cases handled
s = [4], d = 4, m = 1i=0: add 4, i >= m? no. i >= m−1 (0 ≥ 0) and sum == 4 → count = 1. Single-element windows work.s = [2, 2, 1, 3, 2], d = 4, m = 4First full window at i=3: 2+2+1+3 = 8 ≠ 4; next 2+1+3+2 = 8 ≠ 4 → 0. Large window, no match.s = [1, 1], d = 3, m = 3m > n, so i never reaches m − 1 with a full window → count stays 0.
Pitfalls
- Subtracting s[i − m + 1] instead of s[i − m] — the off-by-one that poisons all later sums.
- Counting before the window is full — guard with i >= m − 1.
- Resetting windowSum inside the loop instead of editing it — that turns the slide back into O(n·m).
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int birthday(int[] s, int d, int m) { int windowSum = 0; int count = 0; for (int i = 0; i < s.length; i++) { windowSum += s[i]; // element entering on the rightExplore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Rebuilding the sum every window
Re-adding all m elements per window is O(n·m). The whole point of a fixed window is to reuse the overlap.
Explore the code comparisonHide the code comparison
Rebuilding the sum every window
Re-adding all m elements per window is O(n·m). The whole point of a fixed window is to reuse the overlap.
Don't write this
for i in range(len(s) - m + 1):
if sum(s[i:i + m]) == d: # O(m) every iteration
count += 1Write this instead
for i in range(len(s)):
window_sum += s[i]
if i >= m:
window_sum -= s[i - m] # O(1) slide2Wrong departing index
The element leaving the window is s[i − m]. Using s[i − m + 1] subtracts an element still inside the window, and the error compounds forever.
Explore the code comparisonHide the code comparison
Wrong departing index
The element leaving the window is s[i − m]. Using s[i − m + 1] subtracts an element still inside the window, and the error compounds forever.
Don't write this
windowSum -= s[i - m + 1]; // still inside the windowWrite this instead
windowSum -= s[i - m]; // the element that actually left3Counting a half-full window
Before index m − 1 the window holds fewer than m elements; testing its sum scores invalid short segments.
Explore the code comparisonHide the code comparison
Counting a half-full window
Before index m − 1 the window holds fewer than m elements; testing its sum scores invalid short segments.
Don't write this
if (windowSum == d) count++; // fires on partial windows tooWrite this instead
if (i >= m - 1 && windowSum == d) count++; // only full windowsRevise
Carry the pattern into the interview
Pattern to remember
Fixed-size sliding window with a running sum
Code pattern to memorize
windowSum = 0; count = 0
for i in range(n):
windowSum += s[i]
if i >= m: windowSum -= s[i - m] # element leaving the window
if i >= m - 1 and windowSum == d: count += 1
return countRules to remember
- 1The window size is fixed at m — this is not a variable-size window, so never grow or shrink it conditionally.
- 2Each step does one add and one subtract: add
s[i]entering on the right, subtracts[i - m]that fell off the left. That is what makes it O(n) instead of O(n·m). - 3Only start counting once the window is full — guard with
i >= m - 1, otherwise you score partial windows. - 4Subtract the correct departing index
s[i - m], nots[i - m + 1]. Off-by-one here silently corrupts every later sum. - 5Segments overlap —
[1,2]and[2,1]are different windows sharing an element. Count every full-length window, do not skip.
Use this pattern when
- Count or aggregate over every contiguous block of a FIXED length
- A running statistic (sum, max, average) over a sliding span
- Re-summing each window from scratch is the naive O(n·k) you want to beat
- The window length is given, not something you optimise
Choose another pattern when
- Window size varies with a condition → variable-size two-pointer window
- You need sums of ALL subarrays, any length → prefix sums or different DP
- Order doesn't matter / you can sort → not a window problem
- You need the segments themselves, not just a count → store indices
Interview takeaway
Fixed-size windows turn an O(n·m) re-sum into an O(n) slide: add the new element, drop the old one. Lily's Chocolate is the textbook case — once you see 'every block of exactly m', reach for the running window before writing a nested loop.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternFixed-size sliding window. When you aggregate over every contiguous block of a known length, maintain one running statistic and update it in O(1) per step — add the entering element, subtract the leaving one. Recurs in Maximum Average Subarray, Sliding Window Maximum, and any 'every window of size k' question.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Maximum Average Subarray IComing soonSame fixed-size window, track the max running sum instead of counting matches.
- Minimum Size Subarray SumVariable-size window — grow and shrink to hit a target sum.
- Subarray Sum Equals KComing soonAny-length subarrays — switch to prefix sums plus a hash map.