Pointer Walk

Two Pointers and Sliding Window

Two markers moving through an array turn a search over every pair into a single pass.

AlgorithmsIntermediate9 min read

Getting rid of the loop inside the loop

Many problems about a list have an obvious solution with a loop inside a loop: for every item, look at every other item. That is O(n²). On a list of 100,000 items it is five billion steps.

Two small techniques turn many of those problems into a single pass. Neither needs a special data structure. They only need you to notice that most of the work in the nested loop is repeated or pointless.

Two pointers

Problem: in a sorted list, find two numbers that add up to a target.

The slow way tries every pair. For 7 numbers that is 21 pairs. For 100,000 numbers it is about 5 billion.

The fast way uses the fact that the list is sorted.

  1. Put one pointer at each end

    left on the smallest number, right on the largest.

  2. Add the two numbers

    If the sum is the target, you are done.

  3. Sum too small? Move left up

    Pairing the left number with anything else gives an even smaller sum, since right is already on the largest. So the left number is useless. Skip it.

  4. Sum too big? Move right down

    By the same argument, the right number is useless.

  5. Stop when the pointers meet

    If they meet, there is no such pair.

Two numbers that add up to 14Interactive
1left, right = 0, len(items) - 1
2while left < right:
3 total = items[left] + items[right]
4 if total == target:
5 return left, right
6 if total < target:
7 left += 1
8 else:
9 right -= 1

Variables

nothing yet

Start. Press play, or step through one line at a time.

Three pairs checked instead of up to 21. Every step throws away one number for good, so there can never be more steps than numbers.

Why is it safe to skip?

This is the part worth understanding. When the sum is too small, the left number has just been tried with the largest partner still available, and it was not enough. No other partner can do better. So no answer includes it, and dropping it loses nothing.

Without sorted order that argument fails, and so does the technique.

Other uses of the same idea

  • Reverse a list in place: swap the two ends and move both pointers inwards.
  • Is this a palindrome? Compare the ends and move inwards.
  • Remove duplicates from a sorted list: a slow pointer marks where to write, a fast one reads ahead.
  • Merge two sorted lists: one pointer in each, always take the smaller. This is the merge step of merge sort.
  • Find a loop in a linked list: a slow pointer and a fast one. If there is a loop, the fast one catches up with the slow one.

Sliding window

Problem: in a list of daily sales, find the three days in a row with the highest total.

The slow way adds up every group of three from scratch. But neighbouring groups overlap almost completely. Days 1 to 3 and days 2 to 4 share two of their three numbers.

So keep one running total, and when the window moves one place:

  • add the number that came in,
  • subtract the number that went out.
The largest sum of 3 neighboursInteractive
1window = sum(items[0:3])
2best = window
3for i in range(3, len(items)):
4 window += items[i] # one comes in
5 window -= items[i - 3] # one goes out
6 best = max(best, window)

Variables

nothing yet

Start. Press play, or step through one line at a time.

Each move costs two operations, however wide the window is. A window of 3 and a window of 3,000 cost the same per move.

Example

How much is saved

A year of daily numbers, and you want the best 30-day stretch.

From scratch: 336 windows of 30 additions each, about 10,000 additions.

Sliding: 30 additions for the first window, then one in and one out for each of the 335 moves, about 700 operations.

The wider the window, the bigger the saving.

Windows that change size

The window does not have to stay the same width. For "the longest stretch with some property", let it grow and shrink.

  • Move the right edge forward to take in a new item.
  • While the window breaks the rule, move the left edge forward to drop items.
  • Record the widest valid window seen.
python
def longest_without_repeats(text):
    seen = set()
    left = best = 0
    for right, letter in enumerate(text):
        while letter in seen:           # rule broken: shrink from the left
            seen.remove(text[left])
            left += 1
        seen.add(letter)
        best = max(best, right - left + 1)
    return best

There is a while inside the for, but it is still a single pass. Each letter enters the window once and leaves at most once. Both edges only ever move forward.

Spotting them

The problem mentionsThink of
A sorted list, and a pair or triple that meets a conditionTwo pointers from the ends
Comparing or swapping the two endsTwo pointers from the ends
Two sorted lists to combine or compareOne pointer in each
A run of neighbours: subarray, substring, "in a row"Sliding window
"Longest", "shortest" or "best" stretch with some propertySliding window that grows and shrinks
A fixed number of neighbours, such as a moving averageSliding window of fixed width

Both rest on the same observation: the pointers only move forward, never back. That is what makes it one pass.

Key takeaways

  • Many loop-inside-a-loop solutions repeat work that a single pass can avoid.
  • Two pointers on a sorted list throws away one item per step, because that item has been shown to be useless.
  • A sliding window updates a running result by adding what enters and removing what leaves.
  • The window can grow and shrink to find the longest or shortest stretch with a property.
  • Both are one pass because the pointers only ever move forward.

Your progress

Check your progress

0%

  1. Read the page50% of this page

    When you have gone through the page and its animations, tick it off.

  2. Take the quiz50% of this page

    7 questions, from easy to hard. Take it as often as you like: the questions change, and only your best score counts.

Saved on this device only. See all your progress