SyntaxPilot
Courses/Python Coding Questions/Lesson 26
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Python Coding Questions · Lesson 26 of 30

Two pointers and sliding window

pair with a target sum in a sorted listcontainer with most watermax sum of k consecutive items

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 left and right) 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:

  1. window = sum(sales[:k]) once.
  2. For each new day i from k to the end: window += sales[i] - sales[i - k] (add the day coming in, subtract the day leaving).
  3. Keep the best. If k > len(sales), there is no window: return None.

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

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. 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).
  7. How many windows of size k are in n items? n - k + 1.
  8. 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 of range(n - k + 1).
  9. Complexity of 3-sum with sorting and two pointers? O(n²) time, O(1) extra space (besides the output and the sort).
  10. 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 < right for 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 > n and 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.