Two pointers and sliding window, worked through a real problem

Two closely related patterns for avoiding nested loops on arrays and strings, worked from brute force to the optimal solution on a real problem each.

Intermediate

3 min read

Two pointers — for sorted, pair-finding problems

Problem: given a sorted array, find two numbers that add up to a target.

def two_sum_sorted_brute(nums, target):    # O(n^2)
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
 
def two_sum_sorted_fast(nums, target):     # O(n)
    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     # sum too small — the only way to grow it is move left pointer up
        else:
            right -= 1    # sum too large — the only way to shrink it is move right pointer down

The two-pointer version exploits the sortedness directly: start at both ends, and the direction to move is never ambiguous — if the current pair sums too low, the only lever that can increase the sum is moving left forward (since the array is sorted, every element to the right of left is ≥ nums[left]); if it sums too high, only moving right backward can decrease it. Each pointer moves at most n times total across the whole run, giving O(n) instead of checking every pair.

Sliding window — for contiguous subarray/substring problems

Problem: find the length of the longest substring without repeating characters.

def longest_unique_substring(s):
    seen = set()
    left = 0
    longest = 0
    for right in range(len(s)):
        while s[right] in seen:
            seen.remove(s[left])
            left += 1
        seen.add(s[right])
        longest = max(longest, right - left + 1)
    return longest

right expands the window one character at a time. The moment the new character is already in the current window (s[right] in seen), the window shrinks from the left — removing characters until the duplicate is gone — before continuing to expand. Every character enters and leaves the window at most once across the entire run, which is what keeps this O(n) instead of the O(n^2) of checking every possible substring explicitly.

The shape that tells you which pattern applies

Both patterns replace "check every pair/every substring" (O(n^2)) with a single pass where two pointers do useful, non-redundant work. The distinguishing signal:

Two pointers, from both ends inward — the input is sorted (or can be sorted), and you're looking for a pair satisfying some condition.
Sliding window, both pointers moving forward — you're looking for a contiguous run (subarray or substring) satisfying some condition, and "shrink from the left when a condition is violated" is a meaningful operation.

Neither pattern requires extra memory proportional to the input the way the hash-map pattern does — that's the trade being made here: sliding window and two pointers save the O(n) space a hash map would cost, at the price of requiring the specific structure (sortedness, or a well-defined "shrink the window" rule) that makes the two-pointer movement valid in the first place.

Two pointers and sliding window, worked through a real problem

Two pointers — for sorted, pair-finding problems

Sliding window — for contiguous subarray/substring problems

The shape that tells you which pattern applies

Further reading