Two Pointers and Sliding Window

Two pointers and sliding windows replace a nested loop with a single pass. Instead of trying every pair or every subarray, you keep two indexes into the data and move them cleverly, so that each element is visited a bounded number of times. When a problem involves a sorted array, a pair, a palindrome, or a contiguous subarray or substring with some property, this is usually the intended approach.

1. When this pattern applies

Two pointers fits when:

• The array (or string) is sorted, or can be sorted without hurting the answer.
• You are looking for a pair or triple satisfying a condition on their sum or difference.
• You need to compare things from both ends (palindromes).
• You are partitioning or removing items in place.

Sliding window fits when:

• The problem asks about a contiguous subarray or substring.
• You want the longest, shortest or count of windows satisfying a condition.
• The condition can be maintained incrementally as the window grows and shrinks.

The key question: "If I move one end, can I tell cheaply which end to move next?" If so, a single pass is possible.

2. Two pointers on a sorted array

Two sum II. In a sorted array, find two numbers that add up to a target.

Start with one pointer at each end. If the sum is too small, the left value is too small to be part of any answer with the current right value or anything smaller, so move left forward. If it is too large, move right backward. Each move discards an element for good.

def two_sum_sorted(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 []

assert two_sum_sorted([1, 3, 5, 7, 9, 11], 12) == [0, 5]
assert two_sum_sorted([2, 7, 11, 15], 9) == [0, 1]
assert two_sum_sorted([1, 2], 10) == []

Time $O(n)$, space $O(1)$. Compare with the hash map version: the same time, but constant memory, which is why interviewers like it when the array is already sorted.

3Sum. Find all unique triples summing to zero. Sort, fix one number, and run two pointers on the rest. Skip duplicates to keep the triples unique.

def three_sum(nums):
    nums.sort()
    result = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i - 1]:      # skip duplicate first elements
            continue
        left, right = i + 1, len(nums) - 1
        while left < right:
            s = nums[i] + nums[left] + nums[right]
            if s < 0:
                left += 1
            elif s > 0:
                right -= 1
            else:
                result.append([nums[i], nums[left], nums[right]])
                left += 1
                right -= 1
                while left < right and nums[left] == nums[left - 1]:   # skip duplicates
                    left += 1
    return result

assert three_sum([-1, 0, 1, 2, -1, -4]) == [[-1, -1, 2], [-1, 0, 1]]
assert three_sum([0, 0, 0, 0]) == [[0, 0, 0]]
assert three_sum([1, 2, 3]) == []

Time $O(n^2)$ (sort is $O(n\log n)$, then $n$ two-pointer passes), space $O(1)$ extra. You cannot beat $O(n^2)$ for 3Sum in general, and saying so shows understanding.

3. Two pointers from both ends

Valid palindrome. Compare characters from the outside in, skipping non-alphanumeric ones.

def is_palindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        while left < right and not s[left].isalnum():
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1
        if s[left].lower() != s[right].lower():
            return False
        left += 1
        right -= 1
    return True

assert is_palindrome("A man, a plan, a canal: Panama") is True
assert is_palindrome("race a car") is False
assert is_palindrome("") is True

Container with most water. Given vertical lines of heights, choose two to hold the most water. The area is min(height) * width. Start with the widest pair. Moving the taller line inward cannot help, because the width shrinks and the height is limited by the shorter line. So always move the shorter one.

def max_area(height):
    left, right = 0, len(height) - 1
    best = 0
    while left < right:
        best = max(best, min(height[left], height[right]) * (right - left))
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    return best

assert max_area([1, 8, 6, 2, 5, 4, 8, 3, 7]) == 49
assert max_area([1, 1]) == 1

The pattern to notice is the justification for which pointer moves. State it in the interview: "moving the taller side can only reduce or keep the area, so I move the shorter side."

Trapping rain water. Water above a bar is min(max_left, max_right) - height. With two pointers, always advance the side with the smaller maximum, because that side's water level is already determined by its own maximum.

def trap(height):
    left, right = 0, len(height) - 1
    left_max = right_max = water = 0
    while left < right:
        if height[left] < height[right]:
            left_max = max(left_max, height[left])
            water += left_max - height[left]
            left += 1
        else:
            right_max = max(right_max, height[right])
            water += right_max - height[right]
            right -= 1
    return water

assert trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]) == 6
assert trap([4, 2, 0, 3, 2, 5]) == 9

4. Same-direction pointers: partitioning in place

A read pointer scans every element, and a write pointer marks where the next kept element goes.

Remove duplicates from a sorted array in place.

def remove_duplicates(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              # the first `write` entries are the unique values

nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
k = remove_duplicates(nums)
assert k == 5 and nums[:k] == [0, 1, 2, 3, 4]

Sort colours (Dutch national flag). Sort an array of 0s, 1s and 2s in one pass with three pointers: everything before low is 0, everything after high is 2, and mid scans the unknown middle.

def sort_colors(nums):
    low, mid, high = 0, 0, len(nums) - 1
    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1            # do not advance mid: the swapped-in value is unexamined
    return nums

assert sort_colors([2, 0, 2, 1, 1, 0]) == [0, 0, 1, 1, 2, 2]
assert sort_colors([2, 0, 1]) == [0, 1, 2]

5. Fast and slow pointers

Two pointers moving at different speeds detect structure, such as cycles. This is most often used on linked lists, covered in its own chapter, and also appears on arrays, for example the "find the duplicate number" problem, where the array values act as next pointers.

6. Sliding window

A window is a contiguous range [left, right]. Expanding right adds an element, contracting left removes one. If you can update the window's state in $O(1)$ when an element enters or leaves, the whole pass is $O(n)$.

Fixed-size window

Maximum sum of a subarray of size $k$. Slide the window one step at a time: add the new element, subtract the one that left.

def max_sum_window(nums, k):
    window = sum(nums[:k])
    best = window
    for i in range(k, len(nums)):
        window += nums[i] - nums[i - k]      # add the entering element, drop the leaving one
        best = max(best, window)
    return best

assert max_sum_window([2, 1, 5, 1, 3, 2], 3) == 9
assert max_sum_window([4], 1) == 4

Variable-size window: the template

When the window size is not fixed, grow right every step and shrink left while the window is invalid (for "longest" problems), or shrink while it is still valid to find the smallest (for "shortest" problems).

Longest substring without repeating characters. Keep the last index of each character. If the new character already appears inside the window, jump left past its previous position.

def length_of_longest_substring(s):
    last = {}
    left = best = 0
    for right, ch in enumerate(s):
        if ch in last and last[ch] >= left:
            left = last[ch] + 1              # shrink the window past the repeat
        last[ch] = right
        best = max(best, right - left + 1)
    return best

assert length_of_longest_substring("abcabcbb") == 3
assert length_of_longest_substring("bbbbb") == 1
assert length_of_longest_substring("pwwkew") == 3
assert length_of_longest_substring("") == 0

Longest repeating character replacement. Replace at most $k$ characters to make the longest run of one letter. A window is valid if window_length - count_of_most_frequent_char <= k. The window never needs to shrink below its best size, so a common trick is to let it slide rather than strictly shrink.

from collections import defaultdict

def character_replacement(s, k):
    count = defaultdict(int)
    left = best = max_freq = 0
    for right, ch in enumerate(s):
        count[ch] += 1
        max_freq = max(max_freq, count[ch])
        while (right - left + 1) - max_freq > k:     # too many replacements needed
            count[s[left]] -= 1
            left += 1
        best = max(best, right - left + 1)
    return best

assert character_replacement("ABAB", 2) == 4
assert character_replacement("AABABBA", 1) == 4

Minimum size subarray sum. Shortest subarray whose sum is at least a target, for positive numbers. Grow until valid, then shrink as far as it stays valid, recording the length each time.

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

assert min_subarray_len(7, [2, 3, 1, 2, 4, 3]) == 2
assert min_subarray_len(11, [1, 1, 1, 1]) == 0

This only works when numbers are positive, so that growing the window increases the sum and shrinking decreases it. With negatives, use prefix sums and a map, as in the arrays chapter.

Minimum window substring (the classic hard one). Find the smallest window of s that contains every character of t, with multiplicities. Track how many distinct required characters are currently satisfied.

from collections import Counter

def min_window(s, t):
    if not s or not t:
        return ""
    need = Counter(t)
    missing = len(need)                  # distinct characters still not satisfied
    left = 0
    best = (float("inf"), 0, 0)
    for right, ch in enumerate(s):
        if ch in need:
            need[ch] -= 1
            if need[ch] == 0:
                missing -= 1
        while missing == 0:              # window contains all of t: shrink
            if right - left + 1 < best[0]:
                best = (right - left + 1, left, right)
            left_ch = s[left]
            if left_ch in need:
                need[left_ch] += 1
                if need[left_ch] > 0:
                    missing += 1
            left += 1
    return "" if best[0] == float("inf") else s[best[1]:best[2] + 1]

assert min_window("ADOBECODEBANC", "ABC") == "BANC"
assert min_window("a", "a") == "a"
assert min_window("a", "aa") == ""

Time $O(|s|+|t|)$: each index enters the window once and leaves once. Space $O(|t|)$.

7. Why the sliding window is linear

The while loop inside the for loop looks quadratic. It is not, because left only moves forward. Over the entire run, right moves at most $n$ times and left moves at most $n$ times, so the total number of steps is at most $2n$. State that argument explicitly when you analyse complexity.

8. Choosing among the techniques

9. Common mistakes

• Using a window when the condition is not monotonic. With negative numbers, extending the window can decrease the sum, so you cannot decide which end to move.
• Forgetting to skip duplicates in 3Sum and similar problems, producing repeated results.
• Moving the wrong pointer in the container problem. Always justify the choice.
• Off-by-one in the window length. The length is right - left + 1.
• Updating the best answer at the wrong time, such as before the window is valid.
• Not shrinking in a loop. After adding one element, several elements may need to leave, so use while, not if.
• Not sorting first when the two-pointer logic requires order. Remember sorting changes indexes, so if the problem returns original indexes, store them or use a map.

10. Practice set

1. Valid palindrome II (delete at most one character).
2. Two sum II, 3Sum, 4Sum (generalise with recursion).
3. Container with most water, trapping rain water.
4. Best time to buy and sell stock (a one-pass relative of the window idea).
5. Longest substring without repeating characters, longest repeating character replacement.
6. Permutation in string (a fixed window with counts).
7. Find all anagrams in a string.
8. Minimum window substring, then sliding window maximum (needs a deque, see the stacks chapter).
9. Subarrays with at most $k$ distinct integers (count windows, then use "at most $k$ minus at most $k-1$").
10. Maximum consecutive ones III (flip at most $k$ zeros).