Coding

Two Pointers & Sliding Window

Two pointers and sliding window reduce O(n²) brute-force to O(n). These patterns are foundational for array and string optimization and appear in almost every company's screening rounds.

Practice with AI Feedback — Free AI Mock Interview

Sample Questions & Strong Answers

Valid Palindrome — check if string is a palindrome (ignoring non-alphanumeric).

Two pointers from each end. Skip non-alphanumeric characters. Compare lowercased characters. If mismatch, return false. If pointers cross, return true. Time O(n), Space O(1).

💡

Pro tip: Do the cleanup (alphanumeric filter, lowercase) in the comparison step, not by creating a new string — that costs O(n) extra space. Amazon, Meta, Microsoft.

Remove Duplicates from Sorted Array (in-place).

Two pointers: slow pointer tracks position of last unique element. Fast pointer scans forward. When fast finds a new value (nums[fast] ≠ nums[slow]), increment slow and copy. Return slow+1. Time O(n), Space O(1).

💡

Pro tip: The 'write pointer' pattern (slow) appears in many in-place modification problems. Amazon, Google, Microsoft.

Minimum Size Subarray Sum — smallest contiguous subarray with sum ≥ s.

Variable sliding window: expand right pointer until sum ≥ s, then shrink left pointer as long as sum ≥ s, recording minimum length. Time O(n), Space O(1). If no valid window, return 0.

💡

Pro tip: Expand first, then shrink — this guarantees you find the minimum window for each right position. Amazon, Google.

Longest Repeating Character Replacement — longest substring with up to k replacements.

Sliding window: track max frequency character in window. If (window length − maxFreq) > k, shrink from left. Track max window length. Time O(n), Space O(1).

💡

Pro tip: Key insight: we only need to fill slots that aren't the dominant character. maxFreq never decreases (we only care about larger windows). Google, Amazon.

Permutation in String — does s2 contain a permutation of s1?

Fixed sliding window of size s1.length. Use frequency arrays of size 26. Compare arrays. On slide: decrement outgoing character, increment incoming. If arrays match, return true. Time O(n), Space O(1).

💡

Pro tip: Comparing two frequency arrays of size 26 is O(1) per window slide. Amazon, Microsoft, Google.

Find All Anagrams in String — return all start indices of anagrams of p in s.

Same as Permutation in String but collect all matching window start indices. Fixed window of p.length, slide across s. Time O(n), Space O(1).

💡

Pro tip: Extend the Permutation in String solution — once you have the sliding window, storing indices is trivial. Meta, Amazon, Google.

Longest Substring with At Most K Distinct Characters.

Variable sliding window: expand right, add to frequency map. When distinct count > k, shrink left (decrement freq, remove from map if 0). Track max window. Time O(n), Space O(k).

💡

Pro tip: This generalizes Longest Substring Without Repeating Characters (k=1 distinct per window, or rather no repeats). Amazon, Google — medium.

Subarray Product Less Than K.

Sliding window: maintain running product. If product ≥ k, shrink left. Count subarrays ending at right: right − left + 1 (each ending at right with a valid left is a valid subarray). Time O(n), Space O(1).

💡

Pro tip: Count of valid subarrays added per right position = (right − left + 1). Handle k ≤ 1 edge case (no valid subarray possible). Amazon, Google.

3Sum Closest — find triplet sum closest to target.

Sort array. Fix one element, use two pointers for remaining two. Compute sum, update closest if |sum−target| < current best. Move pointers: if sum < target, left++; if sum > target, right−−; if equal, return target. Time O(n²), Space O(1).

💡

Pro tip: Sorting + two pointers is the canonical approach. Track best absolute difference. Google, Amazon.

Fruit Into Baskets (Longest Subarray with At Most 2 Distinct).

Variable sliding window with frequency map. Expand right: add fruit type. When more than 2 types, shrink left. Track max window length. Time O(n), Space O(1) — only 3 distinct types possible in map.

💡

Pro tip: This is exactly 'Longest Substring with At Most K Distinct Characters' with k=2 in disguise. Recognize the pattern. Google, Amazon.

Expert tips

Fixed sliding window: window size is constant. Variable sliding window: expand until invalid, then shrink until valid.

Two pointers on sorted arrays: reduce 2D search space from O(n²) to O(n) by moving pointers based on sum comparison.

Track window state efficiently: frequency maps, running sums, or monotonic structures — avoid O(k) per slide.

Variable window problems: expand right unconditionally, shrink left while invariant is violated.

Two Pointers & Sliding Window FAQ

Look for: 'contiguous subarray/substring,' 'window of size k,' 'longest/shortest subarray satisfying a condition,' or 'substring containing all characters of a set.' The key indicator is that brute-force would check O(n²) subarrays but the optimal condition allows a two-pointer approach without revisiting elements.

Fixed window: window size k is given. Track state as you slide (decrement outgoing element, increment incoming). Variable window: no fixed size. Expand right freely, shrink left when the window violates a constraint, record result before shrinking or after expanding. The constraint determines when to shrink.

Two pointers are more general: they can start from opposite ends (palindrome, 3Sum), move at different speeds (fast/slow for cycles), or both move right (sliding window). Sliding window is a specific two-pointer pattern where both pointers only move right and the 'window' between them is the subarray of interest.

When the right pointer is at index r and the window's valid left boundary is l, there are r − l + 1 valid subarrays ending at r (all windows [l..r], [l+1..r], ..., [r..r]). Add this count at each r. This technique counts all valid subarrays in O(n) total.

Practice Two Pointers & Sliding Window with real-time AI.

Stop reading sample answers and start practicing. Get personalized feedback on structure, delivery, and depth — every time.

Start Free Practice AI Mock Interview

Free plan available · No credit card needed · Cancel anytime