Stop Guessing: The 'Expand-Contract' Framework for Sliding Window

Originally published on LeetCopilot Blog

---

Left++? Right++? Stop randomly moving pointers. Learn the specific 'Expand vs. Contract' invariant that explains every sliding window problem.

Two pointers feel simple until the interviewer asks you to explain why you expand or contract at each step. This walkthrough shows how to present the expand–contract pattern with clear invariants, so you avoid silent pointer drift and wasted iterations.

TL;DR

• Topic: using two pointers that expand and contract to scan arrays or strings while preserving a target condition.
• Why it matters: interviews reward the invariant you maintain between pointers, not just moving left and right around.
• Core steps: initialize ends, decide the grow/shrink condition, update the invariant after each move, and stop on crossover.
• Common confusion: beginners move both pointers at once or forget to update the invariant before checking the answer bucket.
• What you’ll learn: narration cues, a traceable table, a safe code template, and preparation drills.

Beginner-Friendly Explanation: What Expand-Contract Means

• Expand: Widen the window (usually advance right) to gather more candidates until the condition is met.
• Contract: Shrink from left to restore the invariant (e.g., sum ≤ target, characters unique).
• Invariant: A promise that remains true after each move, such as “window sum is within target” or “characters are unique.” Without it, updates become guesswork.
• Compare with the decision guide in Sliding Window vs Two Pointers: When to Use Which.

Step-by-Step Learning Guidance

1) Declare the invariant out loud

Say: “I will maintain that the window sum never exceeds target.” This mirrors the framing in What to Do When You Recognize the Pattern But Still Can't Solve the Problem.

2) Expand deliberately

Move right while the invariant is preserved or until a violation is detected. Record how the tracked metric changes (sum, count, frequency).

3) Contract with purpose

When the invariant breaks, move left and undo the metric contributions until the promise is restored.

4) Check answers after fixes

Only capture answers once the invariant is valid. This prevents off-by-one captures noted in Sliding Window Debug Checklist for LeetCode Beginners.

5) Stop on crossover

When left passes right, reset or end depending on the problem (e.g., move both for sorted pair search).

Visualizable Example: Unique Substring Length

Index:   0 1 2 3 4
String:  a b c a b
Window: [a b c] violates after second 'a'
Action: contract from left until frequencies are valid → window becomes [b c a]

Seeing the window as a bracket helps you narrate exactly which character leaves during contraction.

Code Example: Expand-Contract Template

def longest_unique_substring(s):
    freq = {}
    left = 0
    best = 0
    for right, ch in enumerate(s):
        freq[ch] = freq.get(ch, 0) + 1
        while freq[ch] > 1:  # invariant broken
            freq[s[left]] -= 1
            left += 1
        best = max(best, right - left + 1)
    return best

This template expands with right, contracts with left, and updates the answer only when the invariant is satisfied.

Practical Preparation Strategies

• Narrate moves: Explain which pointer moves and why before typing; it reduces trial-and-error loops.
• Swap problems: Alternate between substring uniqueness and sorted two-sum to see how invariants change.
• Dry-run aloud: Trace 2–3 iterations on paper, then compare to your code’s printouts.
• Use assistive visuals: LeetCopilot can highlight the active window and show frequency maps so you notice invariant breaks sooner.

Common Mistakes to Avoid

Moving both pointers impulsively

Advancing left and right together often skips candidates. Move only one unless the algorithm requires synchronized motion (e.g., shrinking then immediately expanding).

Forgetting to undo state

When contracting, decrement counts or sums; otherwise the invariant appears broken even after the window shrinks.

Ignoring crossover

If left surpasses right, reset the window start instead of continuing with negative lengths.

Over-storing answers

Storing results before the invariant is restored captures invalid windows.

FAQ

• How do I know the invariant is correct? State the property the final answer must satisfy, then choose the simplest window promise that guarantees it.
• What should I practice first? Start with fixed-size windows, then move to variable windows with frequency maps.
• Is expand–contract always sliding window? Mostly, but sorted pair problems use contraction without tracking all interior elements.
• How should I talk through it in interviews? Describe the invariant, what triggers expansion, what triggers contraction, and when you record answers.

Conclusion

Mastering the expand–contract two pointers pattern is about preserving the invariant, narrating your moves, and stopping when the pointers cross. With deliberate dry runs and clear explanations, you can apply it confidently under interview pressure.

---

If you're looking for an AI assistant to help you master LeetCode patterns and prepare for coding interviews, check out LeetCopilot.