“The secret isn’t in moving the pointers — it’s in NEVER going back. Each pointer only advances; the total distance is O(n). That’s why a nested loop can run as fast as a single one.”

This is the sixth book. If Sliding Window is the “sledgehammer” that turns countless O(n²) problems into O(n), this book teaches you why that hammer is sharp — not just the template, but the amortized analysis that makes it fast and the monotonicity condition that makes it correct.

Part 0 — The core idea: don’t go back

Two Pointers and Sliding Window are two techniques that use a few indices (pointers) sweeping over an array/string together, to avoid a nested O(n²) loop.

• Two Pointers: two indices moving through the data — either from both ends toward the middle, or in the same direction at different speeds.
• Sliding Window: keep a contiguous segment [left, right] and let it “slide” — expand on the right, shrink on the left depending on a condition.

The shared secret: monotonicity + no backtracking

What makes both techniques work is that the data has monotonicity: when you move a pointer one way, the “state” changes in a predictable direction. Thanks to that, you never need to move a pointer back — each pointer only goes forward.

Part 1 — Why O(n)? Amortized analysis

This is the insight that separates “knowing the template” from “understanding the essence.” Looking at sliding-window code, you see a for loop wrapping a while loop — it looks like O(n²). But it really is O(n). Why?

for right in range(n):        # outer loop runs n times
    ...
    while condition:          # inner loop — looks scary!
        left += 1
    ...

The key: the left pointer only INCREASES, never decreases, and is bounded by n. That means across the entire algorithm, left is incremented at most n times total — not n times per outer iteration.

• Outer loop (right): runs n times → O(n).
• Inner loop (left): the total number of runs across all outer iterations combined is ≤ n → O(n).
• Total: O(n) + O(n) = O(n). ✓

This is called amortized analysis: a single operation may cost a lot, but on average over the whole process it’s cheap, because the total work is bounded.

A.1 — Three variants

A.2 — Converging: sorted array / palindrome / two-sum

Two pointers left (from the start) and right (from the end) move toward the middle. Prerequisite: the data usually must be SORTED (so that moving a pointer has a monotonic effect on the “state”).

Two Sum on a sorted array:

def two_sum_sorted(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        s = nums[left] + nums[right]
        if s == target:
            return [left, right]
        elif s < target:
            left += 1               # need a LARGER sum → move left rightward
        else:
            right -= 1              # need a SMALLER sum → move right leftward
    return None

Why it’s correct: since the array is sorted, nums[left]+nums[right] responds monotonically to moving a pointer — moving left only increases the sum, moving right only decreases it. You always know which side to move. O(n) instead of the O(n²) of two nested loops.

Palindrome check:

def is_palindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

Container With Most Water (a greedy flavor):

def max_area(height):
    left, right = 0, len(height) - 1
    best = 0
    while left < right:
        area = min(height[left], height[right]) * (right - left)
        best = max(best, area)
        if height[left] < height[right]:   # ⭐ move the SHORTER wall
            left += 1
        else:
            right -= 1
    return best

3Sum (sort + converging):

def three_sum(nums):
    nums.sort()                     # ⭐ sort first so two pointers work
    res, n = [], len(nums)
    for i in range(n - 2):
        if i > 0 and nums[i] == nums[i-1]:
            continue                # skip duplicates for the anchor element
        left, right = i + 1, n - 1
        while left < right:
            s = nums[i] + nums[left] + nums[right]
            if s == 0:
                res.append([nums[i], nums[left], nums[right]])
                left += 1; right -= 1
                while left < right and nums[left] == nums[left-1]:
                    left += 1       # skip duplicates
                while left < right and nums[right] == nums[right+1]:
                    right -= 1
            elif s < 0:
                left += 1
            else:
                right -= 1
    return res

From O(n³) (three nested loops) down to O(n²) (one outer loop + two pointers).

A.3 — Fast-slow: in-place / linked-list cycle

Two pointers in the same direction, one fast and one slow. slow usually marks “the boundary of the processed part”, while fast scans ahead.

Remove duplicates in place (sorted array):

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]     # slow = end of the deduped result
    return slow + 1

Move zeroes to the end:

def move_zeroes(nums):
    slow = 0
    for fast in range(len(nums)):
        if nums[fast] != 0:
            nums[slow], nums[fast] = nums[fast], nums[slow]
            slow += 1                   # slow = next slot for a non-zero

Detect a cycle in a linked list (Floyd’s — tortoise & hare):

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next            # move 1 step
        fast = fast.next.next       # move 2 steps
        if slow == fast:            # ⭐ they meet → there IS a cycle
            return True
    return False

🔗 Link to the Graph book: this is exactly cycle detection with two pointers! If there’s a loop, the hare (fast) will “catch up” to the tortoise (slow) from behind inside the loop. Floyd’s is the two-pointer version of cycle detection, using only O(1) memory.

A.4 — Two pointers over two arrays (merge)

Each pointer scans one sorted array, compares, and advances the smaller one — exactly the “merge” step of Merge Sort:

def merge_sorted(a, b):
    i, j, result = 0, 0, []
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            result.append(a[i]); i += 1
        else:
            result.append(b[j]); j += 1
    result.extend(a[i:])                # leftover of whichever array remains
    result.extend(b[j:])
    return result

Representatives: Merge Two Sorted Lists, Intersection of Two Arrays, Merge Sorted Array. O(n+m).

A.5 — When Two Pointers works

• ✅ Sorted data (or sortable) — so moving a pointer has a monotonic effect (converging).
• ✅ Problems about pairs / triples satisfying a sum condition (two-sum, 3sum, 4sum).
• ✅ Palindrome or symmetry (converging).
• ✅ In-place array edits (O(1) memory): remove/compact elements (fast-slow).
• ✅ Cycle / middle of a linked list (fast-slow).
• ✅ Merge / intersect / union of two sorted sequences (two arrays).

⚠️ The vital condition: converging two pointers need monotonicity — moving a pointer must change the “state” in a predictable direction. That’s why the array usually must be sorted. No monotonicity → two pointers don’t apply.

B.1 — Two kinds: fixed vs variable

Sliding Window solves problems about a contiguous segment/substring. There are two kinds:

Signature of a sliding-window problem: it mentions a “CONTIGUOUS subarray/substring” (not a scattered subsequence — that’s DP/LIS) and asks for “longest / shortest / count the segments satisfying a condition”.

B.2 — The UNIVERSAL TEMPLATE for a variable window

This is the golden part of Part B. Almost every variable sliding-window problem fits the three-step skeleton below. Memorize it and you can handle a huge class of problems.

def sliding_window(s):
    window = {}                     # window state (char counts, sum, #distinct...)
    left = 0
    result = 0                      # or float('inf') for a "shortest" problem

    for right in range(len(s)):
        # ── STEP 1: EXPAND — add s[right] to the window ──
        add s[right] to window

        # ── STEP 2: SHRINK — while the window is INVALID, move left ──
        while window_violates_condition:
            remove s[left] from window
            left += 1

        # ── STEP 3: UPDATE the answer (window [left, right] is now valid) ──
        result = max(result, right - left + 1)

    return result

        left                    right
         │                        │
   ┌─────┼────────────────────────┼─────┐
   │     [   current valid window  ]     │
   └─────┼────────────────────────┼─────┘
         │                        │
    shrink when            expand each step
    invalid                (right always advances)

Example — Longest substring without repeating characters

def length_of_longest_substring(s):
    window = set()
    left = best = 0
    for right in range(len(s)):
        while s[right] in window:       # INVALID: a repeated character
            window.remove(s[left])      # shrink left until no repeat
            left += 1
        window.add(s[right])            # now it's safe to add
        best = max(best, right - left + 1)
    return best

The “shortest” variant — Minimum Window Substring (harder)

When it asks for the shortest segment, the structure flips: expand until valid, then shrink to minimize:

from collections import Counter

def min_window(s, t):
    need = Counter(t)
    missing = len(t)                    # how many characters are still missing
    left = 0
    best, best_len = "", float('inf')
    for right, ch in enumerate(s):
        if need[ch] > 0:
            missing -= 1
        need[ch] -= 1
        while missing == 0:             # ⭐ window ALREADY contains all of t → shrink to minimize
            if right - left + 1 < best_len:
                best_len = right - left + 1
                best = s[left:right+1]
            need[s[left]] += 1
            if need[s[left]] > 0:       # dropping it makes us miss again
                missing += 1
            left += 1
    return best

B.3 — Fixed window

When the size k is fixed, no growing/shrinking is needed — just “slide”: add the new element on the right, drop the old one on the left.

def max_sum_subarray(nums, k):
    window_sum = sum(nums[:k])          # the first window
    best = window_sum
    for right in range(k, len(nums)):
        window_sum += nums[right] - nums[right - k]   # ⭐ add new, DROP old
        best = max(best, window_sum)
    return best

B.4 — Counting windows: the “at most K” trick

“Count segments that satisfy exactly K” is often hard directly. The magic trick:

Exactly K = (At most K) − (At most K−1)

Because “at most K” is easy to count with a sliding window, and the subtraction cancels the “at most K−1” part, leaving exactly the “exactly K” part.

from collections import defaultdict

def at_most_k_distinct(nums, k):        # #subarrays with AT MOST k distinct elements
    count = defaultdict(int)
    left = result = 0
    for right in range(len(nums)):
        count[nums[right]] += 1
        while len(count) > k:           # invalid: more than k kinds
            count[nums[left]] -= 1
            if count[nums[left]] == 0:
                del count[nums[left]]
            left += 1
        result += right - left + 1      # ⭐ #valid subarrays ENDING at right
    return result

def exactly_k_distinct(nums, k):
    return at_most_k_distinct(nums, k) - at_most_k_distinct(nums, k - 1)

B.5 — Sliding Window Maximum (monotonic deque)

A classic: find the maximum in each sliding window of size k. Use a monotonic deque storing indices in decreasing value order.

from collections import deque

def max_sliding_window(nums, k):
    dq = deque()                        # store INDICES, values decreasing front → back
    result = []
    for i in range(len(nums)):
        if dq and dq[0] <= i - k:       # drop indices that slid out of the window (at front)
            dq.popleft()
        while dq and nums[dq[-1]] < nums[i]:   # drop values smaller than nums[i] (useless)
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            result.append(nums[dq[0]])  # ⭐ the deque's front is always the window MAX
    return result

Why O(n): each index enters the deque exactly once and leaves at most once → total operations O(n) (amortized analysis again!).

🔗 Link to the DP book: this is exactly the “monotonic queue optimization” — the thing that turns many O(n²) DP transitions into O(n). Sliding window maximum is its purest form.

⚠️ KEY BOUNDARY — sliding window and negative numbers: Sliding window relies on the assumption that “adding an element makes the window ‘worse’ in one direction.” With negative numbers, that assumption collapses — adding a negative may decrease the sum, breaking monotonicity. For example, “count subarrays with sum = K” with negatives: sliding window is WRONG; you must use prefix sum + hashmap:

def subarray_sum_equals_k(nums, k):
    from collections import defaultdict
    prefix, count = 0, defaultdict(int)
    count[0] = 1                    # the empty prefix
    result = 0
    for x in nums:
        prefix += x
        result += count[prefix - k] # how many earlier prefixes give a segment sum = k
        count[prefix] += 1
    return result

This is an extremely common trap: you see “subarray” and reflexively reach for sliding window, but with negatives you must use prefix sum. Remember this boundary!

💀 Pitfall #1: Sliding Window with negatives

The technique assumes monotonicity; negatives break it. “Subarray sum = K” with negatives → use prefix sum + hashmap, not sliding window.

💀 Pitfall #2: Off-by-one in window size

The size of window [left, right] is right - left + 1 (with the +1!). Forgetting the +1 is a classic bug. Sanity-check with a tiny example: left=right → size 1.

💀 Pitfall #3: Wrong ORDER of the three steps

In the template: expand → shrink → update. For a “longest” problem, update after shrinking (the new window is valid). Updating in the wrong place → you count invalid windows.

💀 Pitfall #4: Two pointers on an UNSORTED array

Converging two pointers need monotonicity (usually a sorted array). Forgetting to sort before 3Sum/two-sum-sorted → wrong result.

💀 Pitfall #5: Forgetting to handle duplicates (3Sum, 4Sum)

Not skipping duplicates → you produce repeated tuples. Remember the lines while ... nums[left] == nums[left-1]: left += 1.

💀 Pitfall #6: Fast-slow on a linked list — forgetting the null check

fast.next.next crashes if fast or fast.next is None. Always check while fast and fast.next first.

💀 Pitfall #7: Confusing “contiguous subarray” with “scattered subsequence”

Sliding window is only for CONTIGUOUS segments. If the problem lets you skip middle elements (a subsequence) → that’s DP (like LIS), not sliding window.

1. Two Pointers ~ Greedy thinking. “Always move the shorter wall” (Container With Most Water) is a greedy argument — discard choices that can’t be optimal.
2. Fast-slow ~ cycle detection. Floyd’s tortoise-hare is the two-pointer version of graph cycle detection — using only O(1) memory.
3. Sliding Window Maximum = monotonic queue. Exactly the DP-optimization technique that drops O(n²) to O(n).
4. Prefix Sum — also a DP optimization, and the “savior” when sliding window meets negatives.
5. Monotonicity ~ Binary Search. The “monotone” condition that makes two pointers/sliding window work is the same essence as the condition that makes binary search work — all three exploit monotone structure to skip redundant work.

Four questions for any array/string problem: (1) Contiguous subarray or scattered? (2) Any negative numbers? (3) Is the data sorted? (4) Asking about pairs/tuples (→two pointers) or longest/shortest segment (→sliding window)?

Problem names in LeetCode style.

🟢 Level 1 — Getting started

• Two Sum II (Input Array Is Sorted) — the most basic converging two pointers.
• Valid Palindrome — converging, checking symmetry.
• Move Zeroes / Remove Duplicates from Sorted Array — in-place fast-slow.
• Maximum Average Subarray I — fixed window.

🟡 Level 2 — Applying

• Longest Substring Without Repeating Characters — the classic sliding-window template, a must-know.
• 3Sum — sort + two pointers, handling duplicates.
• Container With Most Water — converging with a greedy flavor.
• Fruit Into Baskets — sliding window “at most 2 kinds” (i.e., at-most-K).
• Linked List Cycle — Floyd’s tortoise-hare.

🔴 Level 3 — Advanced

• Minimum Window Substring — the “shortest” sliding window, a hard variant.
• Longest Repeating Character Replacement — a window with a subtle condition.
• Subarrays with K Different Integers — the exactly K = atMost(K) − atMost(K−1) trick.
• Sliding Window Maximum — monotonic deque.
• Subarray Sum Equals K — ⚠️ the negatives trap, must use prefix sum + hashmap (not sliding window!).

⚫ Final bosses

• Minimum Number of K Consecutive Bits Flips — sliding window + a clever flip trick.
• Count Number of Nice Subarrays — at-most-K over parity.
• Trapping Rain Water — advanced converging two pointers (or a stack).
• Find All Anagrams in a String — fixed window + character counts.
• Prove by hand: why sliding window is O(n) (amortized); why it breaks with negatives.

🏋️ Practice principle: for every problem, before coding answer the four questions in Part F. Especially the two crucial ones: “Any negatives?” (decides sliding window vs prefix sum) and “Contiguous or scattered?” (decides sliding window vs DP). Picking the wrong tool up front is wrong at the root.

🎓 Closing — The mantra of Two Pointers & Sliding Window

Wrap the whole book into five mantras:

1. Pointers only advance, never go back. That’s why a nested loop runs O(n) — count total pointer steps, not loops.
2. Sliding Window is same-direction Two Pointers. One idea, “sweep once”; the 3-step template handles a whole class of problems.
3. Monotonicity is the vital condition. Two pointers need a sorted array; sliding window needs a “monotone window” (usually non-negative values). Lose monotonicity → lose the technique.
4. Negatives are the spoiler. “Subarray sum = K” with negatives → sliding window breaks; switch to prefix sum + hashmap. This is the deadliest trap.
5. Distinguish contiguous vs scattered. Contiguous segment → sliding window; scattered subsequence → DP. Misreading it is wrong at the root.

Practice all four levels in Part G, asking the four framing questions each time — after about 30–40 problems, you’ll instantly “smell” which is two pointers, which is sliding window, and which is a prefix-sum trap in disguise. That’s when you’ve mastered the art of the single pass. 🎯