Two Pointers and Sliding Window

Chapter 23: Two Pointers and Sliding Window

You have a sorted array and need to find two numbers that add up to a target. The brute-force approach tries every pair — O(n²). But if you place one pointer at the start and another at the end, you can solve it in a single pass. This is the two-pointer technique: by maintaining invariants about what lies between, before, or after the pointers, you eliminate vast swaths of the search space without checking them.

The sliding window is its close cousin. When the problem asks about a contiguous subarray or substring that satisfies some property, you can maintain a "window" — defined by left and right pointers — and grow or shrink it efficiently. Both techniques transform O(n²) brute force into O(n) elegance, and both share a single underlying principle: monotonic progress guarantees correctness without exhaustive search.

Level 1 · What You Need to Know

1.1 Three Pointer Patterns

Two-pointer problems fall into three distinct categories. Recognizing which pattern applies is 80% of solving the problem.

Why three patterns and not one? Because the search space geometry differs. In collision pointers, you're searching over pairs (i, j) where i < j in a sorted structure — moving inward exploits sort order. In fast-slow, you're exploiting the difference in traversal speed to detect structural properties (cycles, midpoints). In sliding windows, you're searching over contiguous ranges, and the key insight is that when you advance the right pointer, you never need to move the left pointer backward (Klee, "Measuring the Intersection of Geometric Objects", 1977 — though the technique predates formal publication).

1.2 Fast-Slow Pointers

Floyd's Cycle Detection

The most famous fast-slow pointer algorithm. Given a linked list that may contain a cycle, determine if a cycle exists and find where it starts.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def has_cycle(head: ListNode) -> bool:
    """Detect if linked list has a cycle. O(n) time, O(1) space."""
    slow = fast = head
    while fast and fast.next:
        slow = slow.next        # moves 1 step
        fast = fast.next.next   # moves 2 steps
        if slow == fast:
            return True
    return False

def find_cycle_start(head: ListNode) -> ListNode:
    """Find the node where the cycle begins. Returns None if no cycle."""
    slow = fast = head
    
    # Phase 1: Detect cycle
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            break
    else:
        return None  # No cycle
    
    # Phase 2: Find entry point
    # Reset one pointer to head, advance both at speed 1
    slow = head
    while slow != fast:
        slow = slow.next
        fast = fast.next
    return slow

Why does Phase 2 work? Let the distance from head to cycle start be a, the distance from cycle start to the meeting point be b, and the cycle length be c. When slow and fast meet:

• slow traveled: a + b
• fast traveled: a + b + k·c (for some integer k ≥ 1)
• Since fast moves 2x: 2(a + b) = a + b + k·c → a + b = k·c → a = k·c - b

This means: walking a steps from the meeting point lands you at the cycle start (because you complete k full cycles minus the b steps you already took into the cycle). Walking a steps from the head also lands you at the cycle start. So both pointers meet exactly at the cycle entry.

Find Middle of Linked List

def find_middle(head: ListNode) -> ListNode:
    """Return the middle node. For even length, returns second middle."""
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

When fast reaches the end (or one past the end), slow is at the middle. For a list of length n: fast takes ⌊n/2⌋ iterations of two steps, so slow takes ⌊n/2⌋ single steps — landing on position ⌊n/2⌋ (0-indexed), which is the middle (or second middle for even-length lists).

Palindrome Linked List

Combines find-middle with in-place reversal:

def is_palindrome(head: ListNode) -> bool:
    """Check if linked list is a palindrome. O(n) time, O(1) space."""
    if not head or not head.next:
        return True
    
    # Find middle
    slow = fast = head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    
    # Reverse second half
    prev = None
    curr = slow.next
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    
    # Compare halves
    first, second = head, prev
    while second:
        if first.val != second.val:
            return False
        first = first.next
        second = second.next
    return True

1.3 Collision Pointers (Opposite Direction)

Two Sum in Sorted Array (LeetCode #167)

def two_sum_sorted(numbers: list[int], target: int) -> list[int]:
    """Find two numbers in sorted array that sum to target.
    Returns 1-indexed positions."""
    left, right = 0, len(numbers) - 1
    
    while left < right:
        current_sum = numbers[left] + numbers[right]
        if current_sum == target:
            return [left + 1, right + 1]
        elif current_sum < target:
            left += 1   # Need larger sum → move left pointer right
        else:
            right -= 1  # Need smaller sum → move right pointer left
    
    return []  # No solution found

Why this works (correctness proof): Consider the n×n matrix M where M[i][j] = numbers[i] + numbers[j]. Because the array is sorted, this matrix is sorted both row-wise and column-wise. The two-pointer technique performs a staircase walk through this matrix — starting at top-right corner (i=0, j=n-1). Moving left decreases the sum; moving down increases it. This visits at most 2n-1 cells and is guaranteed to find the target if it exists, because the staircase partitions the matrix into "too small" (below-left) and "too large" (above-right) regions, and the target must lie on the boundary between them.

Three Sum (LeetCode #15)

def three_sum(nums: list[int]) -> list[list[int]]:
    """Find all unique triplets that sum to zero."""
    nums.sort()
    result = []
    
    for i in range(len(nums) - 2):
        # Skip duplicates for first element
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        
        # Early termination: smallest possible sum > 0
        if nums[i] > 0:
            break
        
        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]])
                # Skip duplicates for second element
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                # Skip duplicates for third element
                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

Complexity: Sorting is O(n log n). The outer loop runs n times, inner two-pointer scan is O(n) per iteration. Total: O(n²). This is optimal for Three Sum — Grønlund and Pettie proved in "Threesomes, Degenerates, and Love Triangles" (FOCS 2014) that under certain computational models, sub-quadratic Three Sum is possible but the practical improvement is marginal.

Container With Most Water (LeetCode #11)

def max_area(height: list[int]) -> int:
    """Find two lines that together with x-axis form container with most water."""
    left, right = 0, len(height) - 1
    best = 0
    
    while left < right:
        width = right - left
        h = min(height[left], height[right])
        best = max(best, width * h)
        
        # Move the shorter side inward
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    
    return best

Why move the shorter side? The area is min(h[left], h[right]) × (right - left). When you move either pointer inward, the width decreases by 1. If you move the taller side inward, the height cannot increase (it's still bounded by the shorter side), so the area strictly decreases — no point in exploring those options. By moving the shorter side, the height might increase enough to compensate for the width loss. This greedy choice eliminates O(n) suboptimal options at each step without missing the optimal pair.

1.4 Sliding Window Template

The sliding window technique maintains a range [left, right) (or [left, right]) that satisfies some constraint, and systematically explores all valid windows.

Fixed-Size Window

When the window size k is given, simply maintain a window of exactly k elements:

def max_sum_subarray(nums: list[int], k: int) -> int:
    """Maximum sum of subarray with exactly k elements."""
    n = len(nums)
    if n < k:
        return 0
    
    # Initialize first window
    window_sum = sum(nums[:k])
    best = window_sum
    
    # Slide: add right element, remove left element
    for right in range(k, n):
        window_sum += nums[right] - nums[right - k]
        best = max(best, window_sum)
    
    return best

Variable-Size Window (Universal Template)

This is the template you'll use for 90% of sliding window problems:

def sliding_window_template(s: str) -> int:
    """
    Universal sliding window template for variable-size windows.
    
    The key insight: we expand the window (move right) to explore,
    and shrink the window (move left) to restore a feasibility constraint.
    
    Template works for:
    - Longest substring/subarray satisfying condition → track max length
    - Shortest substring/subarray satisfying condition → track min length
    """
    from collections import defaultdict
    
    window = defaultdict(int)  # Window state (e.g., character counts)
    left = 0
    result = 0  # or float('inf') for minimum problems
    
    for right in range(len(s)):
        # 1. EXPAND: Add s[right] to window state
        window[s[right]] += 1
        
        # 2. SHRINK: While window violates the constraint, shrink from left
        while window_is_invalid(window):  # Replace with actual condition
            window[s[left]] -= 1
            if window[s[left]] == 0:
                del window[s[left]]
            left += 1
        
        # 3. UPDATE: Current window [left, right] is valid, update answer
        result = max(result, right - left + 1)  # For longest
        # result = min(result, right - left + 1)  # For shortest
    
    return result

1.5 Classic Sliding Window Problems

Longest Substring Without Repeating Characters (LeetCode #3)

def length_of_longest_substring(s: str) -> int:
    """Find length of longest substring without repeating characters.
    
    Example: "abcabcbb" → 3 ("abc")
    
    Approach: Maintain a window where all characters are unique.
    When a duplicate enters, shrink from left until it's removed.
    """
    char_index = {}  # char → its most recent index in window
    left = 0
    max_length = 0
    
    for right in range(len(s)):
        # If character already in window, jump left past its previous position
        if s[right] in char_index and char_index[s[right]] >= left:
            left = char_index[s[right]] + 1
        
        char_index[s[right]] = right
        max_length = max(max_length, right - left + 1)
    
    return max_length

Why the >= left check? Without it, we might jump left backward. The character might exist in char_index from a position before the current window's left boundary — that's not actually a duplicate within our window.

Minimum Window Substring (LeetCode #76)

def min_window(s: str, t: str) -> str:
    """Find minimum window in s that contains all characters of t.
    
    Example: s = "ADOBECODEBANC", t = "ABC" → "BANC"
    
    Approach: Expand right to include all chars of t, then shrink left
    to find minimum. This is the 'find shortest valid window' pattern.
    """
    from collections import Counter
    
    if not s or not t:
        return ""
    
    # Count characters needed
    need = Counter(t)
    missing = len(t)  # Number of chars still needed
    
    # Result tracking
    start = 0
    min_len = float('inf')
    left = 0
    
    for right in range(len(s)):
        # Expand: add s[right] to window
        if need[s[right]] > 0:
            missing -= 1
        need[s[right]] -= 1
        
        # Shrink: while window contains all of t, try to minimize
        while missing == 0:
            # Update result
            window_len = right - left + 1
            if window_len < min_len:
                min_len = window_len
                start = left
            
            # Remove s[left] from window
            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 ""

The clever counting trick: Instead of maintaining two counters and comparing them (expensive), we track a single missing variable. It decreases when we add a truly needed character, and increases when we remove one. The window is valid exactly when missing == 0. This reduces the per-step overhead from O(|charset|) comparison to O(1).

Level 2 · How It Works

2.1 Universal Sliding Window Template (Detailed)

Every variable-size sliding window problem follows this structure. The differences between problems lie in three choices:

1. What state does the window maintain? (Counter, sum, set, monotone deque)
2. What is the validity condition? (All chars present, no duplicates, sum ≤ k)
3. Are we maximizing or minimizing the window?

def universal_sliding_window(arr, constraint):
    """
    Detailed universal template with extensive annotations.
    
    INVARIANT: At every point in the algorithm, the window [left, right)
    either satisfies the constraint or we are actively shrinking to restore it.
    
    CORRECTNESS ARGUMENT:
    - We consider every possible right endpoint (outer loop ensures this).
    - For each right endpoint, we find the optimal left endpoint.
    - The optimal left endpoint is monotonically non-decreasing
      (this is the key insight that makes O(n) possible).
    
    WHY O(n) TOTAL:
    - The right pointer advances exactly n times (once per outer iteration).
    - The left pointer advances at most n times total across ALL iterations
      (it never moves backward, and can't exceed n total moves).
    - Each element enters the window exactly once (when right passes it)
      and leaves exactly once (when left passes it).
    - Total operations: at most 2n pointer moves = O(n).
    """
    n = len(arr)
    left = 0
    window_state = initialize_state()  # Problem-specific
    result = initial_result()  # 0 for max, inf for min
    
    for right in range(n):
        # ─── STEP 1: EXPAND ───────────────────────────────────
        # Add arr[right] to the window state.
        # This might violate the constraint.
        update_state_add(window_state, arr[right])
        
        # ─── STEP 2: SHRINK ───────────────────────────────────
        # Restore the constraint by advancing left.
        # For LONGEST valid window: use "while invalid, shrink"
        # For SHORTEST valid window: use "while valid, record and shrink"
        while not is_valid(window_state, constraint):
            update_state_remove(window_state, arr[left])
            left += 1
        
        # ─── STEP 3: RECORD ───────────────────────────────────
        # Window [left, right] is now valid (for longest problems).
        # Record if this is the best window seen so far.
        result = max(result, right - left + 1)
    
    return result

Critical subtlety: longest vs. shortest. For "longest valid window" problems, we shrink until valid, then record. For "shortest valid window" problems (like minimum window substring), we record while valid, then shrink:

# Shortest valid window variant:
for right in range(n):
    update_state_add(window_state, arr[right])
    
    while is_valid(window_state, constraint):
        result = min(result, right - left + 1)  # Record INSIDE the while
        update_state_remove(window_state, arr[left])
        left += 1

2.2 Why Sliding Window is O(n): A Rigorous Argument

Many students intuitively feel the nested while loop makes this O(n²). Here's why it's actually O(n):

Amortized analysis (aggregate method): Define a potential function Φ = left. Initially Φ = 0. Each iteration of the outer loop (advancing right) increases Φ by at most some amount via the inner while loop. But left can never exceed n, and left never decreases. Therefore:

• Total advances of right: exactly n
• Total advances of left: at most n (since left ∈ [0, n] and never decreases)
• Total pointer moves: ≤ 2n

Each pointer move does O(1) work (update a counter, compare values). Therefore total work is O(n).

Alternatively (accounting method): Assign each element a "budget" of 2 operations: one for being added to the window (when right passes it) and one for being removed (when left passes it). Each element is added exactly once and removed at most once. Total operations ≤ 2n = O(n).

This amortized argument was formalized by Tarjan in "Amortized Computational Complexity" (SIAM Journal on Algebraic and Discrete Methods, 1985), though the sliding window technique itself had been used earlier in various contexts.

2.3 Floyd's Cycle Detection: Complete Mathematical Proof

Theorem (Floyd, 1967): If a sequence x₀, x₁, x₂, ... defined by xᵢ = f(xᵢ₋₁) is eventually periodic, then there exist integers μ (the start of the cycle) and λ (the cycle length) such that xᵢ = xᵢ₊λ for all i ≥ μ. Both μ and λ can be found using O(1) space and O(μ + λ) time.

Proof of Phase 1 (meeting):

Let μ = distance from start to cycle entry, and λ = cycle length.

When slow enters the cycle (after μ steps), fast has taken 2μ steps, so fast is μ steps into the cycle, i.e., at position μ mod λ within the cycle.

The gap between fast and slow within the cycle is μ mod λ. But since fast gains 1 step per iteration, they meet after λ - (μ mod λ) additional iterations.

Total steps for slow to reach meeting point: μ + (λ - μ mod λ). Meeting point within cycle: (λ - μ mod λ) mod λ.

Proof of Phase 2 (finding μ):

At the meeting point, slow has traveled μ + (λ - μ mod λ) = μ + λ - (μ mod λ) steps.

The meeting point is at distance (λ - μ mod λ) from the cycle start (measuring forward in the cycle).

Now: distance from meeting point back to cycle start (going forward) = λ - (λ - μ mod λ) = μ mod λ.

Distance from head to cycle start = μ = qλ + (μ mod λ) for some integer q.

So walking μ steps from the meeting point means: (μ mod λ) steps to reach cycle start, then q full cycles back to cycle start. You end up at the cycle start.

Walking μ steps from the head also ends at the cycle start.

Therefore, when both pointers move at speed 1 from their respective starting positions (head and meeting point), they meet at the cycle start after exactly μ steps. ∎

Space complexity: O(1) — only two pointer variables. Time complexity: Phase 1 takes O(μ + λ) steps. Phase 2 takes O(μ) steps. Total: O(μ + λ).

2.4 Collision Pointer Correctness Proof

Claim: For the two-sum problem on a sorted array, the collision pointer technique finds a pair summing to the target if one exists.

Proof by invariant:

Let the array be a[0] ≤ a[1] ≤ ... ≤ a[n-1] and suppose a[i*] + a[j*] = target where i* < j*.

Invariant: At every step, i* ≥ left and j* ≤ right.

Base case: Initially left = 0 ≤ i* and j* ≤ n-1 = right. ✓

Inductive step: Suppose the invariant holds. Consider the current sum S = a[left] + a[right].

Case 1: S = target. We found it. Done.

Case 2: S < target. We increment left. Need to show i* ≥ left + 1, i.e., i* ≠ left.

Suppose for contradiction that i* = left. Then a[i*] + a[right] = a[left] + a[right] = S < target = a[i*] + a[j*]. This implies a[right] < a[j*]. Since the array is sorted and j* ≤ right, we have a[j*] ≤ a[right] — contradiction. Therefore i* > left, so i* ≥ left + 1. ✓

Case 3: S > target. Symmetric argument shows j* < right, so j* ≤ right - 1. ✓

Since the invariant is maintained, the algorithm cannot terminate without finding the solution (because we exit only when left ≥ right, but the invariant guarantees left ≤ i* < j* ≤ right, meaning left < right holds throughout). ∎

Key takeaway: The proof shows that each pointer movement provably eliminates an entire row or column from the search space — not by checking them, but by mathematical reasoning about the sort order.

2.5 Complexity Analysis of Classic Problems

Level 3 · What the Spec Says

3.1 Floyd's Cycle Detection: Historical Context

Robert W. Floyd published the tortoise-and-hare algorithm in his 1967 unpublished note "Nondeterministic Algorithms" (the algorithm is sometimes attributed to this note, though the full details appeared in Knuth's "The Art of Computer Programming", Vol. 2, 1969, Exercise 6 in Section 3.1).

The algorithm was developed in the context of pseudo-random number generator testing. If a PRNG has internal state of size s bits, its period cannot exceed 2ˢ. Floyd's algorithm can detect the actual period using only O(1) extra memory — critical when the state space is enormous.

Brent's improvement (1980): Richard Brent proposed a modification ("An Improved Monte Carlo Factorization Algorithm", BIT Numerical Mathematics, 1980) that finds the cycle length λ directly in Phase 1. Instead of moving both pointers simultaneously, Brent's algorithm moves only the fast pointer and periodically teleports the slow pointer to the fast pointer's position. This finds the cycle 36% faster on average (the constant improves from 3μ + 3λ to approximately 2.4μ + 2.4λ evaluations of f).

def brent_cycle_detection(f, x0):
    """Brent's cycle detection. Returns (lambda, mu).
    
    f: the function defining the sequence (x_i = f(x_{i-1}))
    x0: starting value
    
    Improvement over Floyd's: ~36% fewer function evaluations.
    (Brent, 'An Improved Monte Carlo Factorization Algorithm', BIT 1980)
    """
    # Phase 1: Find cycle length lambda
    power = lam = 1
    tortoise = x0
    hare = f(x0)
    
    while tortoise != hare:
        if power == lam:  # Time to reset
            tortoise = hare
            power *= 2
            lam = 0
        hare = f(hare)
        lam += 1
    
    # Phase 2: Find cycle start mu
    tortoise = hare = x0
    for _ in range(lam):
        hare = f(hare)
    
    mu = 0
    while tortoise != hare:
        tortoise = f(tortoise)
        hare = f(hare)
        mu += 1
    
    return lam, mu

3.2 Sliding Window and Monotone Queue Relationship

The sliding window technique handles problems where you need to maintain aggregate information (sum, count of distinct elements, character frequencies) over a moving range. But what if you need the maximum or minimum within the window?

Naively checking all elements in the window gives O(nk) for a window of size k. The monotone deque (covered in Chapter 6) provides O(n) total by maintaining a decreasing (or increasing) sequence of candidates:

from collections import deque

def max_sliding_window(nums: list[int], k: int) -> list[int]:
    """Maximum in each sliding window of size k.
    
    Uses monotone decreasing deque: front is always the max.
    Elements that can never be the max are discarded.
    
    Connection to two-pointer: the deque's front and back
    act as implicit "pointers" into the window, with the
    invariant that the deque stores indices of elements in
    decreasing order of value.
    
    See Chapter 6 for full monotone queue theory.
    """
    dq = deque()  # Stores indices
    result = []
    
    for i in range(len(nums)):
        # Remove elements outside window
        while dq and dq[0] <= i - k:
            dq.popleft()
        
        # Maintain decreasing order: remove smaller elements from back
        while dq and nums[dq[-1]] <= nums[i]:
            dq.pop()
        
        dq.append(i)
        
        # Window is full: record the max (front of deque)
        if i >= k - 1:
            result.append(nums[dq[0]])
    
    return result

The relationship: Both sliding window and monotone deque exploit the same principle — when the window slides right, some previously useful information becomes irrelevant (elements that left the window) and can be discarded in O(1) amortized time. The difference is what "useful" means: for sum problems, every element contributes equally; for max/min problems, elements dominated by newer, larger elements are useless.

3.3 Two Pointers in Sorting Algorithms

Two-pointer logic appears at the heart of two fundamental sorting algorithms:

Quicksort partition (Hoare's scheme, 1962):

def hoare_partition(arr: list, low: int, high: int) -> int:
    """Hoare's original two-pointer partition scheme.
    
    Two pointers start at opposite ends and move toward each other.
    Left pointer finds elements >= pivot; right finds elements <= pivot.
    They swap when both find misplaced elements.
    
    This is collision pointer technique applied to partitioning.
    (C.A.R. Hoare, 'Quicksort', The Computer Journal, 1962)
    """
    pivot = arr[low]
    i = low - 1
    j = high + 1
    
    while True:
        i += 1
        while arr[i] < pivot:
            i += 1
        j -= 1
        while arr[j] > pivot:
            j -= 1
        if i >= j:
            return j
        arr[i], arr[j] = arr[j], arr[i]

Merge sort's merge step (von Neumann, 1945):

def merge(left: list, right: list) -> list:
    """Merge two sorted arrays using same-direction two pointers.
    
    Both pointers move left-to-right through their respective arrays.
    At each step, take the smaller element and advance that pointer.
    
    This is same-direction pointer technique on two separate sequences.
    (John von Neumann, first described merge sort in 1945)
    """
    result = []
    i = j = 0
    
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    result.extend(left[i:])
    result.extend(right[j:])
    return result

Dutch National Flag (three-way partition, Dijkstra 1976):

A three-pointer variant used in quicksort to handle many duplicate elements efficiently:

def dutch_national_flag(arr: list, pivot) -> tuple:
    """Three-way partition: elements < pivot, == pivot, > pivot.
    
    Three pointers: low, mid, high.
    - [0, low): less than pivot
    - [low, mid): equal to pivot  
    - [mid, high]: unexamined
    - (high, n-1]: greater than pivot
    
    (E.W. Dijkstra, 'A Discipline of Programming', 1976, Chapter 14)
    """
    low = mid = 0
    high = len(arr) - 1
    
    while mid <= high:
        if arr[mid] < pivot:
            arr[low], arr[mid] = arr[mid], arr[low]
            low += 1
            mid += 1
        elif arr[mid] == pivot:
            mid += 1
        else:
            arr[mid], arr[high] = arr[high], arr[mid]
            high -= 1
    
    return low, mid  # Boundaries of the three partitions

3.4 Formal Analysis: When Can Two Pointers Be Applied?

Two pointers work when the search space has monotonic structure. Formally:

Condition for collision pointers: Given a function f(i, j) defined on pairs where i < j, collision pointers work if:

• f is non-decreasing in j for fixed i (or equivalently, non-decreasing in i for fixed j)
• You can determine from f(i, j) vs. target whether to advance i or retreat j

Condition for sliding window: Given a window property P([left, right]), sliding window works if:

• Monotonicity of feasibility: If P([left, right]) is infeasible (too much), then P([left, right+1]) is also infeasible (adding elements never helps when you have too much)
• Equivalently: if P([left, right]) is feasible, then P([left+1, right]) is also feasible (removing elements preserves feasibility)

This is sometimes called the "two-pointer condition" or "sliding window condition" in competitive programming literature (Laaksonen, "Competitive Programmer's Handbook", 2017).

Level 4 · Edge Cases and Pitfalls

4.1 Common Boundary Errors

Off-by-One in Window Size

# WRONG: Window size is right - left, not right - left + 1
# when using [left, right) convention
length = right - left      # Correct for half-open [left, right)
length = right - left + 1  # Correct for closed [left, right]

# Choose one convention and stick with it!
# Half-open [left, right) is generally safer because:
# - Empty window: left == right (clean check)
# - Window size: right - left (no +1)
# - Iteration: for i in range(left, right) works directly

Empty Array / Single Element

def two_sum_safe(nums: list[int], target: int) -> list[int]:
    """Always handle edge cases first."""
    if len(nums) < 2:
        return []  # Can't form a pair
    
    left, right = 0, len(nums) - 1
    while left < right:  # NOT left <= right (would compare element with itself)
        # ... normal logic
        pass
    return []

The left < right vs left <= right mistake: For pair-finding problems, you must use left < right (strict) because a single element can't pair with itself. Using <= leads to either infinite loops or counting an element twice.

All Elements Identical

# Three sum with all zeros: [0, 0, 0, 0, 0]
# Without deduplication: returns [0,0,0] many times
# The skip-duplicate logic handles this:
if i > 0 and nums[i] == nums[i-1]:
    continue  # Skip duplicate first element

# But be careful: skip AFTER recording, not before checking
# WRONG:
while left < right and nums[left] == nums[left + 1]:
    left += 1
left += 1  # Need this extra advance!

# If you forget the final left += 1, you stay on the same value

4.2 Character Counting Pitfalls in Sliding Window

Counter vs. Plain Dict

from collections import Counter

# PITFALL 1: Counter allows negative values silently
c = Counter("abc")
c['a'] -= 5  # c['a'] is now -4, no error raised!

# This is actually USEFUL for sliding window (see min_window above),
# but you must understand the semantics:
# - Positive count: we still need this many
# - Zero count: exactly satisfied
# - Negative count: we have more than needed (surplus)

# PITFALL 2: Comparing dicts/Counters is O(|alphabet|)
# DON'T do this every iteration:
if window_counter == need_counter:  # O(26) for lowercase, O(128) for ASCII
    # ...

# DO maintain a running "satisfied" count instead:
# Track how many DISTINCT characters have reached their required count.
# This gives O(1) validity checks.

The "formed" Variable Pattern

def find_anagrams(s: str, p: str) -> list[int]:
    """LeetCode #438: Find all start indices of p's anagrams in s.
    
    Key insight: Instead of comparing two Counters each step (O(26)),
    track how many characters have the exact required count.
    """
    if len(p) > len(s):
        return []
    
    from collections import Counter
    
    need = Counter(p)
    window = Counter()
    result = []
    
    # 'formed' = number of unique chars in window matching required count
    formed = 0
    required = len(need)  # Number of unique chars in p
    
    for right in range(len(s)):
        char = s[right]
        window[char] += 1
        
        # Check if this char's count NOW matches
        if char in need and window[char] == need[char]:
            formed += 1
        
        # Shrink if window too large
        if right >= len(p):
            left_char = s[right - len(p)]
            if left_char in need and window[left_char] == need[left_char]:
                formed -= 1
            window[left_char] -= 1
        
        # Check if all chars match
        if formed == required:
            result.append(right - len(p) + 1)
    
    return result

4.3 Interview Problems in Detail

Minimum Size Subarray Sum (LeetCode #209)

def min_subarray_len(target: int, nums: list[int]) -> int:
    """Find minimal length subarray with sum >= target.
    
    All elements are positive (crucial assumption!).
    This means: as we expand right, sum increases; as we shrink left, sum decreases.
    Monotonicity is guaranteed by positive elements.
    
    WARNING: This does NOT work if elements can be negative.
    For arrays with negatives, use prefix sums + binary search (O(n log n)).
    """
    n = len(nums)
    left = 0
    current_sum = 0
    min_length = float('inf')
    
    for right in range(n):
        current_sum += nums[right]
        
        # Shrink while valid (finding shortest)
        while current_sum >= target:
            min_length = min(min_length, right - left + 1)
            current_sum -= nums[left]
            left += 1
    
    return min_length if min_length != float('inf') else 0

Why positive elements matter: If elements can be negative, adding more elements might decrease the sum, and removing elements might increase it. The monotonicity assumption (expanding always increases, shrinking always decreases) breaks down, and the left pointer might need to move backward — violating the O(n) guarantee.

Longest Repeating Character Replacement (LeetCode #424)

def character_replacement(s: str, k: int) -> int:
    """Longest substring where you can replace at most k characters
    to make all characters the same.
    
    Key insight: A window of length L is valid if:
        L - max_count <= k
    where max_count is the count of the most frequent char in the window.
    
    Meaning: the number of chars we need to replace (L - max_count)
    must be at most k.
    """
    from collections import defaultdict
    
    count = defaultdict(int)
    left = 0
    max_count = 0  # Max frequency of any single char in current window
    max_length = 0
    
    for right in range(len(s)):
        count[s[right]] += 1
        max_count = max(max_count, count[s[right]])
        
        # Window invalid: too many chars need replacing
        window_len = right - left + 1
        if window_len - max_count > k:
            count[s[left]] -= 1
            left += 1
        
        max_length = max(max_length, right - left + 1)
    
    return max_length

Subtle optimization: We never decrease max_count when shrinking the window. This seems wrong — when the most frequent character leaves the window, shouldn't max_count decrease?

The key insight: we only care about finding a longer valid window than our current best. A window can only be longer if it has a higher max_count (since the validity condition is window_len - max_count ≤ k, a longer valid window requires max_count to have grown). So we never need to shrink max_count — if the current max_count doesn't lead to a longer window, we simply don't update max_length. This is why we use if (shrink by exactly 1) instead of while (shrink until valid): we maintain the window at a fixed size, only growing it when max_count increases.

This clever trick was popularized by competitive programmers and is attributed to various contest solutions from the mid-2010s.

Find All Anagrams in a String (LeetCode #438)

See the implementation in Section 4.2 above. Additional notes:

def find_anagrams_simple(s: str, p: str) -> list[int]:
    """Alternative: Fixed-size window with sorted/Counter comparison.
    
    Simpler to understand but slightly less efficient due to
    Counter comparison at each step.
    """
    from collections import Counter
    
    k = len(p)
    if k > len(s):
        return []
    
    p_count = Counter(p)
    window_count = Counter(s[:k])
    result = []
    
    if window_count == p_count:
        result.append(0)
    
    for i in range(k, len(s)):
        # Add new character
        window_count[s[i]] += 1
        # Remove old character
        old_char = s[i - k]
        window_count[old_char] -= 1
        if window_count[old_char] == 0:
            del window_count[old_char]  # Important: remove zero entries!
        
        if window_count == p_count:
            result.append(i - k + 1)
    
    return result

Why del window_count[old_char] when count reaches 0? Python's Counter.__eq__ considers Counter({'a': 1, 'b': 0}) != Counter({'a': 1}). Zero-count entries are not automatically removed. If you don't delete them, comparisons will fail. This is the #1 bug in sliding window implementations using Counter comparison.

4.4 Three Sum Deduplication: The Correct Approach

Deduplication in Three Sum is the source of more interview bugs than almost any other aspect of the problem. Here's the correct approach and common mistakes:

def three_sum_dedup_analysis(nums: list[int]) -> list[list[int]]:
    """Detailed analysis of correct deduplication in Three Sum."""
    nums.sort()
    result = []
    
    for i in range(len(nums) - 2):
        # CORRECT: Skip duplicate first elements
        # Check i > 0 to avoid index out of bounds
        # Compare with PREVIOUS, not NEXT
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        
        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]])
                
                # CORRECT: Skip duplicates AFTER recording the solution
                # Move past ALL duplicates of nums[left]
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                # Move past ALL duplicates of nums[right]
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1
                # THEN move one more step (past the last duplicate)
                left += 1
                right -= 1
                
            elif total < 0:
                left += 1
            else:
                right -= 1
    
    return result

# COMMON MISTAKE 1: Skipping duplicates BEFORE checking
# This can skip valid solutions:
# WRONG: if nums[left] == nums[left+1]: left += 1; continue
# This skips without ever checking if current left forms a solution!

# COMMON MISTAKE 2: Forgetting the final left += 1 / right -= 1
# After the while loops skip duplicates, you're ON the last duplicate.
# You need one more step to move past it.

# COMMON MISTAKE 3: Using a set to store results
# three_sum_set.add(tuple(sorted(triplet)))  # Works but O(1) extra per result
# This is considered poor form in interviews — the interviewer wants
# to see you handle deduplication algorithmically.

4.5 When NOT to Use Two Pointers

Two pointers are not universally applicable. Knowing when they don't work is as important as knowing when they do.

Unsorted Array Two Sum

# Two Sum (LeetCode #1): Find indices of two numbers summing to target.
# Array is NOT sorted.

# WRONG approach: sorting + two pointers
# Sorting loses the original indices! You'd need to store (value, index)
# pairs, sort by value, then extract indices — works but awkward.

# CORRECT approach: Hash map, O(n) time, O(n) space
def two_sum_unsorted(nums: list[int], target: int) -> list[int]:
    """For unsorted arrays, use a hash map, not two pointers."""
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

# WHY two pointers fail here:
# 1. No sort order → no monotonic invariant → can't decide which pointer to move
# 2. Sorting costs O(n log n), hash map is O(n) — worse time complexity
# 3. Sorting destroys index information (the problem asks for indices)

Subarray Sum with Negative Numbers

# Subarray sum equals k (LeetCode #560): Array may contain negatives.
# 
# WRONG: Sliding window
# With negatives, extending the window might decrease the sum,
# and shrinking might increase it. No monotonicity!
#
# Example: nums = [1, -1, 1, -1, 1], k = 0
# Window [0,1] sums to 0 ✓, but sliding window logic can't find [0,3] = 0

# CORRECT: Prefix sum + hash map
def subarray_sum(nums: list[int], k: int) -> int:
    """Count subarrays summing to k. Works with negative numbers."""
    from collections import defaultdict
    
    count = 0
    prefix_sum = 0
    # Map: prefix_sum value → number of times it's occurred
    prefix_counts = defaultdict(int)
    prefix_counts[0] = 1  # Empty prefix
    
    for num in nums:
        prefix_sum += num
        # If prefix_sum - k existed before, those subarrays sum to k
        count += prefix_counts[prefix_sum - k]
        prefix_counts[prefix_sum] += 1
    
    return count

Non-Contiguous Subsequences

Two pointers / sliding window are for contiguous subarrays. If the problem asks about subsequences (not necessarily contiguous), you typically need dynamic programming or other techniques.

# Longest Increasing Subsequence: NOT a two-pointer problem
# Longest Common Subsequence: NOT a two-pointer problem
# These require DP because elements can be non-adjacent

# EXCEPTION: Two-pointer on two sorted arrays for merge/intersection
# works because both sequences are traversed in order

4.6 Performance Comparison: Two Pointers vs. Alternatives

4.7 Debugging Checklist for Two-Pointer Problems

When your solution fails on edge cases, check these in order:

1. Initialization: Are left and right starting at the correct positions? (0 and n-1 for collision; both 0 for same-direction)

2. Loop condition: left < right (pair problems) vs. left <= right (search problems) vs. right < n (sliding window)

3. Update order: In sliding window, always expand first, then check validity, then shrink. Getting the order wrong causes off-by-one errors.

4. Pointer movement after match: In Three Sum, after finding a valid triplet, you must advance BOTH pointers (not just one). Otherwise you either miss solutions or generate duplicates.

5. Empty input / single element: Always handle len(nums) < 2 (or whatever minimum makes sense) as a special case before the main loop.

6. Integer overflow: In languages with fixed-width integers (C, Java), nums[left] + nums[right] might overflow. Use (long)nums[left] + nums[right] or check before adding.

7. Window state cleanup: When removing an element from the window, check if its count reaches 0 and clean it up (delete from dict/Counter). Stale zero-count entries cause subtle comparison bugs.

# Complete debugging example: minimum window substring
def min_window_debug(s: str, t: str) -> str:
    """Version with extensive assertions for debugging."""
    from collections import Counter
    
    if not s or not t or len(s) < len(t):
        return ""
    
    need = Counter(t)
    missing = len(t)
    left = 0
    start, min_len = 0, float('inf')
    
    for right in range(len(s)):
        if need[s[right]] > 0:
            missing -= 1
        need[s[right]] -= 1
        
        assert missing >= 0, "missing should never go negative"
        
        while missing == 0:
            window_len = right - left + 1
            assert window_len >= len(t), "valid window can't be shorter than t"
            
            if window_len < min_len:
                min_len = window_len
                start = left
            
            need[s[left]] += 1
            if need[s[left]] > 0:
                missing += 1
            left += 1
            
            assert left <= right + 1, "left can't pass right"
    
    return s[start:start + min_len] if min_len != float('inf') else ""

4.8 Summary of Key Patterns

┌─────────────────────────────────────────────────────────────────┐
│              TWO POINTERS DECISION TREE                         │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  Is the array/list SORTED (or can you sort it)?                │
│  ├── YES: Is the problem about PAIRS (i,j)?                   │
│  │   ├── YES → COLLISION POINTERS (left=0, right=n-1)         │
│  │   └── NO → Consider binary search instead                  │
│  └── NO: Is it about CONTIGUOUS subarrays/substrings?         │
│      ├── YES: Is there MONOTONICITY in the constraint?         │
│      │   ├── YES → SLIDING WINDOW                              │
│      │   └── NO → Use prefix sums + hash map                  │
│      └── NO → Hash map or DP (two pointers won't work)        │
│                                                                 │
│  Is it a LINKED LIST problem?                                  │
│  ├── Cycle detection → FAST-SLOW (Floyd's)                    │
│  ├── Find middle → FAST-SLOW                                  │
│  ├── k-th from end → two pointers with k gap                  │
│  └── Merge/intersect → same-direction pointers                │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

Final thought: Two pointers and sliding window are not just "tricks" — they are manifestations of a deeper algorithmic principle. When your search space has monotone structure, you can replace exhaustive enumeration with guided traversal. The O(n²) → O(n) reduction comes not from cleverness but from understanding the mathematical properties of your problem. Every time you write a two-pointer solution, ask yourself: what invariant makes it safe to never move a pointer backward? If you can answer that, your solution is correct. If you cannot, it probably isn't.