These are the notes for Python Coding Questions, episode 26: two pointers and the sliding window. Two patterns that turn slow nested loops into a single pass: a pair with a target sum in a sorted list, the container with the most water, and the maximum sum of k consecutive items.
Every program was run with Python 3.13 (python3 main.py), the SyntaxPilot compiler's Python command. Every output below is real. Timings change from machine to machine and run to run; what matters is how they grow.
Two words for today:
- Two pointers: two index variables (here
leftandright) that move through a list, usually from both ends towards each other, each step ruling something out. - Sliding window: a block of consecutive items (a window) that moves along the list one step at a time, updated instead of recomputed.
Q1: Pair with a target sum (sorted list)
Real-life example: two friends at a gift shop with a sorted price list 150, 200, 350, 400, 650, 800 want two different gifts costing exactly 1,000 rupees together.
Attempt 1: try every pair
import time
def pair_sum(prices, target):
for i in range(len(prices)):
for j in range(i + 1, len(prices)):
if prices[i] + prices[j] == target:
return prices[i], prices[j]
return None
prices = [150, 200, 350, 400, 650, 800] # sorted gift prices
print(pair_sum(prices, 1000))
for n in [2_000, 4_000, 8_000]:
big = list(range(1, n + 1))
start = time.perf_counter()
pair_sum(big, 0) # no pair: check them all
print(n, f"{time.perf_counter() - start:.2f} s")
Output:
(200, 800)
2000 0.07 s
4000 0.27 s
8000 1.07 s
Correct, but double n → about 4× the time: every pair is checked, n(n-1)/2 pairs, O(n²). And we ignored the one thing we were given: the list is sorted.
The fix: one pointer at each end
| Situation | Move | Why it is safe |
|---|---|---|
prices[left] + prices[right] < target |
left += 1 |
even the costliest gift can't lift prices[left] to the target, so prices[left] pairs with nothing |
prices[left] + prices[right] > target |
right -= 1 |
even the cheapest gift is too much with prices[right], so it pairs with nothing |
| equal | done |
Each step throws one gift away for good, so at most n steps: O(n) time, O(1) space.
The trap: left <= right
def pair_sum(prices, target):
left, right = 0, len(prices) - 1
while left <= right:
total = prices[left] + prices[right]
if total == target:
return prices[left], prices[right]
if total < target:
left += 1 # need more: move up from the cheap end
else:
right -= 1 # too much: move down from the costly end
return None
prices = [150, 200, 350, 400, 650, 800]
print(pair_sum(prices, 1000))
print(pair_sum(prices, 700))
Output:
(200, 800)
(350, 350)
(350, 350) for 700: one gift used twice. Why: with <= the loop keeps going when left == right, so both friends point at the same gift. Two different items need left < right.
import time
def pair_sum(prices, target):
left, right = 0, len(prices) - 1
while left < right: # two DIFFERENT gifts
total = prices[left] + prices[right]
if total == target:
return prices[left], prices[right]
if total < target:
left += 1
else:
right -= 1
return None
prices = [150, 200, 350, 400, 650, 800]
print(pair_sum(prices, 1000), pair_sum(prices, 700), pair_sum(prices, 550))
print(pair_sum([], 5), pair_sum([5], 10))
big = list(range(1, 1_000_001))
start = time.perf_counter()
print(pair_sum(big, 0), f"{time.perf_counter() - start:.2f} s")
Output:
(200, 800) None (150, 400)
None None
None 0.06 s
Two pointers need sorted input
On an unsorted list the moves no longer rule anything out, and real pairs are missed. Sort first (O(n log n)), or use the set/dict approach from episode 8 (O(n) time, O(n) space).
def pair_sum(prices, target):
left, right = 0, len(prices) - 1
while left < right:
total = prices[left] + prices[right]
if total == target:
return prices[left], prices[right]
if total < target:
left += 1
else:
right -= 1
return None
unsorted = [150, 200, 350, 650, 800, 400] # NOT sorted
print(pair_sum(unsorted, 1000)) # misses (200, 800)
print(pair_sum(sorted(unsorted), 1000))
Output:
None
(200, 800)
Q2: Container with most water
Real-life example: walls of different heights stand in a row on a roof. Pick two walls and fill water between them: it spills over the shorter wall. Which pair holds the most?
water = min(walls[left], walls[right]) * (right - left): the shorter height times the width.
Attempt 1: all pairs
import time
def most_water(walls):
best = 0
for i in range(len(walls)):
for j in range(i + 1, len(walls)):
water = min(walls[i], walls[j]) * (j - i)
best = max(best, water)
return best
print(most_water([1, 8, 6, 2, 5, 4, 8, 3, 7]))
for n in [2_000, 4_000, 8_000]:
walls = list(range(n))
start = time.perf_counter()
most_water(walls)
print(n, f"{time.perf_counter() - start:.2f} s")
Output:
49
2000 0.14 s
4000 0.74 s
8000 2.42 s
49 is right (the walls of height 8 and 7, seven apart), but it's O(n²) again.
The fix: start widest, always move the shorter wall
Start with the first and last walls (the widest tank). Then:
- Moving the taller wall inwards: the width shrinks, and the height is still capped by the same short wall, so the water can only go down. Never useful.
- Moving the shorter wall: the width shrinks too, but a taller wall might replace it and raise the level. The only move with hope.
So the shorter wall has already had its best tank (the widest one) and can be dropped for good. One step per wall: O(n) time, O(1) space. When both walls are equal, moving either is fine.
import time
def most_water(walls):
left, right = 0, len(walls) - 1
best = 0
while left < right:
water = min(walls[left], walls[right]) * (right - left)
best = max(best, water)
if walls[left] < walls[right]:
left += 1 # the shorter wall limits the water
else:
right -= 1
return best
print(most_water([1, 8, 6, 2, 5, 4, 8, 3, 7]))
print(most_water([1, 1]), most_water([4, 3, 2, 1, 4]), most_water([5]))
walls = list(range(1_000_000))
start = time.perf_counter()
print(most_water(walls), f"{time.perf_counter() - start:.2f} s")
Output:
49
1 16 0
249999500000 0.12 s
Q3: Maximum sum of k consecutive items (sliding window)
Real-life example: a shop's daily sales in thousands of rupees: 4, 2, 1, 7, 3, 6, 9. The best 3 days in a row are the last three: 3 + 6 + 9 = 18. Picture a cardboard frame covering 3 days, sliding along one day at a time.
Attempt 1: sum every window, and an off-by-one
def best_k_days(sales, k):
best = sum(sales[:k])
for i in range(len(sales) - k): # every window of k days?
best = max(best, sum(sales[i:i + k]))
return best
sales = [4, 2, 1, 7, 3, 6, 9] # thousands of rupees per day
print(best_k_days(sales, 3))
Output:
16
16, not 18. Why: with n = 7 days and k = 3 there are n - k + 1 = 5 windows, starting at 0 to 4. range(len(sales) - k) gives 0 to 3, so the last window (3, 6, 9) is never checked: a classic off-by-one error. And even fixed, summing every slice from scratch is O(n · k).
The fix: slide, one day in and one day out
Neighbouring windows share k - 1 days. So:
window = sum(sales[:k])once.- For each new day
ifromkto the end:window += sales[i] - sales[i - k](add the day coming in, subtract the day leaving). - Keep the best. If
k > len(sales), there is no window: returnNone.
O(n) time, O(1) space, whatever k is. Below it races the (correct) slice version on 50,000 days with k = 10,000.
import time
def best_k_days(sales, k):
if k > len(sales):
return None
window = sum(sales[:k]) # the first k days
best = window
for i in range(k, len(sales)):
window += sales[i] - sales[i - k] # one day in, one day out
best = max(best, window)
return best
sales = [4, 2, 1, 7, 3, 6, 9]
print(best_k_days(sales, 3), best_k_days(sales, 1), best_k_days(sales, 7))
print(best_k_days([5, 1], 3), best_k_days([-3, -1, -2], 2))
def slow(sales, k):
return max(sum(sales[i:i + k]) for i in range(len(sales) - k + 1))
days = list(range(50_000))
for f in (slow, best_k_days):
start = time.perf_counter()
f(days, 10_000)
print(f.__name__, f"{time.perf_counter() - start:.2f} s")
Output:
18 9 32
None -3
slow 2.97 s
best_k_days 0.00 s
All-negative sales still work (-3, the least bad pair) because best starts from a real window, not from 0.
Common mistakes (and what you really see)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
| nested loops on a sorted list | double n → 4× the time | O(n²), ignores the order | two pointers from both ends |
while left <= right: |
(350, 350) for 700 |
one item used twice | while left < right: |
| two pointers on an unsorted list | None although 200 + 800 = 1000 |
the moves rely on order | sort first, or use a set |
| moving the taller wall | misses the best tank | the short wall still caps the water | move the shorter wall |
range(len(sales) - k) |
16 instead of 18 |
misses the last window | n - k + 1 windows: range(k, n) when sliding |
sum(sales[i:i + k]) per window |
seconds for 50,000 days | O(n · k) | slide: + sales[i] - sales[i - k] |
best = 0 to start |
0 for all-negative sales |
0 isn't a real window | start from the first window's sum |
no check for k > len(sales) |
a wrong "best" or an error | there is no window | return None |
Your turn: the shortest streak to a target (solution)
Question: the fewest days in a row whose sales add up to at least a target (0 if impossible). For [2, 3, 1, 2, 4, 3] and 7, the answer is 2 (4 + 3).
Idea: a variable-size window. Grow it on the right; while the total is big enough, record its length and shrink it from the left. Each day enters once and leaves once: O(n). (This works because sales are never negative.)
def shortest_streak(sales, target):
best = float("inf")
total = left = 0
for right, x in enumerate(sales):
total += x
while total >= target:
best = min(best, right - left + 1)
total -= sales[left]
left += 1
return 0 if best == float("inf") else best
print(shortest_streak([2, 3, 1, 2, 4, 3], 7), shortest_streak([1, 1], 5), shortest_streak([8], 7))
Output:
2 0 1
Mini project: a Diwali sales report
Both window kinds in one small report: the best fixed 3-day stretch and the shortest streak that reaches a target.
def sales_report(sales, k, target):
"""Best k-day stretch (fixed window) and the shortest streak reaching
a target (variable window), both in one pass each."""
window = sum(sales[:k])
best, best_start = window, 0
for i in range(k, len(sales)):
window += sales[i] - sales[i - k]
if window > best:
best, best_start = window, i - k + 1
shortest, total, left = None, 0, 0
for right, x in enumerate(sales):
total += x
while total >= target:
if shortest is None or right - left + 1 < shortest[1] - shortest[0] + 1:
shortest = (left, right)
total -= sales[left]
left += 1
return best, best_start, shortest
diwali = [12, 18, 25, 40, 55, 30, 20, 15] # thousands of rupees
best, start, streak = sales_report(diwali, 3, 90)
print(f"best 3 days: {best} (days {start + 1} to {start + 3})")
print(f"shortest streak to 90: days {streak[0] + 1} to {streak[1] + 1}")
Output:
best 3 days: 125 (days 4 to 6)
shortest streak to 90: days 4 to 5
Practice questions (with solutions)
1. Three numbers that sum to zero (all unique triples).
Solution
Sort, fix the first number, then run two pointers on the rest. Skip repeated values so each triple appears once. O(n²), much better than O(n³).
def three_sum_zero(nums):
nums = sorted(nums)
found = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue # skip repeated first numbers
left, right = i + 1, len(nums) - 1
while left < right:
s = nums[i] + nums[left] + nums[right]
if s < 0:
left += 1
elif s > 0:
right -= 1
else:
found.append((nums[i], nums[left], nums[right]))
left += 1
while left < right and nums[left] == nums[left - 1]:
left += 1
return found
print(three_sum_zero([-1, 0, 1, 2, -1, -4]))
print(three_sum_zero([0, 0, 0, 0]), three_sum_zero([1, 2]))
Output:
[(-1, -1, 2), (-1, 0, 1)]
[(0, 0, 0)] []
2. Remove duplicates from a sorted list in place.
Solution
Two pointers moving the same direction: read scans every item, write marks where the next new value goes. O(n) time, O(1) extra space.
def remove_duplicates(nums):
"""Sorted list: keep one of each in place, return the new length."""
if not nums:
return 0
write = 1 # slow pointer: where to write
for read in range(1, len(nums)): # fast pointer: what we read
if nums[read] != nums[read - 1]:
nums[write] = nums[read]
write += 1
del nums[write:]
return write
a = [1, 1, 2, 3, 3, 3, 7]
print(remove_duplicates(a), a)
b = []
print(remove_duplicates(b), b)
Output:
4 [1, 2, 3, 7]
0 []
3. Squares of a sorted list (it may contain negatives), in sorted order, in O(n).
Solution
The biggest square is at one of the two ends. Fill the result from the back with two pointers.
def sorted_squares(nums):
"""nums is sorted (may have negatives): squares in sorted order, O(n)."""
result = [0] * len(nums)
left, right = 0, len(nums) - 1
for pos in range(len(nums) - 1, -1, -1): # fill from the biggest
if abs(nums[left]) > abs(nums[right]):
result[pos] = nums[left] ** 2
left += 1
else:
result[pos] = nums[right] ** 2
right -= 1
return result
print(sorted_squares([-7, -3, 0, 2, 5]))
Output:
[0, 4, 9, 25, 49]
4. Longest substring without repeating characters (episode 14, as a sliding window).
Solution
Remember where each character was last seen; when it repeats inside the window, move the window's start past it. O(n).
def longest_unique(s):
last_seen = {}
best = start = 0
for i, ch in enumerate(s):
if ch in last_seen and last_seen[ch] >= start:
start = last_seen[ch] + 1 # shrink past the repeat
last_seen[ch] = i
best = max(best, i - start + 1)
return best
print(longest_unique("abcabcbb"), longest_unique("pwwkew"), longest_unique(""))
Output:
3 3 0
Quick quiz
What does this print?
nums = [1, 2, 3, 4, 6]
left, right, steps = 0, len(nums) - 1, 0
while left < right:
s = nums[left] + nums[right]
if s == 6:
break
steps += 1
if s < 6: left += 1
else: right -= 1
print(nums[left], nums[right], steps)
(A) 2 4 2 (B) 1 6 0 (C) 2 4 1 (D) 3 3 2
Answer
(A). 1 + 6 = 7 is too big: right moves to 4 (1 step). 1 + 4 = 5 is too small: left moves to 2 (2 steps). 2 + 4 = 6: break.
nums = [1, 2, 3, 4, 6]
left, right, steps = 0, len(nums) - 1, 0
while left < right:
s = nums[left] + nums[right]
if s == 6:
break
steps += 1
if s < 6: left += 1
else: right -= 1
print(nums[left], nums[right], steps)
Output:
2 4 2
Interview questions
- When can you use two pointers? When the data is sorted (or has some order) so that each comparison tells you which side can be ruled out; also for in-place problems with a read and a write pointer.
- Why is pair-sum with two pointers correct? Each move discards a value that cannot be part of any answer with the remaining values, so no valid pair is skipped.
- Two pointers vs a hash set for pair sum? Two pointers: O(n) time, O(1) space, needs sorted input. Set: O(n) time, O(n) space, works unsorted.
- Why move the shorter wall in the container problem? Moving the taller one can never increase the water: the width shrinks and the height is still capped by the shorter wall.
- Fixed vs variable sliding window? Fixed: k items, add one and remove one each step. Variable: grow on the right, shrink on the left while a condition holds.
- Why does the variable window need non-negative numbers? Shrinking must make the total smaller; with negatives that's not guaranteed (use prefix sums instead).
- How many windows of size k are in n items? n - k + 1.
- What is an off-by-one error? A loop or index that's one too many or one too few, like
range(n - k)instead ofrange(n - k + 1). - Complexity of 3-sum with sorting and two pointers? O(n²) time, O(1) extra space (besides the output and the sort).
- Where else do sliding windows appear? Moving averages, rate limiting (requests in the last minute), longest substring problems, and network protocols.
Glossary
| Term | Meaning | Example |
|---|---|---|
| Pointer (index) | A variable holding a position in a list | left, right |
| Two pointers | Two positions moving through the data | both ends of a sorted list |
| Sorted | In increasing order | 150, 200, 350 |
| Target sum | The value two items must add up to | 1,000 rupees |
left < right |
Two different positions | stop when they meet |
| Container with most water | Two walls, water = shorter × width | 49 |
min() |
The smaller value | min(8, 7) |
| Window | A block of consecutive items | 3 days in a row |
| Sliding window | A window moved one step at a time and updated | + in - out |
| Fixed / variable window | Same size every step / grows and shrinks | max sum of k / shortest streak |
| Consecutive | Next to each other, in order | days 4, 5, 6 |
| Off-by-one error | A loop bound that's one too short or long | range(n - k) |
range(k, n) |
Indexes k, k + 1, ..., n - 1 | the incoming days |
| Read / write pointer | Two pointers moving the same way | remove duplicates |
| In place | Changing the list itself, no copy | del nums[write:] |
| O(n · k) | Time grows with n times k | summing every slice |
| O(n²) | Double n, about 4× the time | all pairs |
| O(n) | One pass | two pointers, sliding window |
| Amortised | Average cost over all steps | each day enters and leaves once |
Summary
- Two pointers on a sorted list: start at both ends; too small →
left += 1, too big →right -= 1;while left < rightfor two different items. O(n) time, O(1) space. Unsorted input breaks it. - Container with most water: start widest and always move the shorter wall: O(n).
- Sliding window: there are n - k + 1 windows; sum the first once, then add the item coming in and subtract the item going out: O(n) instead of O(n · k). Handle
k > nand negative values. - A variable window (grow right, shrink left) finds the shortest streak reaching a target.
- Next episode: dynamic programming questions: climbing stairs, coin change (where greedy fails), and the longest common subsequence.