Sliding Window and Two Pointer Patterns in Python

Sliding Window and Two Pointers

These patterns convert O(n^2) solutions into O(n) single-pass solutions. They appear in hundreds of interview problems.

def max_sum_subarray(arr, k):
    window_sum = sum(arr[:k])
    max_sum    = window_sum
    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i-k]
        max_sum     = max(max_sum, window_sum)
    return max_sum

print(max_sum_subarray([2,1,5,1,3,2], 3))  # 9 (5+1+3)

Variable Sliding Window

def longest_substring_k_distinct(s, k):
    char_count = {}
    l = max_len = 0
    for r, ch in enumerate(s):
        char_count[ch] = char_count.get(ch, 0) + 1
        while len(char_count) > k:
            char_count[s[l]] -= 1
            if char_count[s[l]] == 0: del char_count[s[l]]
            l += 1
        max_len = max(max_len, r - l + 1)
    return max_len

print(longest_substring_k_distinct("araaci", 2))  # 4 (araa)

Two Pointer Patterns

def two_sum_sorted(arr, target):
    l, r = 0, len(arr) - 1
    while l < r:
        s = arr[l] + arr[r]
        if   s == target: return [l, r]
        elif s < target:  l += 1
        else:             r -= 1
    return []

def remove_duplicates(nums):
    if not nums: return 0
    slow = 0
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]
    return slow + 1