Two Pointers and Sliding Window

Learn the two pointers and sliding window techniques in Python to turn O(n squared) array and string problems into clean O(n) solutions.

• Intermediate
• 18 min read
• 4 objectives

Before this lessonLesson 1: Searching

Many array and string problems have an obvious brute-force answer: try every pair, or every sub-array, with two nested loops. That is O(n²), and at a million elements it means a trillion steps. Two pointers and the sliding window are two closely related tricks that walk through the data once, moving two indexes in a disciplined way, and finish in O(n).

The key idea is that each pointer only ever moves forward (or only inward). Because neither pointer goes back, the total number of moves is at most 2n. The hard part is not the code; it is convincing yourself that skipping the pairs you never look at is safe. This lesson shows the reasoning for each pattern so you can apply it to new problems.

Pattern 1: opposite ends on a sorted array

Classic problem: given a sorted list of prices and a budget, find two items whose prices add up to exactly the budget. Put left at the start and right at the end. If the sum is too small, the only way to grow it is to move left right. If it is too big, move right left. Every step throws away one element that cannot be part of any answer.

def pair_with_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 a bigger sum
        else:
            right -= 1     # need a smaller sum
    return None

prices = [3, 8, 11, 15, 21, 30]
print(pair_with_sum(prices, 26))
print(pair_with_sum(prices, 7))

(11, 15)
None

Why is it safe to move left when the sum is too small? Because prices[right] is the largest value still in play. If even that cannot reach the target with prices[left], nothing else can either, so prices[left] is useless. Time O(n), space O(1). Compare this with a hash set approach (also O(n) time but O(n) space) which works on unsorted data.

Pattern 2: fast and slow pointers in one direction

Sometimes both pointers start at the left. A slow pointer marks where the next "kept" element should go, and a fast pointer scans ahead. This lets you filter or deduplicate a list in place without allocating a new one.

def dedupe_sorted(nums):
    if not nums:
        return 0
    slow = 0
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]
    return slow + 1          # length of the unique prefix

user_ids = [101, 101, 102, 105, 105, 105, 110]
k = dedupe_sorted(user_ids)
print(k, user_ids[:k])

4 [101, 102, 105, 110]

The same shape solves "move all zeros to the end", "remove every occurrence of a value" and, on linked lists, cycle detection (Floyd's tortoise and hare, where fast moves two nodes per step). Time O(n), space O(1).

Pattern 3: fixed-size sliding window

A window is a contiguous slice [left, right]. When the size is fixed, say the best 3-day sales total, you do not need to re-add all three numbers every time. Slide the window one step: add the element entering on the right and subtract the one leaving on the left.

def best_window_sum(values, k):
    window = sum(values[:k])
    best = window
    for right in range(k, len(values)):
        window += values[right] - values[right - k]
        best = max(best, window)
    return best

daily_orders = [4, 2, 12, 3, 8, 9, 1, 7]
print(best_window_sum(daily_orders, 3))

23

The naive version recomputes a k-element sum at each of n positions: O(n*k). The sliding version does O(1) work per step: time O(n), space O(1).

Pattern 4: variable-size sliding window

The most useful version grows and shrinks. The recipe: move right forward one step at a time to expand the window; while the window breaks a rule, move left forward to shrink it; after that, the window is valid, so record the answer. Example: the longest substring with no repeated characters.

def longest_unique(s):
    last_seen = {}
    left = best = 0
    for right, ch in enumerate(s):
        if ch in last_seen and last_seen[ch] >= left:
            left = last_seen[ch] + 1     # jump past the duplicate
        last_seen[ch] = right
        best = max(best, right - left + 1)
    return best

for word in ["stackcone", "abcabcbb", "bbbb", ""]:
    print(repr(word), longest_unique(word))

'stackcone' 5
'abcabcbb' 3
'bbbb' 1
'' 0

Another common one: the shortest sub-array whose sum is at least a target (all numbers positive). Expand until the sum is big enough, then shrink as far as you can while it stays big enough.

def shortest_subarray_at_least(nums, target):
    left = total = 0
    best = float("inf")
    for right, x in enumerate(nums):
        total += x
        while total >= target:
            best = min(best, right - left + 1)
            total -= nums[left]
            left += 1
    return 0 if best == float("inf") else best

print(shortest_subarray_at_least([2, 3, 1, 2, 4, 3], 7))
print(shortest_subarray_at_least([1, 1, 1], 10))

2
0

There is a while inside a for, yet this is still O(n): left only moves forward and can move at most n times in total across the whole run. This "amortised" argument is worth memorising because interviewers often ask about it.

How to spot these patterns

• Input is sorted, or sorting it is cheap and allowed: think opposite-end pointers.
• The question says contiguous sub-array or substring: think sliding window.
• You must modify a list in place with O(1) extra space: think slow/fast pointers.
• The brute force is a pair of nested loops over the same array: ask whether one pointer can skip work the other already ruled out.

Recap

• Two pointers replace nested loops by moving each index only one way, giving O(n) time.
• Opposite-end pointers need sorted data; each step discards an element that cannot be in any answer.
• Fixed windows update a running value by adding the new element and removing the old one.
• Variable windows expand with right, shrink with left while invalid, then record the answer.
• The while inside the loop is still O(n) overall because left never moves back.

# Write your solution here