Two Pointers & Sliding Window

Two pointers and sliding window are the two most reliable ways to turn a brute-force O(n²) or O(n³) into a clean O(n). They aren't separate "data structures" — they're a way of *moving through* an array (or string, or linked list) so cleverly that each element gets touched a constant number of times. Once you spot the pattern, half of the medium LeetCode problems collapse into a few lines.

What These Techniques Actually Are

Two pointers — instead of nested loops, use two index variables that walk through the data in a coordinated way. The pointers can:

• start at opposite ends and move *toward* each other (converging),
• start at the same end and move in the *same direction* at different speeds (slow/fast),
• one fixed, the other scanning.

Sliding window — a special case: the two pointers always satisfy \left ≤ right\ and define a contiguous window \arr[left..right]\. You incrementally add the element entering the right side and remove the element leaving the left side — never recomputing the whole window from scratch.

Both ideas exploit that the array has order or contiguity, so once you've moved a pointer forward, you rarely need to move it back. Total work: O(n).

Daily Mental Model

• Two pointers, opposite ends: "Should I shrink from the left or the right?" Two-Sum on a sorted array, container with most water, palindrome check.
• Two pointers, same direction: "Read pointer scans, write pointer fills." Remove duplicates in-place, move zeroes, partitioning.
• Fast/slow: "One moves twice as fast as the other." Cycle detection, find middle of linked list.
• Sliding window: "What's the longest / shortest contiguous segment satisfying X?" The right pointer expands, the left shrinks when a constraint breaks.

Beginner Mistakes to Skip

1. Trying to use two pointers on an *unsorted* array for problems that require order. Two-sum on unsorted data → use a hash map, not two pointers. 2. Using two pointers when the answer is non-contiguous. "Longest *increasing* subsequence" isn't sliding window — it's DP. Sliding window only works for *contiguous* segments. 3. Forgetting to shrink the window. \while (window invalid) left++;\ — without it, the right pointer races off and the window grows forever. 4. Off-by-one in window size. Window length is \right - left + 1\, not \right - left\. 5. Resetting the left pointer to 0 after each right move. That's nested-loop O(n²) again. The whole point is left never moves backward. 6. Updating the answer in the wrong place. For *longest* problems, update *after* the inner shrink loop. For *shortest*, update *inside* the shrink loop.

Intermediate: Two Pointers — Opposite Direction

Pointers start at \left = 0\ and \right = n - 1\, move toward each other.

\\\`js // Two-Sum on a SORTED array function twoSum(arr, target) { let l = 0, r = arr.length - 1; while (l < r) { const s = arr[l] + arr[r]; if (s === target) return [l, r]; if (s < target) l++; // need bigger sum → move left up else r--; // need smaller → move right down } return [-1, -1]; } \\\`

Classic problems:

• Valid Palindrome — compare \s[l]\ and \s[r]\, move inward.
• Container With Most Water — area is \min(h[l], h[r]) * (r - l)\. Move the *shorter* line.
• 3Sum — sort, fix one element, two-pointer the rest.
• Trapping Rain Water — track \maxLeft\ and \maxRight\ while two-pointering.

The pattern works because sortedness gives you monotonicity: if the current sum is too small, you *know* moving the right pointer down won't help — only moving the left up can.

Intermediate: Two Pointers — Same Direction (Read/Write)

Both pointers march forward. The "write" pointer trails the "read" pointer, only advancing when the read finds something worth keeping.

\\\`js // Remove duplicates from sorted array, in-place function removeDuplicates(arr) { if (arr.length === 0) return 0; let write = 1; for (let read = 1; read < arr.length; read++) { if (arr[read] !== arr[read - 1]) { arr[write++] = arr[read]; } } return write; } \\\`

Classic problems: Move Zeroes, Remove Element, partition step of quicksort, merging two sorted arrays into one with a third write pointer.

Intermediate: Fast / Slow (Floyd's Cycle Detection)

The slow pointer moves 1 step, the fast pointer moves 2. If there's a cycle, they're guaranteed to meet inside it.

\\\`js function hasCycle(head) { let slow = head, fast = head; while (fast && fast.next) { slow = slow.next; fast = fast.next.next; if (slow === fast) return true; } return false; } \\\`

Bonus uses:

• Find middle of linked list — when fast hits the end, slow is at the middle.
• Find cycle start — once they meet, reset one pointer to head, advance both at speed 1; they meet at the cycle's entry.
• Happy Number — treat the digit-square sequence as a linked list, detect cycles.

Advanced: Sliding Window — Fixed Size

Window size is a constant \k\. Slide one position at a time.

\\\`js // Maximum sum of any subarray of size k function maxSumK(arr, k) { let sum = 0; for (let i = 0; i < k; i++) sum += arr[i]; let best = sum; for (let i = k; i < arr.length; i++) { sum += arr[i] - arr[i - k]; // add new, remove old best = Math.max(best, sum); } return best; } \\\`

The trick: don't recompute the sum — just add the entering element and subtract the leaving one. O(n).

Advanced: Sliding Window — Variable Size

Right pointer expands, left pointer shrinks when a constraint breaks. Same skeleton, two flavours.

For maximum window length (constraint must stay valid):

\\\` left = 0 for right in 0..n-1: add arr[right] to window while window is INVALID: remove arr[left] from window; left++ best = max(best, right - left + 1) \\\`

For minimum window length (constraint must be reached):

\\\` left = 0 for right in 0..n-1: add arr[right] to window while window is VALID: // note: VALID, not invalid best = min(best, right - left + 1) remove arr[left] from window; left++ \\\`

Advanced: Sliding Window with a Hash Map

For "longest substring with property X over characters", maintain a frequency map of the current window.

\\\`js // Longest substring without repeating characters function longestUnique(s) { const seen = new Map(); // char → most recent index let left = 0, best = 0; for (let r = 0; r < s.length; r++) { if (seen.has(s[r]) && seen.get(s[r]) >= left) { left = seen.get(s[r]) + 1; // jump past the duplicate } seen.set(s[r], r); best = Math.max(best, r - left + 1); } return best; } \\\`

Other classics:

• Minimum Window Substring — track required-char counts, shrink when all are covered.
• Longest Substring with At Most K Distinct Characters — shrink when distinct > k.
• Find All Anagrams — fixed-size window, frequency-match.
• Permutation in String — same idea, fixed window.

Advanced: Why Sliding Window Is Genuinely O(n)

Looks like O(n²) because of the inner \while\, but isn't:

• Right pointer moves from 0 to n − 1 → exactly n increments total.
• Left pointer also moves from 0 to at most n − 1 → at most n increments across the entire algorithm.
• Each element is added to the window once and removed at most once.

Total: 2n = O(n). The key: left never moves backward. Once you internalise this, sliding-window problems stop being scary.

Advanced: Pattern Recognition — When to Reach for What

Signals for two pointers:

• "Sorted array" + "find pair / triplet"
• "In-place" modification of an array
• "Linked list" + "cycle" or "middle"
• You need O(n) on data that has natural order

Signals for sliding window:

• "Subarray" or "substring" with a property
• "Maximum / minimum length of contiguous …"
• "At most k", "exactly k", "without repeating"
• Constraint applies to a contiguous range

Signals it's NOT sliding window:

• The answer is a non-contiguous subsequence (use DP).
• The constraint requires looking at the whole array (sometimes use prefix sums + hash map).

Advanced: Bonus — Monotonic Deque for Sliding-Window Maximum

A pure sliding-window approach can't compute the max in O(1) when the leaving element *was* the max — you'd need to re-scan. The trick: maintain a deque of indices in decreasing order of value.

\\\` for right in 0..n-1: while deque non-empty and arr[deque.back()] <= arr[right]: deque.popBack() deque.pushBack(right) if deque.front() <= right - k: deque.popFront() // out of window if right >= k - 1: result.push(arr[deque.front()]) \\\`

Each index enters and leaves the deque at most once → O(n).

Practice Path

1. Two-Sum II (sorted array) using opposite-direction two pointers. Then try Container With Most Water — same skeleton, just decide *which* pointer to move. 2. Move Zeroes in-place using same-direction two pointers (read/write). Verify O(1) extra space. 3. Find the longest substring without repeating characters with a sliding window + hash map. Trace it on \"abcabcbb"\ to confirm \left\ never moves backward. 4. Sliding-window maximum on \[1,3,-1,-3,5,3,6,7]\ with \k=3\ using a monotonic deque. Expected: \[3,3,5,5,6,7]\.