Array Patterns: Two Pointers, Sliding Window and Prefix Sums

#Words Used in This Lesson

#The Slow Way First

Here is the shelf problem as code. For every pair of positions, add the two values and compare with the target. The function also counts how many pairs it checks. The target is too large to find, so it checks every pair.

def pair_sum_brute(nums, target):
    checks = 0
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            checks += 1
            if nums[i] + nums[j] == target:
                return (i, j), checks
    return None, checks


for n in (500, 1_000, 2_000):
    nums = list(range(1, n + 1))
    print(n, pair_sum_brute(nums, 10 * n)[1])
# Output:
# 500 124750
# 1000 499500
# 2000 1999000

Doubling n makes the work four times bigger. That is O(n²) time with O(1) extra space. The reason is the loop inside a loop: about n times n over 2 pairs. Every habit below exists to avoid looking at all those pairs.

#Two Pointers From Both Ends

The sum is 12 and the target is 10. Before you read on, decide which marker should move.

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


print(pair_sum_sorted([1, 3, 4, 6, 8, 11], 10))
print(pair_sum_sorted([1, 3, 4, 6, 8, 11], 100))
for n in (500, 1_000, 2_000):
    print(n, pair_sum_sorted(list(range(1, n + 1)), 10 * n)[1])
# Output:
# ((2, 3), 5)
# (None, 5)
# 500 499
# 1000 999
# 2000 1999

Same task, 1,999 steps against 1,999,000. The two markers start n - 1 apart and the gap shrinks by one on every step, so the loop runs at most n - 1 times. The time is O(n) and the extra space is O(1).

What if the list is not sorted? Sorting first costs O(n log n), and that cost then decides the total. It also moves the values, so the positions you return no longer match the original list. A dict that remembers each value seen so far avoids both problems. For each value, ask whether its partner is already in the dict.

def pair_sum_dict(nums, target):
    seen = {}
    for i, value in enumerate(nums):
        if target - value in seen:
            return (seen[target - value], i)
        seen[value] = i
    return None


print(pair_sum_dict([5, 1, 4, 9], 10))
# Output:
# (1, 3)

This is O(n) time on average and O(n) space, because the dict can grow to hold every value. The two pointers trade the dict's memory for the need for order.

#Palindromes

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


print(is_palindrome("A man, a plan, a canal: Panama"))
print(is_palindrome("racecar"))
print(is_palindrome("hello"))
print(is_palindrome(""))
# Output:
# True
# True
# False
# True

#Container With the Most Water

Here is a harder one. The numbers are heights of vertical walls, standing one unit apart. Pick two walls. The water between them is as wide as the gap and as high as the shorter wall. Which pair holds the most?

The gap is widest at the two ends, so start there. Now suppose you move the taller wall inwards. The gap gets smaller and the height is still limited by the shorter wall, so the water can only stay the same or shrink. Moving the taller wall can never help. Move the shorter one.

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


def max_water_brute(heights):
    return max(
        (j - i) * min(heights[i], heights[j])
        for i in range(len(heights))
        for j in range(i + 1, len(heights))
    )


heights = [1, 8, 6, 2, 5, 4, 8, 3, 7]
print(max_water(heights), max_water_brute(heights))
# Output:
# 49 49

The best pair is the wall of height 8 at index 1 and the wall of height 7 at index 8: a gap of 7 times a height of 7 is 49. This is O(n) time and O(1) space, against O(n²) for the brute force.

The list does not need to be sorted here. What makes it work is the argument about which side can be thrown away. Check that argument each time you meet a new two-pointer problem.

#Two Pointers in the Same Direction

Remove duplicates from a sorted list. The write pointer starts at 1, because the first value is always kept. For each value that the read pointer sees, if it differs from the last kept value, copy it to the write position and step the write pointer.

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


data = [1, 1, 2, 2, 2, 3, 5, 5]
k = remove_duplicates(data)
print(k, data[:k], data)
# Output:
# 4 [1, 2, 3, 5] [1, 2, 3, 5, 2, 3, 5, 5]

def move_zeros(nums):
    write = 0
    for read in range(len(nums)):
        if nums[read] != 0:
            nums[write], nums[read] = nums[read], nums[write]
            write += 1
    return nums


print(move_zeros([0, 1, 0, 3, 12]))
# Output:
# [1, 3, 12, 0, 0]

This is O(n) time and O(1) space. Quicksort uses a partition of exactly this kind, with a pivot value as the rule, and the sorting lesson builds on it.

#Sliding Window of Fixed Size

A window is a subarray you hold between two markers. Sliding it right by one means adding the new value on the right and removing the old value on the left. You never add up the whole window again.

Problem: find the largest sum of any run of k neighbouring values. The slow way adds k values for each of the n - k + 1 positions, which is O(n * k). The window needs one addition and one subtraction per move.

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


print(max_sum_k([2, 1, 5, 1, 3, 2], 3))
print(max_sum_k([-4, -1, -3, -2], 2))
# Output:
# 9
# -4

The first window costs k steps and every move after it costs 2, so the total is O(n) time and O(1) space. Notice that the best is set from the first window and not from 0. With all negative numbers, starting at 0 would report a sum that no window has. The second call checks that: the best pair is -1 and -3, giving -4.

#Sliding Window of Variable Size

Often the window size is not given. You grow the window on the right, and when it stops being valid you shrink it from the left until it is valid again. The goal is the longest or the shortest valid window.

#Longest Substring Without Repeats

def longest_unique(text):
    last_seen = {}
    start = 0
    best = 0
    for end, ch in enumerate(text):
        if ch in last_seen and last_seen[ch] >= start:
            start = last_seen[ch] + 1
        last_seen[ch] = end
        best = max(best, end - start + 1)
    return best


for word in ("abcabcbb", "bbbbb", "pwwkew", "abba", ""):
    print(repr(word), longest_unique(word))
# Output:
# 'abcabcbb' 3
# 'bbbbb' 1
# 'pwwkew' 3
# 'abba' 2
# '' 0

Each letter is stored and looked up once, so the time is O(n). The dict holds at most one entry per distinct letter, so the space is O(k) for k distinct letters. The three first words are not enough to catch a missing guard, which is why 'abba' is worth keeping in your tests: with the guard removed the four answers become 3, 1, 3 and 3.

#Smallest Subarray With Sum At Least s

def min_subarray_len(target, nums):
    left = 0
    total = 0
    best = 0
    for right in range(len(nums)):
        total += nums[right]
        while total >= target:
            length = right - left + 1
            if best == 0 or length < best:
                best = length
            total -= nums[left]
            left += 1
    return best


print(min_subarray_len(7, [2, 3, 1, 2, 4, 3]))
print(min_subarray_len(100, [1, 2, 3]))
# Output:
# 2
# 0

#Why the Window Is O(n)

You can see it by counting. The list below has 1,000 values. The cell counts every move of each marker for three targets.

def count_moves(target, nums):
    left = total = 0
    right_moves = left_moves = 0
    for right in range(len(nums)):
        right_moves += 1
        total += nums[right]
        while total >= target:
            total -= nums[left]
            left += 1
            left_moves += 1
    return right_moves, left_moves


nums = [i % 7 + 1 for i in range(1000)]
print(len(nums), count_moves(500, nums))
print(len(nums), count_moves(10, nums))
print(len(nums), count_moves(10**9, nums))
# Output:
# 1000 (1000, 875)
# 1000 (1000, 999)
# 1000 (1000, 0)

The right marker always moves 1,000 times. The left marker moves 875, 999 and 0 times. It never reaches 1,001. The time is O(n) and the extra space is O(1).

#Prefix Sums

The third habit is different. It does not slide anything. It does a little work once, and then answers many questions about ranges quickly.

def build_prefix(nums):
    prefix = [0]
    for value in nums:
        prefix.append(prefix[-1] + value)
    return prefix


def range_sum(prefix, i, j):
    return prefix[j + 1] - prefix[i]


nums = [3, 1, 4, 1, 5, 9, 2, 6]
prefix = build_prefix(nums)
print(prefix)
print(range_sum(prefix, 2, 5), sum(nums[2:6]))
print(range_sum(prefix, 0, 7), range_sum(prefix, 3, 3))
# Output:
# [0, 3, 4, 8, 9, 14, 23, 25, 31]
# 19 19
# 31 1

#Counting Subarrays That Add Up to k

Here is a harder question. How many subarrays of a list add up to exactly k? The values may be negative. Try the smallest case first.

def count_subarrays_sum_k(nums, k):
    seen = {0: 1}
    running = 0
    count = 0
    for value in nums:
        running += value
        count += seen.get(running - k, 0)
        seen[running] = seen.get(running, 0) + 1
    return count


print(count_subarrays_sum_k([1, 2, 3], 3))
print(count_subarrays_sum_k([1, -1, 1, -1], 0))
print(count_subarrays_sum_k([3, 4, 7, 2, -3, 1, 4, 2], 7))
# Output:
# 2
# 4
# 4

One pass, one dict lookup per value. The time is O(n) on average, because a dict lookup is O(1) on average, and the space is O(n) for the dict. The second call has negative values and still works, which a window cannot do, as the next part shows.

#Two Dimensions in One Paragraph

grid = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
rows, cols = len(grid), len(grid[0])
pre = [[0] * (cols + 1) for _ in range(rows + 1)]
for r in range(rows):
    for c in range(cols):
        pre[r + 1][c + 1] = grid[r][c] + pre[r][c + 1] + pre[r + 1][c] - pre[r][c]


def rect_sum(r1, c1, r2, c2):
    return pre[r2 + 1][c2 + 1] - pre[r1][c2 + 1] - pre[r2 + 1][c1] + pre[r1][c1]


print(rect_sum(1, 1, 2, 2), rect_sum(0, 0, 2, 2), rect_sum(0, 1, 1, 2))
# Output:
# 28 45 16

The first result is 5 + 6 + 8 + 9 = 28. The whole grid is 45, and the top right block is 2 + 3 + 5 + 6 = 16. This is the only taste of 2D prefix sums we need now.

#Which Pattern Does the Problem Want?

Read the problem and look for these signs.

#When Each Pattern Fails

Every habit rests on an assumption, and breaking the assumption breaks the answer.

Two pointers from the ends need an order or an argument for discarding one side. On an unsorted pair-sum, moving a marker discards values that might have been part of the answer. Sort first, or use a dict.

A variable window needs the sum to behave. When you add a value the sum must not drop, so shrinking always makes the sum smaller and growing makes it larger. That is true only for non-negative numbers. With negative numbers, the left marker cannot know whether dropping a value helps. Here the window code from above is run on a list with a negative number, and compared with a brute-force check.

def min_len_brute(target, nums):
    best = 0
    for i in range(len(nums)):
        total = 0
        for j in range(i, len(nums)):
            total += nums[j]
            if total >= target and (best == 0 or j - i + 1 < best):
                best = j - i + 1
    return best


print(min_subarray_len(6, [1, -5, 6]), min_len_brute(6, [1, -5, 6]))
# Output:
# 0 1

The window says no run reaches 6. The brute force finds the single value 6. The window kept the early values 1 and -5 in the sum and never got a chance to throw them away. For negative numbers use prefix sums, or a more advanced structure.

Prefix sums use O(n) extra space. When you must use O(1) space and the values are non-negative, a window is the better choice.

#How This Shows Up in Real Code

#Common Mistakes

#Try It

Five problems, from easy to hard. Fill in each stub, run it, and compare the printed result with the comment. Do not skip a rung. Before you code each one, trace a tiny input by hand in a table, the way this lesson did.

#Recap

The three habits all replace a loop inside a loop with one pass. Two pointers from both ends work on sorted data or when you can prove that one side is safe to discard, and they run in O(n) time with O(1) space. Read and write pointers change a list in place in O(n) time.

Prefix sums pay O(n) time and space once, and then answer any range sum in O(1).

With a dict they count the subarrays that add up to k in O(n), even with negative values. Choose by the signs in the problem, and check the assumption each habit needs: order for two pointers, non-negative values for a variable window.

#Quiz