DevPath
Tracks

Two Pointers and Sliding Window

Turn nested loops into a single pass by moving two indexes cleverly: opposite-end pointers, fast and slow pointers, and windows that grow and shrink.

intermediate40 min#two-pointers#sliding-window#arrays#strings

Prerequisites: Arrays and Dynamic Arrays

Why it matters

A huge share of array and string problems ask about pairs, ranges, or substrings. The brute-force answer checks every pair or every range with nested loops, which is O(n^2) or worse. Two pointers and sliding window reduce many of these to a single O(n) pass, and they need almost no extra memory. They are among the most common patterns in coding interviews and in real code that scans logs, streams, or time series.

Intuition

Think of a caterpillar crawling along a branch. Its head moves forward to explore; its tail moves forward to let go of what it no longer needs. The two ends never move backwards, so over the whole trip each end travels at most n steps. That is the entire trick: two indexes that only move in one direction give a total of at most 2n moves, even when the work looks nested.

The pattern works when moving a pointer lets you safely rule out a whole group of candidates. In a sorted array, if the sum of the two ends is too big, the right end cannot pair with anything to its right of the left end, so you can drop it for good.

How it works

There are three common shapes.

1. Opposite ends. Start l = 0 and r = n - 1 and move them toward each other. This needs some monotonic property, usually a sorted array. Used for pair sums, reversing, palindrome checks, and container-with-most-water style problems.

Here is the opposite-end search from the code below, looking for a pair that sums to 10.

1
0
l
3
1
4
2
6
3
8
4
11
5
r
Target 10. 1 + 11 = 12, which is too big.
step 1 / 5

Every step discards one end for good, so the pointers meet or find the pair in at most n steps. Click Next to step through.

2. Fast and slow (same direction). A slow pointer marks where the next good item goes; a fast pointer scans. Used for in-place deduplication, removing a value, partitioning, and cycle detection in linked lists.

3. Sliding window. Two indexes left and right bound a window. Expand right to add an element, then while the window breaks a rule, advance left to remove elements. You keep a small summary of the window (a sum, a count map) updated in O(1) per move.

s = "abcabcbb"
 window grows right:      [a b c] a b c b b     size 3
 'a' repeats, left jumps:   a [b c a] b c b b   size 3
 'b' repeats, left jumps:   a b [c a b] c b b   size 3

Two flavours of window: fixed size (always k items, add the new one and drop the old one) and variable size (grow until invalid, then shrink until valid again). For variable windows, decide whether you are maximizing length (record the best after restoring validity) or minimizing length (record the best while the window is valid, before shrinking).

First the fixed window from max_sum_window: instead of re-adding k numbers, add the new item and drop the old one.

2
0
left
1
1
5
2
right
1
3
3
4
2
5
k = 3. First window 2 + 1 + 5 = 8. Best = 8.
step 1 / 4

The window sum is updated in O(1) per slide (new minus old) instead of re-summing the window.

Now the variable window from longest_unique on abcabcbb: the window grows on the right and left jumps past a repeated letter.

a
0
left
b
1
c
2
right
a
3
b
4
c
5
b
6
b
7
Letters a, b, c are all new. Window length 3, best = 3.
step 1 / 6

The window always holds distinct letters. When a letter repeats, left jumps just past its previous copy and never moves backwards.

Sliding window assumes that shrinking a window never makes it more valid in a way you would miss, and that expanding never makes it less so. Sums of non-negative numbers satisfy this. Sums with negative numbers do not, which is why subarray-sum problems with negatives use prefix sums and a hash map instead.

OperationTimeNotes
Opposite-end pair search (sorted)O(n)Each pointer moves at most n times
Fast / slow in-place filteringO(n)O(1) extra space
Sliding window (any size)O(n)Left and right each pass the array once
Brute-force pairs or rangesO(n^2)What these patterns replace
Window state (count map)O(k) spacek is the alphabet or distinct items

Code: three classic windows

The first function is an opposite-end search on a sorted array. The second is a variable window with a map of last-seen positions. The third is a fixed window that updates its sum incrementally.

def two_sum_sorted(a, target):
    l, r = 0, len(a) - 1
    while l < r:
        s = a[l] + a[r]
        if s == target:
            return (l, r)
        if s < target:
            l += 1
        else:
            r -= 1
    return None
 
def longest_unique(s):
    last = {}          # char -> most recent index
    left = best = 0
    for right, ch in enumerate(s):
        if ch in last and last[ch] >= left:
            left = last[ch] + 1   # shrink past the earlier copy
        last[ch] = right
        best = max(best, right - left + 1)
    return best
 
def max_sum_window(a, k):
    cur = sum(a[:k])
    best = cur
    for i in range(k, len(a)):
        cur += a[i] - a[i - k]   # slide: add new, drop old
        best = max(best, cur)
    return best
 
print(*two_sum_sorted([1, 3, 4, 6, 8, 11], 10))
print(longest_unique("abcabcbb"), longest_unique("pwwkew"))
print(max_sum_window([2, 1, 5, 1, 3, 2], 3))

The output of both versions is three lines: 2 3 (indexes of 4 and 6, which sum to 10), 3 3 (the longest unique substrings of "abcabcbb" and "pwwkew" both have length 3), and 9 (the window 5, 1, 3).

Common pitfalls

  • Using it on unsorted data: opposite-end pair search needs sorted input. Otherwise use a hash map or sort first (and remember sorting loses original indexes).
  • Forgetting to guard the jump: in the unique-substring code, left must only move forward. Without the check last[ch] >= left, an old occurrence outside the window would pull left backwards.
  • Negative numbers in sum windows: the window logic breaks, because adding an element can lower the sum. Reach for prefix sums.
  • Off-by-one on window length: length is right - left + 1, not right - left.
  • Moving the wrong pointer: in opposite-end problems, always be able to argue why the discarded candidate can never be part of an answer.

Practice

Reverse a string in place easy

Hint

Swap the two ends, then move both inward until they meet.

Show solution

Set l = 0 and r = n - 1. While l < r, swap the two items and move both pointers inward. O(n) time, O(1) extra space (note that Python and JavaScript strings are immutable, so convert to a list or array first).

Minimum size subarray with sum at least target medium

Hint

All numbers are positive. Expand right until the sum is big enough, then shrink left as far as you can.

Show solution

Keep a running total. For each right, add a[right]. While total >= target, record right - left + 1 and then subtract a[left] and advance left. Because every number is positive, shrinking always reduces the sum, so the window logic is sound. O(n) time, O(1) space. Return 0 if no window qualified.

Three Sum medium

Hint

Fix one number, then solve a two-sum on the sorted remainder. How do you skip duplicates?

Show solution

Sort the array. For each index i, run opposite-end pointers on i + 1 .. n - 1 looking for a pair summing to -a[i]. After finding a triple, move both pointers and skip values equal to the previous ones. Also skip repeated values of a[i]. O(n^2) time, which beats the O(n^3) brute force.

Longest substring with at most k distinct characters hard

Hint

Keep a count map of the window. Distinct count is the number of keys with a positive count.

Show solution

Expand right, incrementing its count. While the number of distinct keys exceeds k, decrement the count of a[left], delete the key at zero, and advance left. Record right - left + 1 after each step. Each index enters and leaves the window once, so O(n) time and O(k) space.

Interview questions

  1. When can you use two pointers instead of a hash map for two sum? When the input is sorted (or you can sort it and indexes do not matter). Pointers give O(1) space; a map works on unsorted data in O(n) time but O(n) space.
  2. Why is a sliding window O(n) even though there is a loop inside a loop? left never moves backwards, so across the whole run it advances at most n times. The total number of operations is at most 2n.
  3. Fixed versus variable window: how do you choose? If the problem fixes the length k, use a fixed window. If it asks for the longest or shortest range satisfying a condition, use a variable window.
  4. How would you detect a cycle in a linked list with O(1) memory? Fast and slow pointers: fast moves two steps, slow one; if they ever meet there is a cycle.

Interviewers look for: stating the invariant that justifies discarding candidates, handling empty and single-element inputs, and noticing when negative numbers or unsorted data invalidate the approach.

Quick check

Why does the variable sliding window run in O(n) total even though it has a while loop inside a for loop?

Finished this lesson?

Further resources

Related lessons