Two pointers and sliding windows

Introduction

Many list problems that look like they need two nested loops, O(n²), can be solved in a single pass, O(n), by keeping two positions in the list and moving them cleverly. These patterns appear constantly in coding interviews.

Some problems seem to need checking every pair, which is slow on large lists. These patterns use what you know about the data to skip almost all of the pairs, turning quadratic work into a single pass.

How it works

Swapping inwards

letters = ["c", "o", "d", "e"]
i, j = 0, len(letters) - 1
while i < j:
    letters[i], letters[j] = letters[j], letters[i]
    i += 1
    j -= 1
print(letters)

Swap the two ends, then move both pointers towards the middle until they meet. The list is reversed in place, with no second list.

A sliding window

sales = [4, 2, 7, 1, 8, 3]
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)

To find the best total of 3 days in a row, do not re-add every window from scratch. Slide the window one step: add the new day and subtract the day that left. The windows total 13, 10, 16 and 12, so the answer is 16.

Syntax

left, right = 0, len(nums) - 1
while left < right:
    ...
    left += 1          # or right -= 1

window = sum(nums[:k])
for i in range(k, len(nums)):
    window += nums[i] - nums[i - k]

Example

nums = [1, 3, 4, 6, 9, 11]
target = 13
left, right = 0, len(nums) - 1
while left < right:
    total = nums[left] + nums[right]
    if total == target:
        print(nums[left], nums[right])
        break
    elif total < target:
        left += 1
    else:
        right -= 1

The list is sorted, and we want two numbers that add up to 13. Start with left at the smallest and right at the largest. If the sum is too small, move left up; if too big, move right down. The calculation box shows each sum, such as nums[left] + nums[right] → 1 + 11 → 12. The pair 4 + 9 is found in 4 checks, never more than n.

Line by line

1. nums is sorted, and target is 13.
2. left starts at the smallest value and right at the largest.
3. total adds the two values at the pointers.
4. If it is exactly right, the pair is printed and the loop ends.
5. If it is too small, only moving left up can help. If it is too big, only moving right down can.

Expected result

4 9

In the real world

Sliding windows are used for moving averages on stock prices and for limiting how many requests a server accepts. These patterns also come up constantly in coding interviews.

Common mistakes

• Using the from-both-ends pattern on an unsorted list: it only works because the list is sorted.
• Off-by-one window edges: the day leaving the window is sales[i - k], not sales[i - k + 1].
• Moving the wrong pointer; work through a small example by hand (or in the visualizer) first.

Best practices

• Check that the data is sorted before using the two-ends pattern.
• Work through a small example by hand first.
• Define exactly which items the window holds.

Summary

Two pointers replace nested loops by moving positions according to what is known about the data. The from-both-ends pattern needs sorted data, and a sliding window keeps a running total as it moves.

Practice

Use a sliding window to find the largest total of any 2 neighbouring values in [5, 1, 3, 9, 2] (the answer is 12).

Mark lesson complete