01 — Two Pointers, Sliding Windows & Rate Limiting

At a glance

After completing this lesson you can:

• Apply two-pointer and sliding window algorithmic patterns to stream processing and string/array problems.
• Implement production-grade sliding-window log and sliding-window counter rate limiters.
• Avoid $O(n^2)$ re-scanning loops by maintaining incremental window state ($O(n)$ total).

Time: ~50 minutes · Prerequisites: 04 — Heaps, Priority Scheduling & Tries

Reading Companion

• Book: Grokking Algorithms (2nd Edition) — Aditya Y. Bhargava
• Chapter 4: Quicksort (Divide and conquer, Two-pointer partitioning).
• Book: System Design Interview (Vol. 1) — Alex Xu
• Chapter 4: Design a Rate Limiter (Token bucket, Leaking bucket, Fixed window counter, Sliding window log).

Why this matters in production

Rate limiting is the first line of defense protecting backend APIs against denial-of-service, brute force logins, and noisy neighbors. A naive fixed window counter (allow 100 reqs per minute) allows a client to send 100 requests at 00:59 and another 100 requests at 01:01—doubling the intended load spike ($200$ requests in 2 seconds!). Implementing a sliding-window rate limiter enforces an exact moving window across arbitrary time boundaries.

Deep dive

1. Two Pointers Pattern

• Opposite-Direction: Converging pointers from left = 0 and right = len(arr) - 1 (e.g., palindrome validation, Two-Sum in sorted arrays).
• Same-Direction (Fast & Slow): Pointers moving at different speeds (e.g., in-place deduplication, cycle detection).

2. Sliding Window (Fixed vs Dynamic)

Instead of recomputing window metrics from scratch on every step ($O(n imes k)$), maintain a running sum or state by adding the entering element and subtracting the departing element in $O(1)$:

Window size 3 over [2, 1, 5, 1, 3, 2]:
[2, 1, 5] -> sum=8
   [1, 5, 1] -> sum = 8 - 2 + 1 = 7
      [5, 1, 3] -> sum = 7 - 1 + 3 = 9

3. Sliding Window Rate Limiter

Given current time $t$ and window $W$:

1. Evict all stored request timestamps older than $t - W$.
2. If remaining count $< ext{limit}$, append $t$ and allow.
3. Else, reject (HTTP 429 Too Many Requests).

Hands on

python3 phase1-cs-and-architecture/02-algorithmic-patterns/01-two-pointers-and-sliding-window/examples/01_demo.py
python3 phase1-cs-and-architecture/02-algorithmic-patterns/02-algorithmic-patterns/../01-two-pointers-and-sliding-window/examples/02_trap.py

AI Trap & Code Review

# BAD AI-GENERATED CODE — O(N^2) RE-SCANNING SLIDING WINDOW
def max_subsequence_sum(nums: list[int], k: int) -> int:
    max_sum = float("-inf")
    for i in range(len(nums) - k + 1):
        s = sum(nums[i:i+k])  # Re-sums k elements every iteration -> O(n * k)!
        max_sum = max(max_sum, s)
    return max_sum

Exercises

1. Rung 1 (max_subarray_sum_fixed): Calculate maximum sum of any contiguous subarray of fixed size $k$ in single-pass $O(n)$ time.
2. Rung 2 (remove_duplicates_inplace — Fix the AI Bug): Fix a two-pointer function that deduplicates a sorted list in-place without allocating a new list, running in $O(n)$ time and $O(1)$ auxiliary space.
3. Rung 3 (min_subarray_len_target): Find minimal length of a contiguous subarray whose sum $\ge ext{target}$ using dynamic two pointers.
4. Rung 4 (SlidingWindowLogRateLimiter): Build an in-memory sliding window rate limiter accepting timestamps, evicting expired items in $O(1)$ amortized time.
5. Rung 5 (longest_substring_k_distinct): Find length of longest substring with at most $k$ distinct characters using a sliding window and hash map.

Wrapping up

Can you explain?

1. How does the sliding window pattern reduce time complexity from $O(n imes k)$ to $O(n)$?
2. What are the memory trade-offs of the Sliding Window Log rate limiter versus the Sliding Window Counter?
3. When should you use two pointers instead of a hash table?

Further Reading & References

• CPython Source: listobject.c (Dynamic Array Implementation)
• Raymond Hettinger: Modern Dictionaries by Key-Sharing
• Alex Xu: System Design Interview — Rate Limiter Design
• Tim Roughgarden: Algorithms Illuminated Series