Common patterns

Why it matters

Most array and string problems you meet at work or in interviews are not new. They are variations on a handful of patterns. Recognising the pattern is usually the hard part; the code is short once you see it. Two of the most useful are two pointers and sliding window. Both turn a brute-force "check every pair" or "check every subarray" solution, which is O(n^2) or worse, into a single O(n) pass.

Pattern 1: two pointers

Keep two indexes into the same list and move them toward each other (or in the same direction) based on what you see. It works when the data has an order you can exploit, usually because it is sorted.

Example: pair with a given sum in a sorted list. Find two numbers in [1, 3, 4, 6, 8, 11] that add to 10.

Brute force tries every pair: O(n^2). With two pointers, start at both ends:

def pair_with_sum(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        total = nums[left] + nums[right]
        if total == target:
            return (left, right)
        if total < target:
            left += 1        # need a bigger sum: move the small end up
        else:
            right -= 1       # need a smaller sum: move the big end down
    return None

Why is it safe to skip pairs? If nums[left] + nums[right] is too small, then pairing nums[left] with anything left of right is even smaller, so nums[left] can never be part of the answer. Each step rules out a whole row of pairs. At most n steps: O(n) time and O(1) space. (For an unsorted list, use the dict approach from the hash maps lesson instead.)

Other two-pointer problems: checking a palindrome (compare the ends and move inward), removing duplicates from a sorted list in place, and merging two sorted lists (which you already did in merge sort).

Pattern 2: sliding window

A window is a stretch of consecutive items, nums[start:end]. Instead of recomputing each window from scratch, slide it one step and update the answer using only what entered and what left.

Fixed size: maximum sum of k consecutive items. For [2, 1, 5, 1, 3, 2] and k = 3, the windows are [2,1,5]=8, [1,5,1]=7, [5,1,3]=9, [1,3,2]=6, so the answer is 9.

Recomputing each sum is O(n x k). Sliding is O(n):

def max_window_sum(nums, k):
    if k <= 0 or k > len(nums):
        return None
    window = sum(nums[:k])
    best = window
    for i in range(k, len(nums)):
        window += nums[i] - nums[i - k]   # add the new item, drop the old one
        best = max(best, window)
    return best

Variable size: longest substring without repeating characters. Grow the window on the right; when a repeat appears, shrink it from the left until the window is valid again.

def longest_unique(s):
    last_seen = {}
    start = 0
    best = 0
    for end, ch in enumerate(s):
        if ch in last_seen and last_seen[ch] >= start:
            start = last_seen[ch] + 1     # jump past the earlier copy
        last_seen[ch] = end
        best = max(best, end - start + 1)
    return best

longest_unique("abcabcbb")   # 3 ("abc")
longest_unique("pwwkew")     # 3 ("wke")

Each character enters and leaves the window at most once: O(n).

How to spot them

Patterns are a starting point, not a rule. Always write the brute-force idea first in one sentence. It gives you a correct baseline and a set of answers to test the faster version against.

Common mistakes

• Using two pointers on unsorted data for a sum problem. Moving a pointer only makes sense if you know which way the sum will change.
• while left <= right in pair problems, which lets an item pair with itself.
• Not handling k > len(nums) or an empty list in window problems.
• Off-by-one window length. A window from start to end inclusive has end - start + 1 items.
• Moving start backwards in the variable window. That is why the code checks last_seen[ch] >= start.

Quick recap

• Two pointers: two indexes that move based on a comparison; usually needs sorted input; O(n), O(1) space.
• Sliding window: update a running answer as items enter and leave; O(n).
• Start from the brute force, look for the clue, then apply the pattern and test edge cases.

Try it

The Do tab has three functions: a two-pointer pair search, a fixed sliding window and the longest substring without repeats. The checks compare against brute force on random inputs.