Two Pointers & Windows

Two Pointers (Opposite Ends)

Move two indices toward each other on sorted or symmetric data.

Easy, about 60 minutes to practise.

1Understand

The idea

Start one pointer at each end and move them toward each other. On sorted data, comparing the current pair tells you which pointer to move: if the sum is too small, only moving the left one can raise it. Every step rules out a whole row of pairs, so the search is O(n) instead of O(n²).

Intuition

Start one pointer at each end and move them toward each other. On sorted data, comparing the current pair tells you which pointer to move: if the sum is too small, only moving the left pointer can raise it; if too large, move the right.

Every step rules out a whole row of pairs, so the search is O(n) instead of O(n²). The same skeleton handles container-with-most-water and palindrome checks from both ends.

The input must be sorted (or naturally symmetric). Unsorted data needs a sort first or a different pattern.

What you will be able to do

  • Justify which pointer to move
  • Skip duplicates for unique results

When to use it

  • Input is sorted
  • Pair or triplet with a target sum
  • Compare from both ends (palindrome, container)

2See it

Walkthrough

Pair with target sum (sorted)

nums = [1, 2, 4, 7, 11], target = 13, move the end that can fix the sum.

1 / 6

LR
1
2
4
7
11
01234
L → index 0R → index 4

Sorted array, left=0, right=n−1. Requires non-decreasing order.

left, right = 0, n - 1

Live template

Line 1 active

1lo, hi = 0, len(a) - 1
2while lo < hi:
3 s = a[lo] + a[hi]
4 if s == target: ...
5 elif s < target: lo += 1
6 else: hi -= 1

Complexity: time O(n), space O(1)

O(n) after the array is sorted; sorting makes O(n log n) overall. Space O(1) besides the output. Hashing two-sum is O(n) time/space and keeps indices without sorting, use opposite pointers when sorted order is already required or you want O(1) extra space.

Read the walkthrough as text

Two sum on a sorted array. a = [1, 2, 4, 7, 11], target = 9.

  1. lo = 0, hi = 4. Sum 1+11=12 too big → hi -= 1.
  2. Sum 1+7=8 too small → lo += 1.
  3. Sum 2+7=9, found.

For 3-sum, fix one index and run this on the suffix, skipping duplicates so each triplet appears once.

3Recognise it

Kinds of problems (5)

Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.

  • Pair sum on sorted input

    Example. Sorted array; find two numbers that add to target.

    How. Left at start, right at end; move the side that can fix a too-small or too-large sum.

  • 3-sum (fix one, two pointers on the rest)

    Example. Find all unique triplets that sum to zero.

    How. Sort; fix index i; run opposite pointers on i+1 … n−1; skip duplicates.

  • Container with most water

    Example. Two lines form a container; maximise area.

    How. Area is min(height[L], height[R]) × (R, L); move the shorter side inward.

  • Reverse or compare from both ends

    Example. Check palindrome, or reverse words/characters in place.

    How. Swap or compare at L and R, then L++, R-- until they meet.

  • Trapping rain water

    Example. How much water bars can trap.

    How. Two pointers with running leftMax/rightMax; water at a cell is limited by the smaller max.

Common mistakes

Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.

  • Wrong pointer moved

    Why it happens. Guessing which pointer to move instead of letting the comparison decide.

    How it fails. Sum too small but you decrement right, you discard pairs that could still work with a larger left value.

    Fix. On sorted data: sum < target → left++; sum > target → right--. The comparison tells you which side can help.

  • Duplicate results

    Why it happens. After finding one triplet, the next equal values reproduce the same answer.

    How it fails. nums = [-1, -1, 0, 1, 1]; without skipping, (−1, 0, 1) appears twice.

    Fix. After a hit (and when advancing past equals), while lo < hi and a[lo] == a[lo−1]: lo += 1 (same for hi).

  • Unsorted input

    Why it happens. Opposite pointers on unsorted data do not give a monotonic signal about which side to move.

    How it fails. On [3, 1, 4] looking for sum 5, moving either pointer can skip the only pair (1, 4).

    Fix. Sort first (or use a hash map if you must keep indices). Opposite pointers assume order.

4Check yourself

Concept check

A short quiz on this lesson before you practise. Optional, and it does not gate coding.

Ready to practise?

Mastery comes from solving. The lesson is optional context.

All lessons