Interview conceptCoding & Algorithms

Sliding Window And Two-Pointer Scanning

Asked of: Software Engineer

Last updated

Five-frame sliding-window trace over [a, b, a, c, b], showing right-pointer expansion, left-pointer contraction, frequency counts, validity, and the best length-3 window.

What's being tested

These questions test sliding-window and two-pointer scanning over strings and contiguous arrays. You must maintain a precise window invariant, update counts as pointers move, and explain why each element enters and leaves the window at most once. The interviewer is also checking edge-case handling, especially filtering characters, duplicate counts, impossible windows, and O(n) complexity.

Patterns & templates

  • Opposite-end pointers for palindrome checks: advance inward, skip non-alphanumeric characters, compare normalized characters; O(n) time and O(1) space.

  • Expand-and-contract window: move right until valid, then advance left while validity remains; track the shortest valid interval.

  • Frequency map with Map or dictionary: increment on expansion, decrement on contraction, and delete zero-count keys to track distinct values.

  • For every starting index, use a left-to-right window and record the first valid right; avoid restarting scans, preserving O(n) total time.

  • Define validity explicitly: distinctCount >= k or counts.size === requiredTypes; distinguish “at least” from “exactly.”

  • Use isalnum() or an equivalent predicate plus toLowerCase() for normalization; decide whether Unicode letters and digits are required.

  • Return -1 for an impossible window, and handle empty input, k <= 0, k > number of types, and single-element inputs explicitly.

Common pitfalls

Pitfall: Removing a character from the frequency map without decrementing first can make the distinct-count invariant incorrect.

Pitfall: Claiming O(n) while copying or rescanning each candidate window creates hidden O(n²) behavior.

Pitfall: Confusing one global minimum window with the shortest valid window required from every starting index.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.

Practice questions

Related concepts