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.
Put one pointer at each end
lefton the smallest number,righton the largest.Add the two numbers
If the sum is the target, you are done.
Sum too small? Move left up
Pairing the left number with anything else gives an even smaller sum, since
rightis already on the largest. So the left number is useless. Skip it.Sum too big? Move right down
By the same argument, the right number is useless.
Stop when the pointers meet
If they meet, there is no such pair.
1left, right = 0, len(items) - 12while left < right:3 total = items[left] + items[right]4 if total == target:5 return left, right6 if total < target:7 left += 18 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.
1window = sum(items[0:3])2best = window3for i in range(3, len(items)):4 window += items[i] # one comes in5 window -= items[i - 3] # one goes out6 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.
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 bestThere 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 mentions | Think of |
|---|---|
| A sorted list, and a pair or triple that meets a condition | Two pointers from the ends |
| Comparing or swapping the two ends | Two pointers from the ends |
| Two sorted lists to combine or compare | One pointer in each |
| A run of neighbours: subarray, substring, "in a row" | Sliding window |
| "Longest", "shortest" or "best" stretch with some property | Sliding window that grows and shrinks |
| A fixed number of neighbours, such as a moving average | Sliding 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.