Two Pointers & Sliding Window

You've now covered every core data structure and traversal technique in this track. The next four lessons cover patterns — reusable strategies that combine those building blocks to solve entire families of problems efficiently. We'll start with two of the most common: the two pointers technique and its close cousin, the sliding window. Both trade a naive O(n²) nested loop for a single O(n) pass by moving one or two indices through a list intelligently instead of re-scanning it from scratch.

Two Pointers: The Idea

Worked Example: Two-Sum on a Sorted List

Recall the "Two Sum" problem from the hashing lesson: given a list and a target, find two indices whose values sum to the target. The dict solution there ran in O(n) time and O(n) space and worked on an unsorted list. If the list is already sorted, two pointers solves it in O(n) time but only O(1) extra space — no dict needed at all.

The idea: start one pointer left at index 0 and another right at the last index. If the sum of the two values is too small, the only way to increase it is to move left forward (since the list is sorted, that guarantees a larger or equal value). If the sum is too large, move right backward. The pointers converge toward each other, and every step eliminates one candidate pair for good — that's what keeps it linear.

# nums is sorted ascending. Returns the indices of the pair, or None if none exists.
def two_sum_sorted(nums, target):
    left, right = 0, len(nums) - 1

    while left < right:
        total = nums[left] + nums[right]
        if total == target:
            return [left, right]
        elif total < target:
            left += 1   # need a bigger sum
        else:
            right -= 1  # need a smaller sum

    return None  # no pair found

Time complexity: O(n) — the two pointers together cover at most n steps before they meet; no element is ever revisited. Space complexity: O(1) — only two index variables, no auxiliary structure.

Sliding Window: The Idea

Worked Example: Maximum Sum Subarray of Size K (Fixed Window)

Brute force recomputes the sum of every window of size K from scratch: O(n·K) time. A sliding window instead keeps a running sum, adding the element entering the window on the right and subtracting the element leaving it on the left, so each slide is O(1) instead of O(K).

def max_sum_subarray_of_size_k(nums, k):
    window_sum = sum(nums[:k])  # build the first window
    max_sum = window_sum

    for end in range(k, len(nums)):
        window_sum += nums[end] - nums[end - k]  # slide: add right, drop left
        max_sum = max(max_sum, window_sum)

    return max_sum

Time complexity: O(n) — building the first window with sum(nums[:k]) costs O(k), then every subsequent slide is O(1), for a total of O(k + (n − k)) = O(n). Space complexity: O(1) — a running sum and a max variable, nothing that grows with input size.

Worked Example: Longest Substring Without Repeating Characters (Variable Window)

This is the more advanced sliding window shape: the window's size isn't fixed — it grows while a condition holds and shrinks when it's violated. Here the condition is "no repeated characters inside the window." We track the characters currently in the window with a set, expand right one character at a time, and whenever we'd introduce a duplicate, shrink from left until the duplicate is gone.

def length_of_longest_substring(s):
    window_chars = set()
    left = 0
    max_length = 0

    for right in range(len(s)):
        c = s[right]

        # shrink from the left until c is no longer a duplicate in the window
        while c in window_chars:
            window_chars.remove(s[left])
            left += 1

        window_chars.add(c)
        max_length = max(max_length, right - left + 1)

    return max_length

Time complexity: O(n) — although there's a nested while loop, left only ever moves forward and never resets, so across the whole run it advances at most n times total; combined with right's n steps, the total work is O(n), not O(n²). Space complexity: O(min(n, m)) where m is the size of the character set — the set holds at most one entry per distinct character currently in the window.

Recognizing Which Pattern Applies