Two Pointers & Sliding Window
"Give me 30 minutes of music." To answer, Tunebox needs a run of back-to-back tracks that fits the time. The obvious way tries every start with every end — O(n²) pairs, so 10,000 tracks means 50 million checks. This lesson gets the same answers in one pass: instead of one index looping inside another, two indexes move through the array together, and neither ever turns back.
The brute force, and what it wastes
Find two tracks that exactly fill a 9-minute gap before the news:
The inner loop learns nothing from the sort. Once 2 + 8 is too big, every pair containing the 8 is too big — 2 is the shortest partner it will ever get. That track could be thrown away after a single check.
Pointers from both ends
Put lo on the shortest track and hi on the longest, and look at their sum:
- too small → only a longer partner for
locan help: moveloright. - too big →
hiis too long for every track left: movehileft. - exactly right → done.
Every step discards one track for good, so it takes at most n steps: O(n) time, O(1) extra space.
❓ Cross-question — "How do I know it never skips the right pair?"
hionly moves left whenmins[lo] + mins[hi]is too big. Every partner still available is at least as long asmins[lo], so thathitrack was too long for all of them — it couldn't be in any answer. The same argument coverslo. A pointer only ever leaves behind tracks that can't be part of a pair.
mins = [1, 3, 4, 5, 9]
lo, hi = 0, len(mins) - 1
steps = 0
while lo < hi:
steps += 1
total = mins[lo] + mins[hi]
if total == 8:
break
if total < 8:
lo += 1
else:
hi -= 1
print(mins[lo], mins[hi], steps)The same shape — start at both ends, walk inward — reverses a list in place and checks for palindromes:
Both ends must start on real items:
IndexError"level" reads the same both ways, so this should print True. It crashes on the very first comparison instead.
Same direction: a read pointer and a write pointer
Pointers don't have to face each other. To remove skipped plays (0 minutes) in
place, read visits every slot and write marks where the next keeper goes:
plays = [3, 0, 0, 4, 0, 5]
write = 0
for read in range(len(plays)):
if plays[read] != 0:
plays[write] = plays[read]
write += 1
print(plays)write never overtakes read, so nothing is overwritten before it has been read.
That's O(n) time and O(1) space — calling plays.remove(0) in a loop would be O(n)
per removal, O(n²) in all.
Fixed-size sliding window
"Which 3 back-to-back tracks have the most plays?" Re-summing every window is O(n·k). But neighbouring windows share all but two tracks, so slide instead: add the track that enters and subtract the one that leaves.
Getting the leaving index right is the whole trick:
This should print 18, the best total of 3 neighbouring tracks. It prints 20 — the wrong track is leaving the window, so "window" stops being a window.
Variable-size sliding window
The window doesn't need a fixed size. For "the longest run of tracks within a time limit", let it grow on the right while it fits and shrink on the left when it doesn't:
Why it's O(n), not O(n²): there is a loop inside a loop, but the inner one only moves
startforward, andstartnever goes back. Across the whole runendmoves n times andstartat most n times: 2n steps. The cost is amortized over the pass, just likeappend.
❓ Cross-question — "What if a duration could be negative?" Then it breaks. Shrinking assumes that dropping a track never raises the total and adding one never lowers it. With negative numbers a window over the limit could come back under by adding a track, so throwing away its left side can lose the answer. Zero-minute tracks are fine; negatives need a different technique.
Complexity at a glance
| task | brute force | with pointers |
|---|---|---|
| pair with a given sum (sorted input) | O(n²) | O(n) time, O(1) space |
| reverse / palindrome check | O(n) time, O(n) copy | O(n) time, O(1) space |
| remove items in place | O(n²) with remove |
O(n) time, O(1) space |
| best window of size k | O(n·k) | O(n) |
| longest window under a limit | O(n²) | O(n) |
Coming from Java/JS: nothing here is Python-specific —
while (lo < hi)reads the same everywhere. Python just adds the swap without a temp variable:a[lo], a[hi] = a[hi], a[lo].
Idioms & real-world patterns
When the input isn't sorted
Pointers from both ends need sorted data. Sorting costs O(n log n) — still far better than O(n²). If you need the original positions, sort the indexes instead of the values. (A hash table finds the pair in one O(n) pass with no sort, at the price of O(n) memory — that's next lesson.)
Neighbours with pairwise
Comparing each track with the next is two pointers one step apart. itertools.pairwise
does it without indexes or slice copies:
⚡ Advanced — windows that count instead of sum
Plenty of window problems count what's inside — "the longest run with at most 2 different artists". The shape is identical; only the "is this window still valid?" test changes, and a dict of counts keeps it O(1):
🎯 Your turn
Build the session finder: session_within(durations, limit) returns the longest
run of back-to-back tracks whose total minutes are at most limit, as [start, end]
with end exclusive. Ties go to the earliest run; if no track fits, return [0, 0].
Every duration is positive.
session_within([5, 5, 5, 5], 12)→[0, 2]session_within([3, 1, 2, 1], 4)→[1, 4]
Hint — it's longest_within from above, but remember where the best window was,
not just how long it was — and only replace it when a window is strictly longer.
Then press ▶ Run, tap the Live App try chips to call it with different inputs, and hit ✓ Check. Green = this piece of Tunebox is built. ✅