Two Pointers & Sliding Window

These two patterns alone solve a huge portion of array and string problems. They replace brute-force nested loops with elegant O(n) solutions.

Two Pointers Pattern

The idea is simple: use two pointers that move through the data structure, typically from opposite ends or at different speeds.

Three Variations:

1. Opposite Direction (Converging)

Used when you need to find pairs or check symmetry.

# Container with Most Water
def max_area(height):
    left, right = 0, len(height) - 1
    max_water = 0
    while left < right:
        width = right - left
        h = min(height[left], height[right])
        max_water = max(max_water, width * h)
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    return max_water

# Two Sum (sorted array)
def two_sum_sorted(numbers, target):
    left, right = 0, len(numbers) - 1
    while left < right:
        total = numbers[left] + numbers[right]
        if total == target:
            return [left + 1, right + 1]
        elif total < target:
            left += 1
        else:
            right -= 1

2. Same Direction (Fast/Slow)

Used for removing duplicates, partitioning, or linked list problems.

# Remove duplicates from sorted array (in-place)
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

3. Three Pointers

Extension of two pointers for problems like 3Sum.

# 3Sum: find all triplets that sum to zero
def three_sum(nums):
    nums.sort()
    result = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i-1]:
            continue  # Skip duplicates
        left, right = i + 1, len(nums) - 1
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            if total == 0:
                result.append([nums[i], nums[left], nums[right]])
                while left < right and nums[left] == nums[left+1]:
                    left += 1  # Skip duplicates
                while left < right and nums[right] == nums[right-1]:
                    right -= 1
                left += 1
                right -= 1
            elif total < 0:
                left += 1
            else:
                right -= 1
    return result

Sliding Window Pattern

A window that slides across an array/string, expanding or shrinking to find optimal subarrays.

Fixed-Size Window

# Maximum sum of subarray of size k
def max_sum_subarray(nums, k):
    window_sum = sum(nums[:k])
    max_sum = window_sum
    for i in range(k, len(nums)):
        window_sum += nums[i] - nums[i - k]
        max_sum = max(max_sum, window_sum)
    return max_sum

Variable-Size Window

# Longest substring without repeating characters
def length_of_longest_substring(s):
    char_set = set()
    left = 0
    max_len = 0
    for right in range(len(s)):
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1
        char_set.add(s[right])
        max_len = max(max_len, right - left + 1)
    return max_len

# Minimum window substring
def min_window(s, t):
    from collections import Counter
    need = Counter(t)
    missing = len(t)
    left = start = 0
    min_len = float('inf')
    for right, char in enumerate(s):
        if need[char] > 0:
            missing -= 1
        need[char] -= 1
        while missing == 0:
            if right - left + 1 < min_len:
                min_len = right - left + 1
                start = left
            need[s[left]] += 1
            if need[s[left]] > 0:
                missing += 1
            left += 1
    return s[start:start + min_len] if min_len != float('inf') else ""

Pattern Recognition Guide

Signal	Pattern	Time Complexity
"Sorted array + find pair"	Two Pointers (opposite)	O(n)
"Palindrome check"	Two Pointers (opposite)	O(n)
"Remove duplicates in-place"	Two Pointers (same direction)	O(n)
"Subarray of size K"	Fixed Sliding Window	O(n)
"Longest/shortest substring with condition"	Variable Sliding Window	O(n)
"3Sum / 4Sum"	Sort + Two Pointers	O(n^2) / O(n^3)

---

Next, we'll cover binary search and greedy algorithms -- patterns that optimize decision-making. :::