Two pointers and sliding windows · Data Structures and Algorithms

Why you need it

The intuition

Definition

Two pointers

Two indexes that move toward each other (or in the same direction) so each element is visited once.

Sliding window

A range [left, right) over the list that moves forward, updating a running total instead of recomputing it.

Examples

1
2
3
4
5
6
7
8
9
10
11
12
13

def pair_sum(xs, target):
    left, right = 0, len(xs) - 1
    while left < right:
        total = xs[left] + xs[right]
        if total == target:
            return (xs[left], xs[right])
        if total < target:
            left += 1
        else:
            right -= 1
    return None

print(pair_sum([1, 3, 4, 6, 9, 11], 13))

1
2
3
4
5
6
7
8

sales = [4, 2, 7, 1, 8, 3, 5]
k = 3
window = sum(sales[:k])
best = window
for i in range(k, len(sales)):
    window += sales[i] - sales[i - k]
    best = max(best, window)
print(best)

Common mistakes

Quick quiz

1
2
3
4
5
6
7

xs = [1, 2, 3, 4, 5]
left, right = 0, len(xs) - 1
while left < right:
    xs[left], xs[right] = xs[right], xs[left]
    left += 1
    right -= 1
print(xs)

Practice

3 exercises in three steps: predict what a program prints, change a program to meet a new requirement, then write one from scratch. Your code runs in the browser and is checked the moment you submit.

1. PredictTrace the pointers

   Type exactly what this program prints.

2. ModifyRemove duplicates in one pass

   dedupe(xs) gets a sorted list and returns it without repeats. The inner loop scans all of out for every item (O(n²)). Since the list is sorted, a repeat can only equal the last item kept. Use that to make it O(n).

3. WriteBest window

   Write best_window(xs, k) that returns the largest sum of any k consecutive numbers in xs (assume len(xs) ≥ k ≥ 1). Use a sliding window: O(n).

Terms in this lesson