Two Pointers and Sliding Window

Two pointers

def is_palindrome(text):
    """Compare from both ends inward. O(n) time, O(1) space."""
    cleaned = [c.lower() for c in text if c.isalnum()]
    left, right = 0, len(cleaned) - 1

    while left < right:
        if cleaned[left] != cleaned[right]:
            return False
        left += 1
        right -= 1

    return True


print(is_palindrome("A man, a plan, a canal: Panama"))     # True
print(is_palindrome("hello"))                               # False

a m a n a p l a n ...
^                 ^
left            right     compare, then move both inward

Two sum on sorted data

def two_sum_sorted(numbers, target):
    """O(n) time, O(1) space - no dictionary needed when sorted."""
    left, right = 0, len(numbers) - 1

    while left < right:
        total = numbers[left] + numbers[right]
        if total == target:
            return left, right
        if total < target:
            left += 1                 # need a larger total
        else:
            right -= 1                # need a smaller total

    return None


print(two_sum_sorted([1, 3, 4, 6, 8, 11], 10))     # (2, 4)
print(two_sum_sorted([1, 2, 3], 100))               # None

The hash based version uses O(n) memory and works on unsorted data. This one uses O(1) memory and requires sorted data. Which is better depends entirely on what you already have.

Three sum

def three_sum(numbers):
    """Every triple summing to zero, without duplicates. O(n^2)."""
    values = sorted(numbers)
    results = []

    for i in range(len(values) - 2):
        if i > 0 and values[i] == values[i - 1]:
            continue                              # skip a duplicate first value

        left, right = i + 1, len(values) - 1
        while left < right:
            total = values[i] + values[left] + values[right]
            if total == 0:
                results.append((values[i], values[left], values[right]))
                while left < right and values[left] == values[left + 1]:
                    left += 1
                while left < right and values[right] == values[right - 1]:
                    right -= 1
                left += 1
                right -= 1
            elif total < 0:
                left += 1
            else:
                right -= 1

    return results


print(three_sum([-1, 0, 1, 2, -1, -4]))

Removing duplicates in place

def remove_duplicates(values):
    """A sorted list, deduplicated in place. Returns the new length."""
    if not values:
        return 0

    write = 1
    for read in range(1, len(values)):
        if values[read] != values[write - 1]:
            values[write] = values[read]
            write += 1

    return write


data = [1, 1, 2, 2, 2, 3, 4, 4]
length = remove_duplicates(data)
print(length, data[:length])                # 4 [1, 2, 3, 4]

A read pointer and a write pointer moving at different speeds. This shape appears constantly: filtering, compacting and partitioning all use it.

Merging two sorted lists

def merge_sorted(first, second):
    """One pointer per list. O(n + m)."""
    result = []
    i = j = 0

    while i < len(first) and j < len(second):
        if first[i] <= second[j]:
            result.append(first[i])
            i += 1
        else:
            result.append(second[j])
            j += 1

    result.extend(first[i:])
    result.extend(second[j:])
    return result


print(merge_sorted([1, 4, 7], [2, 3, 8, 9]))

import heapq
print(list(heapq.merge([1, 4, 7], [2, 3, 8, 9])))     # the standard library version

Container with the most water

def max_area(heights):
    """The largest rectangle between two lines. O(n)."""
    left, right = 0, len(heights) - 1
    best = 0

    while left < right:
        area = min(heights[left], heights[right]) * (right - left)
        best = max(best, area)
        if heights[left] < heights[right]:
            left += 1                 # only moving the shorter side can help
        else:
            right -= 1

    return best


print(max_area([1, 8, 6, 2, 5, 4, 8, 3, 7]))     # 49

Sliding window: fixed size

def max_sum_window(numbers, k):
    """The largest sum of k consecutive values. O(n)."""
    if len(numbers) < k:
        return None

    window = sum(numbers[:k])
    best = window

    for i in range(k, len(numbers)):
        window += numbers[i] - numbers[i - k]      # add one, remove one
        best = max(best, window)

    return best


print(max_sum_window([2, 1, 5, 1, 3, 2], 3))       # 9

[2, 1, 5, 1, 3, 2]   k = 3
 [------]             sum 8
    [------]          sum 7      = 8 - 2 + 1
       [------]       sum 9      = 7 - 1 + 3
          [------]    sum 6      = 9 - 5 + 2

Each step is one addition and one subtraction, not a fresh sum.

from collections import deque


def moving_average(numbers, k):
    """The average of every window of k values."""
    window = deque(maxlen=k)
    result = []

    for value in numbers:
        window.append(value)
        if len(window) == k:
            result.append(sum(window) / k)

    return result


print([round(v, 2) for v in moving_average([1, 2, 3, 4, 5, 6], 3)])

Sliding window: variable size

def smallest_window_with_sum(numbers, target):
    """The shortest run of positive numbers summing to at least target. O(n)."""
    start = 0
    total = 0
    best = float("inf")
    best_range = None

    for end, value in enumerate(numbers):
        total += value                                # grow to the right

        while total >= target:                        # shrink from the left
            if end - start + 1 < best:
                best = end - start + 1
                best_range = (start, end)
            total -= numbers[start]
            start += 1

    return best_range


print(smallest_window_with_sum([2, 3, 1, 2, 4, 3], 7))     # (4, 5)

grow the window until the condition holds,
then shrink it from the left while it still holds.

Each index enters the window once and leaves once -> O(n), not O(n^2).

def longest_unique_substring(text):
    """The longest run with no repeated character. O(n)."""
    seen = {}
    start = best = best_start = 0

    for end, character in enumerate(text):
        if character in seen and seen[character] >= start:
            start = seen[character] + 1               # jump past the repeat
        seen[character] = end

        if end - start + 1 > best:
            best = end - start + 1
            best_start = start

    return text[best_start:best_start + best]


print(longest_unique_substring("abcabcbb"))      # abc
print(longest_unique_substring("pwwkew"))        # wke

from collections import defaultdict


def longest_with_k_distinct(text, k):
    """The longest run containing at most k distinct characters."""
    counts = defaultdict(int)
    start = best = best_start = 0

    for end, character in enumerate(text):
        counts[character] += 1

        while len(counts) > k:
            counts[text[start]] -= 1
            if counts[text[start]] == 0:
                del counts[text[start]]
            start += 1

        if end - start + 1 > best:
            best = end - start + 1
            best_start = start

    return text[best_start:best_start + best]


print(longest_with_k_distinct("eceba", 2))       # ece
print(longest_with_k_distinct("aabbcc", 2))      # aabb

Finding all anagrams

from collections import Counter


def find_anagrams(text, pattern):
    """Every start index where an anagram of pattern appears. O(n)."""
    if len(pattern) > len(text):
        return []

    needed = Counter(pattern)
    window = Counter(text[:len(pattern)])
    results = [0] if window == needed else []

    for i in range(len(pattern), len(text)):
        window[text[i]] += 1
        left = text[i - len(pattern)]
        window[left] -= 1
        if window[left] == 0:
            del window[left]
        if window == needed:
            results.append(i - len(pattern) + 1)

    return results


print(find_anagrams("cbaebabacd", "abc"))        # [0, 6]

Recognising the pattern

Fast and slow pointers

def has_cycle(head):
    """Floyd's algorithm. O(n) time, O(1) space."""
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False


def find_duplicate(numbers):
    """One duplicate among 1..n, treating the list as a linked list."""
    slow = fast = numbers[0]
    while True:
        slow = numbers[slow]
        fast = numbers[numbers[fast]]
        if slow == fast:
            break

    slow = numbers[0]
    while slow != fast:
        slow = numbers[slow]
        fast = numbers[fast]
    return slow


print(find_duplicate([1, 3, 4, 2, 2]))     # 2

Why these are O(n)

# A nested loop: every pair is examined
def brute_force(numbers, target):
    for i in range(len(numbers)):
        for j in range(i + 1, len(numbers)):        # n * n / 2 comparisons
            if numbers[i] + numbers[j] == target:
                return i, j


# Two pointers: each index is visited at most once by each pointer
def two_pointers(numbers, target):
    left, right = 0, len(numbers) - 1
    while left < right:                              # at most n steps total
        ...

In a sliding window, start and end each move forward only, and never past the end. The inner while looks like a nested loop but cannot run more than n times in total across the whole outer loop. That is the amortised argument, and it is what makes the technique linear.

Common mistakes

• Using two pointers on unsorted data where sorting is required.
• Writing while left <= right when the two must be distinct.
• Forgetting to move a pointer, causing an infinite loop.
• Recomputing the whole window sum instead of adding and subtracting.
• Not removing a key when its count reaches zero, so len(counts) is wrong.
• Off by one in the window length: it is end - start + 1.
• Applying a sliding window to a problem with negative numbers where shrinking is not valid.

Best practices

• Draw the pointers on a small example before writing the loop.
• Decide explicitly what the window invariant is, and restore it in the inner loop.
• Update the running total incrementally.
• Test with an empty input, one element, and a case where nothing qualifies.
• Remember two pointers on sorted data uses O(1) space where hashing uses O(n).

Practice

1. Move every zero in a list to the end, in place, keeping the other values in order.
2. Find the pair in a sorted list whose sum is closest to a target.
3. Find the longest run of consecutive equal values.
4. Find the smallest window in a string containing every character of a pattern.
5. Find the maximum in every window of size k, and state the complexity of your solution.

Conclusion

Two pointers and sliding windows both replace a nested loop with a single pass by never moving backwards. Look for them whenever a problem says "contiguous", "pair", "longest run" or "at most k" - and whenever your first solution is O(n²).