Two Pointers and Sliding Window: Patterns for Array Problems

The idea in one minute

Checking "every element against every other" means two nested loops and O(n²). Both patterns remove the inner loop:

• Two pointers — two indexes that move through the array toward each other, or in the same direction at different speeds.
• Sliding window — a contiguous range [left, right] that grows on the right and shrinks on the left, while the value you track (a sum, character counts) is updated in O(1).

The key insight: each pointer only moves forward and takes at most n steps, so the total work is O(n).

How to recognize the pattern

If the range need not be contiguous, or the array has negative numbers and the condition is about a sum, a window usually fails — look at prefix sums or hash maps instead.

Problem 1. Pair with a given sum in a sorted array

Brute force checks every pair — O(n²). With two pointers: if the sum is too small, move the left one right; if too large, move the right one left.

def pair_with_sum(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        s = nums[left] + nums[right]
        if s == target:
            return left, right
        if s < target:
            left += 1
        else:
            right -= 1
    return None

Time O(n), memory O(1). It works only because the array is sorted: each pointer move safely discards pairs that cannot match.

Problem 2. Remove duplicates from a sorted array in place

The slow pointer write marks where the next unique element goes; the fast pointer read scans the array.

def dedupe_sorted(nums):
    if not nums:
        return 0
    write = 1
    for read in range(1, len(nums)):
        if nums[read] != nums[write - 1]:
            nums[write] = nums[read]
            write += 1
    return write  # length of the unique part

Time O(n), memory O(1) — no new list is created.

Problem 3. Maximum sum of a subarray of length k

Brute force recomputes each window's sum — O(n·k). With a fixed-size window, add the incoming element and subtract the outgoing one on each shift.

def max_sum_k(nums, k):
    window = sum(nums[:k])
    best = window
    for i in range(k, len(nums)):
        window += nums[i] - nums[i - k]
        best = max(best, window)
    return best

Time O(n). Assumes 1 <= k <= len(nums).

Problem 4. Longest substring without repeating characters

A variable-size window: grow on the right, and when a character repeats, move the left edge past its previous occurrence.

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
        last_seen[ch] = right
        best = max(best, right - left + 1)
    return best

Checking every substring for uniqueness is O(n²) or worse. Here each index is visited once: O(n) time and memory proportional to the alphabet size.

Problem 5. Shortest subarray with sum at least target

Numbers are positive. Grow the window while the sum is below target, then shrink from the left while the condition holds, recording the minimum length.

def min_len_subarray(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

The nested while does not make it quadratic: left moves at most n times over the whole run, so the total is O(n).

Variable-window template

1. Move right through the array and add the element to the window state.
2. While the window breaks the condition (or meets it, when looking for a minimum), move left and remove that element from the state.
3. Update the answer after each step.

Common mistakes

• Using a window for sum problems with negative numbers — shrinking from the left no longer guarantees a smaller sum.
• Forgetting the empty array and k > len(nums).
• Off-by-one errors in window length: it is right - left + 1.
• In problem 4, not checking that the previous occurrence is inside the current window.