Two Pointers & Sliding Window: Turning O(n²) Scans into O(n)

In plain words

Imagine searching a sorted guest list for two names that together satisfy some condition — say, two people whose ages sum to 50. The brute-force approach tries every pair. But if the list is sorted by age, you can stand one person at the youngest end and one at the oldest end, then close in: if the sum is too small, advance the youngest pointer; if too large, retreat the oldest pointer. Each step, one pointer moves, and you never backtrack either. That's opposing two pointers — O(n) instead of O(n²).

For a sliding window, imagine looking through a narrow rectangular frame laid over a long strip of data. You slide the frame rightward, adding the new element on the right and (in the fixed-size case) discarding the old one on the left — computing the window's property incrementally rather than recomputing it from scratch. Both ideas reduce 'check everything' to 'visit each element a constant number of times'.

Many array and string problems have an obvious O(n²) solution — check every pair, or re-scan every subarray — and a much better O(n) one hiding behind a simple observation. The two-pointer and sliding-window techniques are how you find that O(n) solution. They're among the highest-return patterns to master: a large fraction of array/string interview questions, and a great deal of real stream-processing code, reduce to one of them.

Two pointers, pattern 1: opposing ends

Place one pointer at the start and one at the end of a sorted array, and move them toward each other based on a comparison. The canonical example — find two numbers summing to a target in a sorted array:

1. left = 0, right = n − 1.
2. Compute sum = array[left] + array[right].
3. If sum == target, done. If sum < target, the only way to grow it is to move left rightward (a larger small value). If sum > target, move right leftward (a smaller large value).
4. Repeat until the pointers cross.

Sorted array: [  2,  7, 11, 15, 20, 25 ]
               idx:  0   1   2   3   4   5
Target sum: 22

Step 1  left=0(val=2)  right=5(val=25)  sum=27 > 22 → right--
        [  2,  7, 11, 15, 20, 25 ]
           ↑L                ↑R

Step 2  left=0(val=2)  right=4(val=20)  sum=22 == 22 → FOUND (2, 20)  ✓
        [  2,  7, 11, 15, 20, 25 ]
           ↑L          ↑R

Each step moves one pointer. They can cross at most n times total → O(n).
Correctness: when sum < target, every pair (left, anything ≤ right) is too small
             → left is safely skipped. Symmetric reasoning for sum > target.

Why it's O(n) and correct. Each step moves exactly one pointer inward, so they meet after at most n steps — one linear pass, O(1) space. Correctness rests on the sorted order: when sum is too small, *no* pair using the current left with anything ≤ right can reach the target, so left is safely discarded — the comparison lets you eliminate a whole possibility in one move. Compare this to the hash-map two-sum from Lesson 9: that works on *unsorted* input with O(n) extra space; this works on *sorted* input with O(1) space. The palindrome check from Lesson 4 and array reversal are the same opposing-pointer template.

Two pointers, pattern 2: same direction (fast/slow)

Both pointers move forward at different rates or under different conditions. A slow pointer marks a 'write' position while a fast pointer scans ahead — the standard way to remove duplicates or filter an array *in place*. It also powers Floyd's cycle detection from Lesson 5 (slow +1, fast +2). To dedupe a sorted array in place: slow starts at 0; fast scans; whenever array[fast] differs from array[slow], advance slow and copy it there. One pass, O(n) time, O(1) space, and the first slow+1 elements are the unique values.

Sorted array: [ 1, 1, 2, 3, 3, 4 ]   (n=6)
               idx:  0  1  2  3  4  5

slow=0, fast=0 → fast scans:

fast=1: array[1]=1 == array[slow=0]=1 → skip (duplicate)
fast=2: array[2]=2 != array[slow=0]=1 → slow=1, array[1]=2
        array now: [ 1, 2, 2, 3, 3, 4 ]
                       ↑slow
fast=3: array[3]=3 != array[slow=1]=2 → slow=2, array[2]=3
        array now: [ 1, 2, 3, 3, 3, 4 ]
                          ↑slow
fast=4: array[4]=3 == array[slow=2]=3 → skip
fast=5: array[5]=4 != array[slow=2]=3 → slow=3, array[3]=4
        array now: [ 1, 2, 3, 4, 3, 4 ]   (first slow+1=4 elements are unique)
                             ↑slow
Result: unique portion = array[0..3] = [ 1, 2, 3, 4 ]  ✓

The sliding window

A sliding window is two same-direction pointers bounding a contiguous subarray/substring that grows and shrinks as it slides across the input. Instead of recomputing each window from scratch (O(n) per window → O(n²) overall), you update incrementally — add the element entering the window, remove the one leaving — so the whole scan is O(n). Two flavors:

• Fixed-size window. The window is always exactly k wide. Compute the first window's value, then slide: add the new right element, subtract the old left element. Classic use: maximum sum of any k consecutive elements, or averages over a rolling window. (The monotonic deque from Lesson 7 handles the harder 'max of each window' variant.)
• Variable-size window. The window grows and shrinks to maintain a condition. Expand the right edge to include more; when the window violates the constraint, contract the left edge until it's valid again. Used for 'longest/shortest subarray satisfying X' problems.

Array: [ 2,  1,  5,  1,  3,  2 ]
         idx:  0   1   2   3   4   5
k=3, find max sum of any 3 consecutive elements.

Initial window [0..2]: sum = 2+1+5 = 8
Slide right:
  Remove array[0]=2, add array[3]=1 → sum = 8-2+1 = 7   window [1..3]
  Remove array[1]=1, add array[4]=3 → sum = 7-1+3 = 9   window [2..4]  ← max
  Remove array[2]=5, add array[5]=2 → sum = 9-5+2 = 6   window [3..5]

Answer: 9 (subarray [5,1,3])   ✓

Each element enters once (right edge) and leaves once (left edge) → O(n) total.
No recomputing from scratch!

Worked example: longest substring without repeating characters

Find the longest substring with all-distinct characters. Brute force checks every substring: O(n²) or worse. Sliding window does it in O(n): expand right, adding each character to a set tracking the current window's characters; when the new character is already in the set, contract from the left (removing characters) until the duplicate is gone; track the maximum window length throughout. Trace on 'abcabcbb': window grows to 'abc' (length 3); next 'a' duplicates → shrink from left past the old 'a', window becomes 'bca' then continues; the maximum distinct window stays 3. Each character is added once and removed at most once — the right and left pointers each traverse the string a single time, so despite the inner shrink loop the total is O(n), O(min(n, alphabet)) space.

String: a  b  c  a  b  c  b  b
 index: 0  1  2  3  4  5  6  7
left=0, maxLen=0, seen={}

right=0: add 'a' → seen={a}   window='a'     len=1  maxLen=1
right=1: add 'b' → seen={a,b} window='ab'    len=2  maxLen=2
right=2: add 'c' → seen={a,b,c} window='abc' len=3  maxLen=3
right=3: 'a' in seen → shrink:
   remove array[left=0]='a', left=1 → seen={b,c}
   add 'a' → seen={b,c,a}   window='bca'  len=3  maxLen=3
right=4: 'b' in seen → shrink:
   remove 'b'(left=1), left=2 → seen={c,a}
   add 'b' → seen={c,a,b}   window='cab'  len=3  maxLen=3
right=5: 'c' in seen → shrink:
   remove 'c'(left=2), left=3 → seen={a,b}
   add 'c' → seen={a,b,c}   window='abc'  len=3  maxLen=3
right=6: 'b' in seen → shrink twice → window='cb' len=2
right=7: 'b' in seen → shrink → window='b'  len=1

Answer: maxLen = 3  ('abc' or 'bca' or 'cab')  ✓
Total pointer moves: right traverses 8, left traverses ≤ 8 → O(n)

Complexity and recognition

The recognition signals are worth memorizing: 'sorted array' + 'find a pair' → opposing pointers. 'Contiguous subarray/substring' + 'longest/shortest/max/min' → sliding window. 'In place, no extra array' + 'remove/partition' → fast/slow. Spotting the pattern is most of the solution; the code is short once you know which template applies.

Under the hood: why the inner loop doesn't make it O(n²)

The subtlety of sliding window is that the shrink loop looks like O(n) work per outer iteration, suggesting O(n²) total. But use an amortized argument: assign a 'token' to each element — it starts with one token, spends it when left advances past it. Each element can contribute to the shrink loop at most once across the entire run (because left is monotonically non-decreasing). So total shrink operations across all outer iterations ≤ n. Right pointer advances n times. Total work: 2n = O(n). This is the same amortized reasoning used for stack operations in Lesson 6 and the monotonic deque in Lesson 7.

Common pitfalls

• Using opposing pointers on unsorted data. The technique's correctness depends on order. Sort first (if allowed), or use a hash map instead.
• Recomputing the window from scratch. The whole point is incremental updates. Re-summing each window reintroduces the O(n²) you were escaping.
• Botching the shrink condition in variable windows. Contract while the window is invalid, then update the answer — getting the order or the loop bound wrong is the usual bug. Hand-trace on a small string.
• Off-by-one on window size. A window from left to right inclusive has length right − left + 1. Fixed-window slides must add-then-remove (or remove-then-add) consistently.
• Forcing a window where none exists. These patterns need *contiguity* (subarrays/substrings) or *sortedness*. For subsequences or unordered subsets, they don't apply — reach for dynamic programming or other tools.

Practice problems

1. 3Sum: find all unique triplets in an unsorted array summing to zero. Sort, then for each element i, apply opposing two pointers on the rest. O(n²) overall — better than O(n³) brute force.
2. Minimum window substring: given strings s and t, find the smallest window in s containing all characters of t. Variable sliding window with a character-frequency map. O(n + m).
3. Maximum sum subarray of size k: classic fixed-window. Initialize with the first k elements, then slide. O(n).

Key takeaways

• Two pointers and sliding windows turn many O(n²) pair/subarray scans into O(n) single passes by moving pointers monotonically.
• Opposing pointers exploit sorted order to eliminate possibilities one comparison at a time; fast/slow pointers filter in place and detect list cycles.
• Sliding windows update incrementally — fixed-size (exactly k) or variable-size (grow/shrink to keep a condition).
• They're linear because each element is added and removed a constant number of times — the amortized argument again.
• Recognition is the skill: sorted+pair → opposing; contiguous+extremal → window; in-place filter → fast/slow.

These patterns were specific tactics. The next lessons zoom out to *design paradigms* — general strategies for building algorithms — starting with the one merge sort and quicksort already used: divide and conquer. Drill two-pointer and window questions in the **AI Learning app**.

AI Learning: AI/ML/DS Q&A

A private, offline app to learn Artificial Intelligence, Machine Learning & Data Science at your own level: ~10,000 Q&A, illustrated guides, cheat sheets, quizzes and mock tests.

Coming soon toGoogle Play