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.](https://ik.imagekit.io/9osfw19dn/cheatsheets/concepts/sliding-window-and-two-pointer-scanning_E7a8lAH1e.png?tr=w-1360,q-95)
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 andO(1)space. -
Expand-and-contract window: move
rightuntil valid, then advanceleftwhile validity remains; track the shortest valid interval. -
Frequency map with
Mapor 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, preservingO(n)total time. -
Define validity explicitly:
distinctCount >= korcounts.size === requiredTypes; distinguish “at least” from “exactly.” -
Use
isalnum()or an equivalent predicate plustoLowerCase()for normalization; decide whether Unicode letters and digits are required. -
Return
-1for 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 hiddenO(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
- Shortest Contiguous Team From Each Start Covering K Distinct SubjectsWalmart Labs · Software Engineer · Online Assessment · medium
- Palindrome Check That Ignores Spaces, Symbols and Letter CaseWalmart Labs · Software Engineer · Onsite · easy
- Shortest Talent-Covering Team Starting At Each IndexWalmart Labs · Software Engineer · Technical Screen · hard
Related concepts
- String And Sliding Window AlgorithmsCoding & Algorithms
- Sliding Window Frequency MapsCoding & Algorithms
- Sliding Window, Binary Search, and Prefix ReasoningCoding & Algorithms
- Arrays, Intervals, Sliding Windows, And Prefix SumsCoding & Algorithms
- Sweep Line And Sliding Window OptimizationCoding & Algorithms
- Arrays, Strings, Hash Maps, And Sliding WindowsCoding & Algorithms