Conceptual Foundation & Intuitive Analogy
🧭 Conceptual Foundation & Pattern Intuition
When an array is sorted, elements possess a strict monotonic spatial order: moving to the right guarantees larger numbers, while moving to the left guarantees smaller numbers. In an unsorted array, locating a pair that sums to a target requires an hash set. But with sorted data, the space overhead can be eliminated entirely: by placing two pointers at opposite ends, the sum of the boundary elements acts as an infallible guide. If their sum is too small, the left boundary is permanently inadequate and must advance. If their sum is too large, the right boundary must retreat.
🏟️ The Analogy: The Balancing Seesaw
Imagine two people on a giant seesaw trying to balance a target weight. On the left side is a line of light weights arranged from lightest to heaviest; on the right side is a line of heavy weights arranged from heaviest to lightest. If the scale tips too low (sum is less than target), replacing the current light weight with an even lighter weight would make the deficit worse; you must step forward to a heavier light weight. If the scale tips too high, you must step back to a lighter heavy weight. You never need to restart or reconsider discarded weights.
🔑 Why It Works
The proof of correctness is absolute: at step cur_sum < target, numbers[left] + numbers[k] < target for all because numbers[k] <= numbers[right]. Therefore, numbers[left] can never participate in any valid solution. Discarding it permanently via left += 1 is mathematically airtight.
The invariant to say out loud: "Everything I have moved past can never be part of a better answer than the one I already recorded — so I never have to look at it again." If you cannot say that sentence about your problem, two pointers is unsound and you need prefix sums, a hash map, or a heap instead.
Opposite boundaries step inward. Outer pairs are strictly dominated by sortedness or geometric width. Works with negative numbers (Two Sum II, 3Sum, Squares of Sorted Array) because monotonicity relies on sorted positional order (A[i] ≤ A[j]), not element signs.
Same-direction traversal maintaining contiguous state. FAILS on negative numbers for sum/product: evicting a negative increases sum and adding one decreases it, destroying window monotonicity!
The negative numbers rescue. When negative numbers break sliding window monotonicity, prefix sums transform contiguous range searches into algebraic point lookups: P[L] = P[R+1] - target, recovering strict O(N) via hash map.
YES for Converging / Squeeze: On sorted arrays (e.g. Two Sum II, 3Sum, Squares of Sorted Array), negative numbers work natively because monotonicity is governed by sorted index order (A[i] ≤ A[j]), not signs.
NO for Sliding Window Sums: If elements can be negative, expanding can decrease the sum and contracting can increase it. Monotonicity collapses! Pivot immediately to Prefix Sum + Hash Map (LC 560) or Monotonic Deque (LC 862).
The 15 Mental Models of Two Pointers & Sliding Window
Two Pointers problems divide by how the pointers move, what the window holds, and what a lookup remembers. Name the model before coding.
1Hash Map
items ➔ computed key ➔ dict lookup or count in O(1)Hashing & Frequency Maps (Group Anagrams, Two Sum)
| 1 | from collections import defaultdict |
| 2 | |
| 3 | |
| 4 | def group_anagrams(strs: list[str]) -> list[list[str]]: |
| 5 | """Group Anagrams: words with the same sorted letters share one key in a hash map. |
| 6 | Time: O(N * K log K) | Space: O(N * K) |
| 7 | """ |
| 8 | groups: dict[str, list[str]] = defaultdict(list) # key -> every word read so far with that key |
| 9 | # 1. File Each Word Under Its Key: |
| 10 | # Words with the same letters and the same counts produce the same sorted-letters key ("eat", "tea" -> "aet"), so every anagram lands in the same group without comparing any two words. |
| 11 | for s in strs: |
| 12 | key = "".join(sorted(s)) |
| 13 | groups[key].append(s) |
| 14 | return list(groups.values()) |
| 15 | |
| 16 | |
| 17 | def two_sum(nums: list[int], target: int) -> list[int]: |
| 18 | """Two Sum: remember each value's index, and look up the partner each new value needs. |
| 19 | Time: O(N) | Space: O(N) |
| 20 | """ |
| 21 | index_of: dict[int, int] = {} # value -> an index where it was seen |
| 22 | # 1. Look Up The Partner Before Storing: |
| 23 | # If target - num was already seen, its stored index completes the pair; storing num only after the lookup keeps num from ever pairing with itself. |
| 24 | for i, num in enumerate(nums): |
| 25 | partner = target - num |
| 26 | if partner in index_of: |
| 27 | return [index_of[partner], i] |
| 28 | index_of[num] = i |
| 29 | return [] # LeetCode guarantees exactly one answer, so this line is never reached |
A hash map finds a key's entry in one step, so pick the key the question is about and store under it what the answer needs: in group_anagrams the key is a word's sorted letters and the value is every word read so far with that key; in two_sum the key is a number and the value is its index. Items that belong together produce equal keys, so groups[key].append(s) files every anagram in one pass without comparing any two words, and partner in index_of finds an earlier number that completes the pair without a second loop. The trap is a lossy key: it must be equal only for items that truly belong together, so key on "".join(sorted(s)), which keeps repeated letters, never on frozenset(s) or set(s), which drop them and put "aab" and "abb" in one group.
Gotcha 1 of 4
- The trap
Gotcha 1: Keying on
frozenset(s)instead of the sorted lettersMistakekey = frozenset(s)Fixkey = "".join(sorted(s))What happens: A set keeps each letter once and drops the repeats.
"aab"and"abb"both give the set ofaandb. They land in one group, but they are not anagrams."".join(sorted(s))keeps every letter, repeats included.Example: strs = ["aab", "abb"]Mistake: returns [['aab', 'abb']]Fix: returns [['aab'], ['abb']]
Bucket Sort (Top K Frequent, Maximum Gap)
min to max), and you need their order, the top k, or the largest gap in linear time, without an O(n log n) sort.| 1 | def maximum_gap(nums: list[int]) -> int: |
| 2 | """Maximum Gap: pigeonhole buckets, compare neighbours across buckets only. |
| 3 | Time: O(N) | Space: O(N) |
| 4 | """ |
| 5 | # 1. Handle Too Few Values: |
| 6 | # With fewer than two values there is no neighbour at all, so no gap can be measured. |
| 7 | n = len(nums) |
| 8 | if n < 2: |
| 9 | return 0 |
| 10 | |
| 11 | # 2. Size The Buckets From The Pigeonhole Bound: |
| 12 | # The largest gap is at least the average gap (hi - lo) / (n - 1); max(1, ...) keeps every |
| 13 | # bucket at least one value wide so the later division never hits zero. |
| 14 | lo, hi = min(nums), max(nums) |
| 15 | width = max(1, (hi - lo) // (n - 1)) |
| 16 | count = (hi - lo) // width + 1 # Enough buckets to hold hi as well |
| 17 | bucket_min = [float("inf")] * count # Smallest value that fell in each bucket |
| 18 | bucket_max = [float("-inf")] * count # Largest value that fell in each bucket |
| 19 | |
| 20 | # 3. Drop Each Value Into Its Bucket, Keeping Only The Extremes: |
| 21 | # No two values are compared here; because width is at most the smallest possible gap, the |
| 22 | # answer can never sit inside one bucket, so only its smallest and largest value matter. |
| 23 | for x in nums: |
| 24 | b = (x - lo) // width |
| 25 | bucket_min[b] = min(bucket_min[b], x) |
| 26 | bucket_max[b] = max(bucket_max[b], x) |
| 27 | |
| 28 | # 4. Walk The Buckets In Order And Measure Cross-Bucket Gaps: |
| 29 | # Skipping empty buckets and carrying prev_max forward means each gap is measured from the |
| 30 | # last non-empty bucket's maximum to the next non-empty bucket's minimum. |
| 31 | best = 0 |
| 32 | prev_max = lo |
| 33 | for b in range(count): |
| 34 | if bucket_min[b] == float("inf"): |
| 35 | continue |
| 36 | best = max(best, bucket_min[b] - prev_max) |
| 37 | prev_max = bucket_max[b] |
| 38 | |
| 39 | return best |
Bucket Sort drops each value straight into the bucket that covers its range, b = (x - lo) // width, so placing a value needs no comparison with other values and the buckets come out in order. The key can be any bounded number: bucket by value range to find gaps, or by count to order items by frequency. For the largest gap between neighbours, keep only bucket_min[b] and bucket_max[b], walk the buckets once, and measure bucket_min[b] - prev_max, where prev_max is the largest value of the last non-empty bucket. That is enough because of the pigeonhole principle: n values from lo to hi leave n - 1 gaps that add up to hi - lo, so the largest gap is at least their average, and being a whole number it is at least width whenever hi > lo. Two values in the same bucket differ by at most width - 1, so the maximum gap is never inside one bucket: it always runs from one bucket's maximum to a later bucket's minimum, and the values in between never matter. The trap is the floor of 1: when hi - lo < n - 1, for example with repeated values, (hi - lo) // (n - 1) is 0 and (x - lo) // width divides by zero, so write width = max(1, (hi - lo) // (n - 1)).
Gotcha 1 of 4
- The trap
Gotcha 1: Computing
widthwithout the floor of 1Mistakewidth = (hi - lo) // (n - 1)Fixwidth = max(1, (hi - lo) // (n - 1))What happens: With repeated values,
hi - locan be smaller thann - 1. Then(hi - lo) // (n - 1)is 0. The next division,(hi - lo) // width, divides by zero.max(1, ...)keeps every bucket at least one value wide.Example: nums = [1, 1, 1, 4, 2]Mistake: raises ZeroDivisionErrorFix: returns 2
3Converging Pointers
left -> <- right (Opposite Boundary Contraction)Two Pointers (Opposite Ends)
| 1 | from typing import Callable, List, Optional, Tuple |
| 2 | |
| 3 | |
| 4 | def converge(n: int, compare: Callable[[int, int], int]) -> Optional[Tuple[int, int]]: |
| 5 | """Converging Pointers: squeeze a pair of indices (left, right) inward from both ends of a sorted sequence of length n. |
| 6 | compare(left, right) returns 0 to stop at this pair, below 0 to move left, and above 0 to move right. |
| 7 | Precondition: each step can rule out the element at left or the element at right for good, and compare says which one. |
| 8 | For a pair sum on a sorted sequence, move left when the pair is too small and move right when it is too big. |
| 9 | compare may also record an answer and return a nonzero value to keep going, as in Container With Most Water and 3Sum. |
| 10 | In Valid Palindrome, a match moves both pointers, so that loop moves left and right together. |
| 11 | T = the cost of one compare call. |
| 12 | Time: O(N * T) | Space: O(1) |
| 13 | """ |
| 14 | left, right = 0, n - 1 # left and right only ever move toward each other |
| 15 | |
| 16 | # 1. Squeeze Inward While Not Met: |
| 17 | # compare rules out the element at left or at right for good on every step, so only the ruled-out end moves and the pair found, if any, is always still between left and right. |
| 18 | while left < right: |
| 19 | order = compare(left, right) |
| 20 | if order == 0: |
| 21 | return (left, right) |
| 22 | elif order < 0: |
| 23 | left += 1 # The pair is too small: the element at left cannot pair with any remaining element |
| 24 | else: |
| 25 | right -= 1 # The pair is too big: the element at right cannot pair with any remaining element |
| 26 | |
| 27 | return None |
Start one pointer at each end of a sorted array. If the pair's sum is too small, only moving left right can raise it; if it is too big, only moving right left can lower it.
Each step rules out one element for good: when curr_sum < target, numbers[left] is already paired with the largest value left, so no remaining partner can reach target (and the mirror holds for right). This works with negative numbers too, because it relies on sorted order, not on signs.
The trap is unsorted input: there, moving a pointer no longer raises or lowers the sum, so the squeeze can walk past the answer; sort first, and keep the original indices if the problem asks for them.
Gotcha 1 of 5
- The trap
Gotcha 1: Running the squeeze on an unsorted array
MistaketwoSum(nums, target)FixtwoSum(sorted(nums), target)What happens: When
curr_sum < target, the loop movesleftone step right to raise the sum. A larger value atleftis certain only whennumsis sorted. On unsorted input, a move can lower the sum, and the loop walks past the pair. Sorting first finds the pair, but it returns positions in the sorted list. Two Sum (LC 1) wants the original indices, so sort(value, index)pairs instead.Example: nums = [1, 4, 2, 3], target = 5Mistake: returns []Fix: returns [1, 4]
4Dummy Node
list whose head may change ➔ dummy.next = head ➔ rewire through prev, return dummy.nextSentinel / Dummy Node
| 1 | from typing import Optional |
| 2 | |
| 3 | class ListNode: |
| 4 | def __init__(self, val: int = 0, next: Optional["ListNode"] = None): |
| 5 | self.val = val |
| 6 | self.next = next |
| 7 | |
| 8 | def remove_elements(head: Optional[ListNode], val: int) -> Optional[ListNode]: |
| 9 | """Remove Linked List Elements: a dummy head makes deleting the real head ordinary. |
| 10 | Time: O(N) | Space: O(1) |
| 11 | """ |
| 12 | dummy = ListNode(0, head) # Every real node now has a previous node |
| 13 | prev = dummy |
| 14 | |
| 15 | # 1. Walk And Unlink Matching Nodes: |
| 16 | # prev always stays on the last kept node, so prev.next = prev.next.next removes the head the same way it removes any other node, and staying put after a removal lets the new prev.next be checked too. |
| 17 | while prev.next: |
| 18 | if prev.next.val == val: |
| 19 | prev.next = prev.next.next |
| 20 | else: |
| 21 | prev = prev.next |
| 22 | |
| 23 | # 2. Return Through The Dummy, Not head: |
| 24 | # head itself may have been removed, so dummy.next, not head, is always the current first real node. |
| 25 | return dummy.next |
The head is the only node without a previous node, which is why deleting or inserting at the head usually needs its own if. A dummy node placed before head gives every real node a previous node, so prev.next = prev.next.next removes the head like any other node. The sentinel does not have to be a node. It can be a virtual index, value or bar that is never stored in the data. It gives the first and the last element the same rule as every other element. Missing Ranges (LC 163) starts with prev = lower - 1 and ends with curr = upper + 1, so the gap before the first number and the gap after the last number use the same check as every gap between two numbers. Largest Rectangle in Histogram (LC 84) adds a bar of height 0 at the end, so the bars still on the stack are handled by the same rule. The trap is returning head: when the first node is removed, head still points at the deleted node, so return dummy.next.
Gotcha 1 of 5
- The trap
Gotcha 1: Returning
headinstead ofdummy.nextMistakereturn headFixreturn dummy.nextWhat happens:
headstill points at the first node of the input. When that node holdsval, the loop unlinks it fromdummy, butheaddoes not change. Returningheadreturns a list that starts with a deleted node.Example: head = [6, 6, 1, 2, 6, 3], val = 6Mistake: returns [6, 6, 1, 2, 3]Fix: returns [1, 2, 3]
Boyer-Moore Voting (Majority Element)
n / k for a small k), and you must find it in one pass with O(1) extra space, so no count per value.| 1 | def majority_element(nums: list[int]) -> int: |
| 2 | """Majority Element: pair off different values; the majority is the value left standing. |
| 3 | Time: O(N) | Space: O(1) |
| 4 | """ |
| 5 | # candidate, count: the value currently "standing" and how many of its copies are not yet |
| 6 | # paired off against a different value. |
| 7 | candidate, count = None, 0 |
| 8 | |
| 9 | # 1. Decide This Value's Role, Then Update The Tally: |
| 10 | # Everything read before a count of 0 is already paired off, so x starts a new run; |
| 11 | # counting after that check means x always counts as its own first copy, and count never |
| 12 | # goes below 0. |
| 13 | for x in nums: |
| 14 | if count == 0: |
| 15 | candidate = x |
| 16 | count += 1 if x == candidate else -1 |
| 17 | |
| 18 | # 2. Report The Value Left Standing: |
| 19 | # A value that fills more than half of nums has more copies than everything else combined, |
| 20 | # so pairing off different values can never cancel it; it is the one still standing at the end. |
| 21 | return candidate |
Let every value cancel one copy of a different value: a value that fills more than half of nums has more copies than all the others together, so it can't be cancelled out, and the code only has to remember what is still standing, candidate and count. When count == 0 everything read so far is paired off, so x becomes the new candidate; then count += 1 if x == candidate else -1 either adds a copy or removes a pair of two different values, at most one of them the majority, which is why the majority is the candidate left at the end. The trap is trusting that survivor: it is the answer only when a majority is promised (in the middle of [2,2,1,1,1,2,2] the candidate is 1, and on [1, 2, 3] the survivor occurs once), so when the promise is missing, count the survivor again in a second pass.
Gotcha 1 of 4
- The trap
Gotcha 1: Returning
candidatewhen no majority is promisedMistakereturn candidateFixif nums.count(candidate) > len(nums) // 2: return candidate return NoneWhat happens: The last
candidateis the majority only when a majority exists. Majority Element (LC 169) promises one, so the blueprint can return it. Without that promise, the survivor can be any value. Count it in a second pass before returning it.Example: nums = [1, 2, 3], with no majority promisedMistake: returns 3Fix: returns None
6KMP
Knuth-Morris-Pratt (KMP) String Matching
| 1 | def str_str(haystack: str, needle: str) -> int: |
| 2 | """KMP: find needle in haystack without ever moving back in haystack. |
| 3 | Time: O(N + M) | Space: O(M) |
| 4 | """ |
| 5 | m = len(needle) |
| 6 | # lps[i]: the longest proper prefix of needle[:i + 1] that is also its suffix (its longest border). |
| 7 | lps = [0] * m |
| 8 | k = 0 # Length of the prefix of needle matched so far |
| 9 | |
| 10 | # 1. Build The Border Table From needle Against Itself: |
| 11 | # Building lps runs the same search on needle against itself, so a mismatch falls back to a |
| 12 | # shorter border the same way the main search below does. |
| 13 | for i in range(1, m): |
| 14 | while k > 0 and needle[i] != needle[k]: |
| 15 | k = lps[k - 1] |
| 16 | if needle[i] == needle[k]: |
| 17 | k += 1 |
| 18 | lps[i] = k |
| 19 | |
| 20 | # 2. Scan haystack Once, Falling Back Instead Of Restarting: |
| 21 | # On a mismatch, the k letters just matched are needle[:k], already known, so k falls back |
| 22 | # to the longest border that still fits; the match ends at i, so it starts i - m + 1 letters |
| 23 | # earlier. |
| 24 | k = 0 |
| 25 | for i, ch in enumerate(haystack): |
| 26 | while k > 0 and ch != needle[k]: |
| 27 | k = lps[k - 1] |
| 28 | if ch == needle[k]: |
| 29 | k += 1 |
| 30 | if k == m: |
| 31 | return i - m + 1 |
| 32 | return -1 |
KMP never reads a character of the text twice: when a mismatch comes after k matched letters, those letters are needle[:k], which you already know, so the search keeps their longest border, k = lps[k - 1], and tries the same letter again instead of moving the start forward by one and re-reading. It is correct because a match that is still possible must begin at a suffix of what was read that is also a prefix of needle, and lps[k - 1] is the longest such part; falling back again while k > 0 and ch != needle[k] visits every shorter one in order, and lps itself is built by running the same loop on needle against itself. The trap is resetting k = 0 on a mismatch: on haystack = "abababc", needle = "ababc" it throws away the border "ab" at i = 4, where the only match begins, and returns -1 instead of 2.
Gotcha 1 of 4
- The trap
Gotcha 1: Resetting
k = 0on a mismatchMistakewhile k > 0 and ch != needle[k]: k = 0Fixwhile k > 0 and ch != needle[k]: k = lps[k - 1]What happens: After
kmatched letters, the text just read isneedle[:k]. Its end can also be the start ofneedle. A match can then begin inside the failed attempt.k = 0throws that start away, and the search can miss the match.k = lps[k - 1]keeps it.Example: haystack = "abababc", needle = "ababc"Mistake: returns -1Fix: returns 2
7Fixed Window
i >= k -> (Absorb Incoming, Evict Outgoing)Fixed-Size Sliding Window
k is given and you measure every window: averages, counts, anagram matches.| 1 | from typing import Callable, List |
| 2 | |
| 3 | |
| 4 | def slide_fixed(n: int, k: int, add: Callable[[int], None], remove: Callable[[int], None], record: Callable[[int], None]) -> None: |
| 5 | """Fixed Window: visit every window of exactly k indices in 0..n-1, one index in and one out per step. |
| 6 | Precondition: n, the number of indices, is known before the loop starts, and k >= 1. |
| 7 | record(start) is called once per window, after the window holds indices start..start + k - 1. |
| 8 | T = the cost of one add, remove or record call. |
| 9 | Time: O(N * T) | Space: O(1) besides the window's state |
| 10 | """ |
| 11 | # 1. Handle Impossible Case: |
| 12 | # Fewer than k indices exist, so no window of length k can ever form. |
| 13 | if n < k: |
| 14 | return |
| 15 | |
| 16 | # 2. Build First Window: |
| 17 | # Add every index from 0 to k - 1 so the window holds its first k indices before any sliding starts. |
| 18 | for i in range(k): |
| 19 | add(i) |
| 20 | record(0) |
| 21 | |
| 22 | # 3. Slide One Step At A Time: |
| 23 | # Add the incoming index i, remove the outgoing index i - k, then record only after both updates land so the window always holds exactly k indices when it is read. |
| 24 | for i in range(k, n): |
| 25 | add(i) |
| 26 | remove(i - k) |
| 27 | record(i - k + 1) |
Every window has the length k = len(p), so build the first window's counts once, then slide one step at a time: add the letter entering on the right and remove the one leaving on the left. Each slide changes exactly two letters of the window, so updating window_count for s[i] and s[i - k] keeps it equal to the counts of the k characters ending at i without recounting the whole window, and window_count == p_count then says whether that window is an anagram of p. The trap is the index of the leaving letter: when s[i] enters, s[i - k] leaves; an off-by-one there shifts every window, so the windows compared are the wrong ones.
Gotcha 1 of 5
- The trap
Gotcha 1: Removing
s[i - k + 1]instead ofs[i - k]Mistakewindow_count[ord(s[i - k + 1]) - ord('a')] -= 1Fixwindow_count[ord(s[i - k]) - ord('a')] -= 1What happens: Before the step, the window is
s[i - k..i - 1]. Whens[i]enters, the letter that leaves iss[i - k]. Removings[i - k + 1]takes out a letter that is still in the window. The counts then match no real window. The result lists wrong start indices.Example: s = "cbaebabacd", p = "abc"Mistake: returns [0, 3, 4, 5]Fix: returns [0, 6]
8Longest Window
left -> right -> (Check Before Growing, Contract To Repair)Variable-Size Sliding Window (Longest Window)
| 1 | from typing import Callable |
| 2 | |
| 3 | |
| 4 | def longest_window(n: int, add: Callable[[int], None], remove: Callable[[int], None], would_be_valid: Callable[[int], bool]) -> int: |
| 5 | """Longest Window: the length of the longest valid window [left, right] of indices 0..n-1. |
| 6 | Precondition: every shorter window inside a valid window is valid too, and the empty window is valid. |
| 7 | add(i) and remove(i) update the window's state for index i. |
| 8 | would_be_valid(i) reads whether adding index i to the current window would keep it valid, without changing the window's state. |
| 9 | T = the cost of one add, remove or would_be_valid call. |
| 10 | Time: O(N * T) | Space: O(1) besides the window's state |
| 11 | """ |
| 12 | left = 0 |
| 13 | max_len = 0 |
| 14 | |
| 15 | for right in range(n): |
| 16 | # 1. Repair By Evicting From left: |
| 17 | # would_be_valid(right) asks whether adding index right would still be a valid window, without changing the window's state. Every window [j, right] with j < left contains everything [left, right] contains, so if adding right to [left, right] would still be invalid, no later left can keep right out of it; evicting left is the only way back to a window that right can be added to. |
| 18 | while not would_be_valid(right): |
| 19 | remove(left) |
| 20 | left += 1 |
| 21 | # 2. Absorb Index right: |
| 22 | # Once would_be_valid(right) confirms the window stays valid, right is actually added. |
| 23 | add(right) |
| 24 | # 3. Record Only After The Add: |
| 25 | # The window [left, right] is now valid and fully updated, so its length can be measured. |
| 26 | max_len = max(max_len, right - left + 1) |
| 27 | |
| 28 | return max_len |
Before you add right to the window, check whether adding it would break the rule. If it would, move left forward until adding right is safe, then add right and record the window's length.
The window is always valid at the moment you add right, because right is only added once the check says adding it keeps the window valid, so the largest measurement is the answer. Moving left never loses a longer answer: any window that starts before left already contains everything [left, right] contains, so adding right to it would break the rule too.
The trap is answering the check by mutating the window's state to test it: the check must read what adding right would do without changing the window, or the add call right after it double-counts right.
Gotcha 1 of 4
- The trap
Gotcha 1: Measuring the window before the
whileloop repairs itMistakefor right in range(len(s)): max_len = max(max_len, right - left + 1) while s[right] in seen_chars:Fixfor right in range(len(s)): while s[right] in seen_chars:What happens: Before the
whileloop,s[right]may already be in the window. Then the windows[left..right]holds a letter twice. A length measured there counts an invalid window, somax_lencan become too large. Thewhileloop movesleftuntil the repeat is gone. After that loop,right - left + 1is the length of a valid window.Example: s = "abcabcbb"Mistake: returns 4Fix: returns 3
9Fast & Slow Pointers
slow (1x) vs fast (2x) (Velocity Differential)Fast & Slow Pointers (Floyd's Tortoise and Hare)
next = nums[i]) may contain a loop, or you need its middle in one pass with O(1) extra space.| 1 | from typing import Optional |
| 2 | |
| 3 | class ListNode: |
| 4 | def __init__(self, val: int = 0, next: Optional["ListNode"] = None): |
| 5 | self.val = val |
| 6 | self.next = next |
| 7 | |
| 8 | def find_cycle_entrance(head: Optional[ListNode]) -> Optional[ListNode]: |
| 9 | """Linked List Cycle II: Floyd's tortoise and hare, then find the cycle's first node. |
| 10 | Time: O(N) | Space: O(1) |
| 11 | """ |
| 12 | if not head or not head.next: |
| 13 | return None |
| 14 | |
| 15 | slow = fast = head # both pointers start together; fast will take exactly twice slow's steps |
| 16 | has_cycle = False |
| 17 | |
| 18 | # 1. Phase 1 - Detect Collision: |
| 19 | # fast gains exactly one step on slow per move, so inside a cycle it cannot jump over slow: they must meet. Testing fast and fast.next (not just fast) keeps fast.next.next from reading an attribute of None. |
| 20 | while fast and fast.next: |
| 21 | slow = slow.next # 1 step |
| 22 | fast = fast.next.next # 2 steps |
| 23 | if slow == fast: |
| 24 | has_cycle = True |
| 25 | break |
| 26 | |
| 27 | if not has_cycle: |
| 28 | return None # fast fell off the end: no cycle |
| 29 | |
| 30 | # 2. Phase 2 - Locate Cycle Origin: |
| 31 | # head and the meeting point are the same number of steps from the cycle's first node, up to whole laps, so walking both one step at a time lands them on it together. |
| 32 | ptr1 = head |
| 33 | ptr2 = slow |
| 34 | while ptr1 != ptr2: |
| 35 | ptr1 = ptr1.next |
| 36 | ptr2 = ptr2.next |
| 37 | |
| 38 | return ptr1 |
Inside a cycle, fast gains exactly one step on slow per move, so it can't jump over it: if there is a cycle they meet, and if fast runs off the end there is none (and slow is then at the middle).
Walking from the head and walking from the meeting point reach the cycle's first node after the same number of steps (the second walk may add whole laps), so ptr1 from head and ptr2 from the meeting point, one step at a time, both land on it.
The trap is the loop test: write while fast and fast.next, because fast.next.next crashes when fast.next is None; testing only fast crashes on every list without a cycle that has an odd number of nodes.
Gotcha 1 of 4
- The trap
Gotcha 1: Writing
while fastinstead ofwhile fast and fast.nextMistakewhile fast:Fixwhile fast and fast.next:What happens: Each step moves
fasttwo nodes withfast.next.next. Whenfastis the last node,fast.nextisNone. Thenfast.next.nextreads an attribute ofNone, and Python raises an AttributeError. This happens on every list without a cycle that has an odd number of nodes.Example: head = [1, 2, 3], pos = -1 (no cycle)Mistake: raises AttributeErrorFix: returns None
10Merge Two Sorted
two sorted sequences ➔ take the smaller head, move only its pointer ➔ drain the other sequence ➔ one passTwo-Sequence Merge Pointers
| 1 | from typing import Optional |
| 2 | |
| 3 | class ListNode: |
| 4 | def __init__(self, val: int = 0, next: Optional["ListNode"] = None): |
| 5 | self.val = val |
| 6 | self.next = next |
| 7 | |
| 8 | def merge_two_lists(list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]: |
| 9 | """Merge Two Sorted Lists: relink the smaller head of the two lists, one node at a time. |
| 10 | Time: O(M + N) | Space: O(1) extra |
| 11 | """ |
| 12 | # list1 and list2 are the two pointers: each one is the first unread node of its own list |
| 13 | dummy = ListNode(0) # Fake first node, so the first real node is attached like every other |
| 14 | tail = dummy # Last node of the merged list built so far |
| 15 | |
| 16 | # 1. Take The Smaller Head: |
| 17 | # Both lists are sorted, so the smaller head is the smallest unread node of both. Attach it, then move only the pointer of the list it came from. |
| 18 | while list1 and list2: |
| 19 | if list1.val <= list2.val: |
| 20 | tail.next = list1 |
| 21 | list1 = list1.next |
| 22 | else: |
| 23 | tail.next = list2 |
| 24 | list2 = list2.next |
| 25 | tail = tail.next |
| 26 | |
| 27 | # 2. Attach The Rest Of The Other List: |
| 28 | # The loop stops when one list is empty. The other list is already sorted and already linked, so one assignment attaches all of it. |
| 29 | tail.next = list1 if list1 else list2 |
| 30 | |
| 31 | # 3. Return The Node After The Dummy: |
| 32 | # dummy only marks the start, so the merged list begins at dummy.next. |
| 33 | return dummy.next |
Each list is sorted, so its first unread node is its smallest, and the smaller of list1 and list2 is the smallest unread node of both lists: attach that node to tail and move only the pointer of the list it came from. The other pointer stays where it is, because its node is not smaller than the node just attached and still has to be compared with the next node of the other list. Each step attaches the smallest node that is left, so the merged list grows in sorted order and every node is attached exactly once. When list1.val equals list2.val, <= takes the node from list1 first, so equal values keep the order in which the two lists were given. The trap is the end of the loop: while list1 and list2 stops as soon as one list is empty, and the other list still holds unread nodes. Attach them with tail.next = list1 if list1 else list2, or every node after the last comparison is lost. Two arrays have no links to reuse, so they need a drain loop that copies the leftover values one by one.
Gotcha 1 of 5
- The trap
Gotcha 1: Leaving out the attach of the other list after the loop
Mistake# nothing after the loopFixtail.next = list1 if list1 else list2What happens:
while list1 and list2stops as soon as one list is empty. The other list still holds nodes that were never compared. Without the linetail.next = list1 if list1 else list2,tail.nextstaysNoneand those nodes are not in the result.Example: list1 = [1, 2, 4], list2 = [1, 3, 4]Mistake: returns [1, 1, 2, 3, 4]Fix: returns [1, 1, 2, 3, 4, 4]
11Linked List Reversal
head ➔ rewire each next pointer ➔ reversed listIn-Place Linked List Reversal (Reverse Linked List II, Reverse Nodes in k-Group)
| 1 | from typing import Optional |
| 2 | |
| 3 | |
| 4 | class ListNode: |
| 5 | def __init__(self, val: int = 0, next: Optional["ListNode"] = None): |
| 6 | self.val = val |
| 7 | self.next = next |
| 8 | |
| 9 | |
| 10 | def reverse_list(head: Optional[ListNode]) -> Optional[ListNode]: |
| 11 | """Reverse Linked List: flip every next pointer in one pass. |
| 12 | Time: O(N) | Space: O(1) |
| 13 | """ |
| 14 | prev = None # Head of the reversed part: empty at the start |
| 15 | curr = head # First node not flipped yet |
| 16 | while curr: |
| 17 | nxt = curr.next # Save the rest BEFORE the flip overwrites curr.next |
| 18 | curr.next = prev # Flip: curr now points back at the reversed part |
| 19 | prev = curr # The reversed part grows by one node |
| 20 | curr = nxt # Step into the saved rest |
| 21 | return prev # The old tail is the new head |
| 22 | |
| 23 | |
| 24 | def reverse_between(head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]: |
| 25 | """Reverse Linked List II: reverse positions left..right (1-indexed) in one pass. |
| 26 | Time: O(N) | Space: O(1) |
| 27 | """ |
| 28 | dummy = ListNode(0, head) # The segment may start at the head: give it a node before it |
| 29 | before = dummy |
| 30 | for _ in range(left - 1): # Walk to the node just before position left |
| 31 | before = before.next |
| 32 | prev = None |
| 33 | curr = before.next |
| 34 | for _ in range(right - left + 1): # The same flip, exactly right - left + 1 times |
| 35 | nxt = curr.next |
| 36 | curr.next = prev |
| 37 | prev = curr |
| 38 | curr = nxt |
| 39 | tail = before.next # The segment's old first node is now its last |
| 40 | before.next = prev # Reattach the reversed segment... |
| 41 | tail.next = curr # ...and hang the untouched rest behind it |
| 42 | return dummy.next |
Reversing a singly linked list only needs every next pointer to point the other way, so walk the list once with two pointers: prev heads the part already reversed (it starts as None) and curr is the first node not flipped yet; each step points curr.next back at prev, then moves prev and curr one node forward. Each step moves exactly one node from the front of the untouched part to the front of the reversed part, so no node is lost or visited twice, and when curr falls off the end, prev is the new head. reverse_between runs the same steps right - left + 1 times from the node before position left, then reconnects both ends with before.next = prev and tail.next = curr. The trap is the order of the lines: curr.next = prev overwrites the only link to the rest of the list, so save nxt = curr.next first; flip first and every node after curr is lost.
Gotcha 1 of 4
- The trap
Gotcha 1: Writing
curr.next = prevbefore savingnxtMistakewhile curr: curr.next = prev nxt = curr.nextFixwhile curr: nxt = curr.next curr.next = prevWhat happens:
curr.nextis the only link fromcurrto the rest of the list.curr.next = prevoverwrites that link. Thennxt = curr.nextsavesprev, which isNoneon the first step. The loop ends after one node, and every node aftercurris lost.Example: head = [1, 2, 3]Mistake: returns [1]Fix: returns [3, 2, 1]
12Read-Write Pointers
reader -> writer -> (Compaction Frontier)Read/Write Pointers (In-Place Array Modification, Dutch National Flag)
| 1 | from typing import Callable, List, TypeVar |
| 2 | |
| 3 | Item = TypeVar("Item") |
| 4 | |
| 5 | |
| 6 | def read_and_write(items: List[Item], keep: Callable[[Item, int], bool]) -> int: |
| 7 | """Read-Write Pointers: move every kept item to the front of items, in order, in place. |
| 8 | keep(value, writer) returns True to keep value. writer is the number of items kept so far. |
| 9 | items[:writer] holds those items, so keep may compare value with items[writer - 1]. |
| 10 | Precondition: keep reads only value and items[:writer], never a slot at writer or later. |
| 11 | Returns writer. The slots from writer on still hold old values. Move Zeroes writes its zeros there afterwards. |
| 12 | N = len(items). T = the cost of one keep call. |
| 13 | Time: O(N * T) | Space: O(1) |
| 14 | """ |
| 15 | writer = 0 # items[:writer] holds the kept items, in order |
| 16 | # 1. Read Every Item, Write Only The Kept Ones: |
| 17 | # writer never gets ahead of reader, so items[writer] = items[reader] always lands on a slot whose old value has already been read, never one still waiting to be read. |
| 18 | for reader in range(len(items)): |
| 19 | if keep(items[reader], writer): |
| 20 | items[writer] = items[reader] |
| 21 | writer += 1 |
| 22 | |
| 23 | return writer # The number of kept items |
writer marks where the next kept element goes; everything before it is final. reader visits every element and copies it to writer only when it should be kept.
Since writer never passes reader, a write never lands on an element that still has to be read, so the array can be rewritten in place. For sorted deduplication, start both at 1, because nums[0] is always kept.
The trap is comparing with the wrong slot: check nums[reader] against nums[writer - 1], the last element kept, not nums[writer], the next free slot, which still holds an old value; on LeetCode Example 2 of Remove Duplicates from Sorted Array (LC 26), [0,0,1,1,1,2,2,3,3,4], the wrong slot keeps 7 values instead of 5.
Gotcha 1 of 4
- The trap
Gotcha 1: Comparing with
items[writer]instead ofitems[writer - 1]Mistakeif nums[reader] != nums[writer]:Fixif nums[reader] != nums[writer - 1]:What happens:
nums[writer - 1]is the last value kept.nums[writer]is the next free slot. It still holds an old value from the input. Comparing with that old value can keep a duplicate. It can also drop a value that is new.Example: Remove Duplicates from Sorted Array (LC 26), Example 2: nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]Mistake: returns 7Fix: returns 5
13Prefix Sums
nums ➔ prefix with n + 1 slots, prefix[0] = 0 ➔ prefix[right + 1] - prefix[left]Prefix Sum Array
left..right. Or you need the running total at each position, counted from the start.| 1 | class NumArray: |
| 2 | """Range Sum Query - Immutable: build the prefix array once, then answer each range with one subtraction. |
| 3 | Time: O(N) to build, O(1) per sumRange | Space: O(N) |
| 4 | """ |
| 5 | |
| 6 | def __init__(self, nums: list[int]) -> None: |
| 7 | # prefix[i]: sum of the first i elements of nums; prefix[0] = 0, the sum of no elements |
| 8 | self.prefix = [0] * (len(nums) + 1) |
| 9 | # 1. Build The Prefix Array Once: |
| 10 | # Each next slot adds one more element to the previous running total, so prefix[i + 1] is always one element ahead of prefix[i]. |
| 11 | for i, num in enumerate(nums): |
| 12 | self.prefix[i + 1] = self.prefix[i] + num |
| 13 | |
| 14 | def sumRange(self, left: int, right: int) -> int: |
| 15 | # 1. Subtract The Two Running Totals: |
| 16 | # The first right + 1 elements are the first left elements followed by nums[left..right], so removing the first left elements' sum leaves exactly that range. |
| 17 | return self.prefix[right + 1] - self.prefix[left] |
Build self.prefix once, with one more slot than nums has elements. self.prefix[0] = 0, and each next slot adds one element: self.prefix[i + 1] = self.prefix[i] + num. Then sumRange answers any range with one subtraction, self.prefix[right + 1] - self.prefix[left]. This is correct because the first right + 1 elements are the first left elements followed by nums[left..right]. Subtracting the sum of the first left elements leaves exactly the range. The leading 0 is the sum of no elements, so left = 0 uses the same formula with no special case. The trap is the index shift. self.prefix[i] stops just before nums[i], so the range ends at self.prefix[right + 1]. Writing self.prefix[right] leaves nums[right] out of every answer.
Gotcha 1 of 3
- The trap
Gotcha 1: Writing
self.prefix[right]instead ofself.prefix[right + 1]Mistakereturn self.prefix[right] - self.prefix[left]Fixreturn self.prefix[right + 1] - self.prefix[left]What happens:
self.prefix[i]is the sum of the elements before indexi. Soself.prefix[right]stops just beforenums[right]. The subtraction then returnsnums[left..right - 1], one element short. On a one-element range it returns 0.Example: nums = [-2, 0, 3, -5, 2, -1], sumRange(0, 2)Mistake: returns -2Fix: returns 1
14Greedy Subsequence Match
i -> s, j -> t (claim s[i] only on a match, i reaches len(s))Subsequence Matching (Earliest-Match Two Pointers)
| 1 | def isSubsequence(s: str, t: str) -> bool: |
| 2 | """Is Subsequence: walk t once with j, and advance i in s only when the current characters match. |
| 3 | Time: O(len(t)) | Space: O(1) |
| 4 | """ |
| 5 | i = 0 # Characters of s already claimed, in order |
| 6 | for j in range(len(t)): |
| 7 | if i < len(s) and s[i] == t[j]: |
| 8 | i += 1 # The earliest available match for s[i] in t never costs a later match |
| 9 | |
| 10 | return i == len(s) |
i counts how many characters of s are already claimed, in order; walking t once with j, advance i only when t[j] equals s[i], the next character of s still unclaimed. s is a subsequence of t exactly when i reaches len(s) by the time the walk ends. Claiming the earliest copy of s[i] in t is always safe: every character of t after that point is still free for the rest of s, so no earlier choice can ever cost a later match, and a later copy would only leave less of t behind for what comes next. The trap is advancing i on every character of t instead of only on a match: i += 1 outside the if claims characters that were never actually matched, so the final check i == len(s) can pass even when s is not really a subsequence of t.
Gotcha 1 of 4
- The trap
Gotcha 1: Advancing
ion every character oft, not only on a match (the card's trap)Mistakefor j in range(len(t)): i += 1Fixfor j in range(len(t)): if i < len(s) and s[i] == t[j]: i += 1What happens:
iis supposed to count only the characters ofsthat were actually matched int, in order. Movingi += 1outside theifmakesicount every character oftinstead.ithen reacheslen(s)as soon astis at least as long ass, no matter what characters either string holds, so the final checki == len(s)saysTruefor pairs that are not a real subsequence match.Example: s = "abc", t = "ahbgdc"Mistake: returns FalseFix: returns True
15Circular Array
circular array ➔ walk indices 0..2n-1 with i % n ➔ see past the endCircular Array Handling (Virtual Doubling)
| 1 | def next_greater_elements(nums: list[int]) -> list[int]: |
| 2 | """Next Greater Element II: scan the virtually doubled array right to left. |
| 3 | Time: O(N) | Space: O(N) |
| 4 | """ |
| 5 | n = len(nums) |
| 6 | res = [-1] * n |
| 7 | stack: list[int] = [] # Candidate values, decreasing from bottom to top |
| 8 | |
| 9 | # 1. Scan The Doubled Array Right To Left: |
| 10 | # i % n reads the circular array twice without copying it, so by the time i reaches a real index, every value that wraps around to its right has already been seen. |
| 11 | for i in range(2 * n - 1, -1, -1): |
| 12 | val = nums[i % n] |
| 13 | # 2. Drop Candidates val Blocks: |
| 14 | # A stacked value that is not strictly greater than val can never be the answer for anything further left, since val stands in front of it and is at least as big. |
| 15 | while stack and stack[-1] <= val: |
| 16 | stack.pop() |
| 17 | # 3. Record Only On The Real Pass: |
| 18 | # i >= n is only priming the stack with the wrap-around values, so the answer is written exclusively when i < n, a real index. |
| 19 | if i < n: |
| 20 | res[i] = stack[-1] if stack else -1 |
| 21 | stack.append(val) |
| 22 | |
| 23 | return res |
A circular array written twice in a row contains every wrap-around, so loop i from 2 * n - 1 down to 0 and read nums[i % n] instead of copying. Scanning right to left, the steps with i >= n fill stack with the values that wrap around, so when i reaches a real index, everything after it on the circle has already been seen; that is why res[i] is written only when i < n. The trap is equal values: pop while stack[-1] <= val, or a value equal to val stays on top and is reported as its next greater element.
Gotcha 1 of 3
- The trap
Gotcha 1: Popping with
stack[-1] < valinstead of<=Mistakewhile stack and stack[-1] < val:Fixwhile stack and stack[-1] <= val:What happens: A value equal to
valis not greater thanval. With<, an equal value stays on the stack. It is then on top, and it is reported as the next greater element.Example: nums = [5, 5, 5]Mistake: returns [5, 5, 5]Fix: returns [-1, -1, -1]
Built on the mental models above
- Hash-Set Sequence ScanningStart-Element Pruning (Longest Consecutive Sequence)
Store the values in a set and walk a run only from its first value, so every value is visited once.
- Counting SortCounting Sort (H-Index, Maximum Ice Cream Bars)
The values are small whole numbers, so each value gets its own slot instead of a range of values.
- Longest Palindromic SubstringExpand Around Center (Longest Palindromic Substring)
Start both pointers at a center and move them outward while the two ends still match.
- Staircase SearchSaddleback Search (Staircase Search in a Sorted Matrix)
The pointers are a row and a column in a sorted grid, and each comparison discards a whole row or a whole column.
- Next PermutationNext Lexicographic Permutation (Narayana Pandita's Algorithm, std::next_permutation)
Find the pivot from the right, swap it with the next larger value, then reverse the suffix with two pointers.
- Three-Reversals AlgorithmIn-Place Array Rotation (Rotate Array)
Reverse the whole range, then reverse each of the two parts, so the items rotate in place.
- Monotonic DequeMonotonic Deque (Sliding Window Maximum)
The window state is a deque of candidate indices whose values only decrease, so the window maximum is always at the front.
- Dual Monotonic DequeDual Monotonic Deque (Longest Subarray Within a Max-Min Limit)
Keep a second deque for the minimum, and move the left end while the maximum minus the minimum is above the limit.
- Shortest WindowVariable-Size Sliding Window (Minimum Window)
Shrink the window while it is still valid and record its length each time, instead of shrinking only when it becomes invalid.
- At-Most TrickExactly K = At Most K − At Most (K−1)
Count the windows that end at each right end with an at-most count, then subtract two at-most counts to get an exact count.
- Fixed-Offset PointersFixed-Offset Pointers (Nth Node From End)
Start one pointer n steps ahead, then move both one step at a time, so the gap between them stays fixed.
- Cyclic SortCyclic Sort (Index as Hash, First Missing Positive)
Swap each value to the index where it belongs, so the array itself records which values are present.
- Prefix-Suffix ScanPrefix & Suffix Passes (Left-Right Scans)
The operation has no inverse, so keep one pass from the left and one pass from the right instead of subtracting prefixes.
- Prefix Sum MapPrefix Sum + Hash Map
Keep a map from each earlier prefix sum to how often it occurred, so a range with the target sum is found in one pass.
- Difference ArrayDifference Array (Range Updates)
Write a mark at each end of a range, then take one prefix sum to read the total at every position.
The Two Pointers Decision Rule (Problem Classification Checklist)
When facing an unseen array, string or linked-list problem, ask in this order:
Build prefix with n + 1 slots and prefix[0] = 0, where prefix[i + 1] = prefix[i] + nums[i]; then the sum of nums[left..right] is prefix[right + 1] - prefix[left].
Keep a map of prefix sums seen, seeded with {0: 1}; at each prefix p, add count[p - k] before recording p.
Add nums[i]; once i >= k, remove nums[i - k]; read the window after both.
Before growing right, check whether adding it would break the limit; while it would, shrink left; once it would not, grow right and record right - left + 1.
Grow right until the window is valid; while it stays valid, record its length and shrink left.
exactly(K) = atMost(K) - atMost(K - 1), where each atMost window adds right - left + 1 per right.
Keep a deque of indices with decreasing values: pop smaller values from the back, drop the front once it leaves the window; the front is the maximum.
Run two deques side by side, one decreasing (front = max) and one increasing (front = min); while the gap between the fronts exceeds the limit, shrink from the left, checking both fronts.
Start left = 0, right = n - 1 and move the pointer whose side can no longer be part of an answer.
Keep one pointer per sequence, take the smaller head and advance only that pointer; drain the leftovers.
Start at the top-right corner: a value too big moves left, a value too small moves down.
The reader scans every element; the writer marks where the next kept element goes; copy on keep.
Swap each value v into index v - 1 until it is home or a duplicate; then the first i with nums[i] != i + 1 answers.
One pass left to right fills the prefix part, one pass right to left combines the suffix part; neither includes nums[i].
diff[l] += v and diff[r + 1] -= v per update, then one running sum recovers every value.
Choose the key (the value, its complement, or a canonical form) and read or update dict[key] in O(1) per item.
Put every value in a hash set; for each value whose predecessor is absent, walk upward while the next value is present, and keep the longest walk.
Walk the second string once with j; advance i in the first string only when the current characters match; the first string is matched once i reaches its length.
Loop i over 0..2n - 1 and read nums[i % n], recording answers only for i < n.
slow moves 1 step, fast moves 2; they meet inside a cycle; restart one at head and move both 1 step to meet at the entry.
Move lead n steps ahead of trail, then move both one step at a time; when lead is the last node, trail is n steps behind it.
Set dummy.next = head, edit through prev starting at dummy, and return dummy.next.
Save nxt = curr.next, point curr.next = prev, then move prev and curr forward.
Expand around each of the 2n - 1 centers (every letter and every gap) while the two ends match.
k %= n; reverse the whole array, then the first k elements, then the rest.
Start at i = n - 2 and move i left while nums[i] >= nums[i + 1]. If i >= 0, swap nums[i] with the rightmost value in nums[i + 1:] that is larger than nums[i]. Then reverse nums[i + 1:]; when there is no such i (i = -1), this reverses the whole array.
Make one slot for each value. Add each value with count[v] += 1. Then walk the slots in order of value.
Put each value into a bucket indexed by its value or count, then read the buckets in order.
Keep k - 1 candidates with counts: a match adds 1, a free slot takes the value, otherwise every count drops by 1; verify in a second pass.
Build the failure table lps; on a mismatch fall back to lps[j - 1] instead of restarting.
Pattern Architecture & Invariant Design Masterclass
The brute-force way to examine every pair or every contiguous stretch of a list is two nested loops: O(n²). Two Pointers is the observation that in many problems you never need to move an index backwards. If you can prove that, then both indices together take at most 2n steps across the entire run, and the whole problem collapses to O(n).
There are two shapes, and confusing them is where most students lose time:
- Converging pointers. One index starts at the far left, one at the far right, and they walk toward each other. Each comparison lets you eliminate one end permanently. Used when the data is sorted or symmetric.
- Sliding window. Both indices start at the left.
rightalways moves forward, adding elements into a running "window state" (a sum, a character count, a max).leftmoves forward only to fix a window that has become invalid or to try shrinking a valid one. The window is always a contiguous stretch.
1.3 — Invariant-First Pointer Boundaries: Deriving < vs <= from Candidate State
A frequent source of off-by-one errors in two-pointer algorithms is guessing whether to write while left < right or while left <= right. The choice is not a matter of memorization—it is dictated by the state semantics of left == right: does the singleton state represent a valid candidate state that must be evaluated, or an invalid/redundant state?
1. When < is Appropriate (Distinct Pair Heuristic)
- Problem Archetypes: Two Sum II (LC 167), Valid Palindrome (LC 125), Container With Most Water (LC 11).
- The Candidate Set: The problem specifically seeks an answer formed by a pair of distinct indices with .
- Why
<Holds: Whenleft == right, the two pointers converge on the exact same element. A single element cannot form a two-sum pair with itself (the problem forbids reusing the same element), cannot hold water between two boundary walls, and a single character in a palindrome is symmetrically identical to itself. Because the candidate pair set is completely exhausted whenleft == right, terminating immediately withwhile left < right:is mathematically sound and avoids wasted computation.
2. When <= is Required (Critical Counterexamples Where < Fails)
- Counterexample 1: Three-Way In-Place Partitioning (Dutch National Flag / LC 75 Sort Colors)
In 3-way partitioning, we maintain pointers
low,mid, andhigh. The subarraynums[mid..high]represents the unexamined candidate elements. The loop must runwhile mid <= high:. If you mistakenly usedmid < high, the loop would stop one iteration too early, leaving the final element atmid == highcompletely uninspected and unpartitioned! - Counterexample 2: Odd-Length Palindromic Center Expansion (LC 5, LC 647)
When expanding outward from prospective centers, odd-length palindromes initialize
left = i, right = i(the singleton stateleft == right). The loop expands whileleft >= 0 and right < len(s) and s[left] == s[right]. Here, evaluatingleft == rightis not a waste—it is the foundational base case. - Counterexample 3: Residual Singleton Evaluation & Hoare Partitioning In quickselect or Hoare-style array partitioning, pointers sweep inward until they cross. The singleton meeting state often holds a pivot element or residual value that must be categorized into one of the two partitions before halting.
3. Framing the Heuristic in Interviews
- The "Pair vs. Target" Rule of Thumb: It is fine to use the "Pair vs. Target" trick as a quick mental intuition check (distinct pairs stop at
<, closed-interval single targets stop at<=). However, it is a memorable heuristic, not a universal law for pointer or binary-search loops. Correct boundary conditions depend on the precise invariant, whether endpoints are inclusive or exclusive, whether a problem needs the first/last valid position, and the update rules forleft,right, andmid. - The Senior Interview Standard: State the candidate state invariant out loud: "The unexamined candidates are in the range
[mid..high]. Because the candidate atmid == highhas not yet been inspected, my loop condition must bewhile mid <= high:."
3.1 — Understanding Invariants & The 5 Invariant Shapes
Before tackling specific problems, the single most critical idea to master is the loop invariant:
An invariant is a statement about your program's state that is True before the loop starts, is temporarily broken during internal state updates, and is strictly restored before the next iteration begins.
The Box Transfer Analogy
Imagine transferring items from Box A to Box B one by one:
- Held (Pre-condition): .
- Broken (In-flight): You pick up an item in your hand. Visible .
- Restored (Post-condition): You place the item into Box B. is true again.
total = len(A) + len(B)while A: item = A.pop() # Invariant temporarily broken (item in hand) B.append(item) # Invariant restored assert len(A) + len(B) == total The 5 Canonical Invariant Shapes in Two Pointers
The Kept-Prefix Boundary Partition (Reader-Writer Shape):
nums[0..writer-1]: The Kept Frontier ("Kept-Prefix Boundary") — Contains only verified, deduplicated elements in finalized order.nums[writer..reader-1]: Discardable Debris — Elements already scanned that were duplicates or filtered out.nums[reader..n-1]: Untrusted Raw Stream — Unprocessed elements waiting to be scanned.- Key Invariant Rule: Every candidate decision
nums[reader]is evaluated against the trusted boundary of truth (nums[writer - 1]ornums[writer - k]), never against the raw stream.
The Prefix Sum Rescue (when values can be negative):
- The Prefix Sum Algebraic Rescue: By shifting from contiguous physical pointers to prefix accumulators , any contiguous subarray sum equals . We convert the window search into the algebraic identity . Storing prefix occurrences in a hash map solves the problem in single-pass time and space, completely immune to negative values.
The "Negative Numbers" Gotcha Matrix: When Two Pointers Works vs. When It Fails
| Pointer Archetype | Allows Negative Numbers? | Why? Underlying Invariant Mechanism | Canonical Archetypes |
|---|---|---|---|
| Converging Squeeze (Opposite Direction) | YES | Monotonicity comes from sorted positional order (A[i] <= A[j]), not element signs. Advancing left increases the pair sum; advancing right decreases the pair sum. | Two Sum II (LC 167), 3Sum (LC 15), 4Sum (LC 18), Container With Most Water (LC 11) |
| Symmetrical Extremes (Squares) | YES | Largest absolute values reside at outer boundaries. Squaring negative extremes yields the largest positive values at the far-left boundary. | Squares of a Sorted Array (LC 977) |
| Partitioning & Compaction (Reader-Writer) | YES | Invariant evaluates an element-wise predicate (nums[i] < 0 or nums[i] == pivot), completely independent of cumulative arithmetic. | Move Zeroes (LC 283), Sort Colors / Dutch Flag (LC 75), Rearrange Array Elements by Sign (LC 2149) |
| Sliding Window (Sum / Product) | NO (Fatal Trap!) | Adding negative numbers causes window sum to decrease; shrinking can cause sum to increase. Window monotonicity broken. | Fails on LC 209 with negatives; MUST pivot to LC 560 (Prefix Sum) or LC 862 (Monotonic Deque) |
| Sliding Window (Frequency / Strings) | YES | Window state tracks character frequencies/sets, which are purely combinatorial and unaffected by numerical arithmetic. | Longest Substring (LC 3), Minimum Window Substring (LC 76), Character Replacement (LC 424) |
| Fast & Slow (Cycle / Midpoint) | YES | Traversal depends on node pointers / relative step speeds (1x vs 2x), completely independent of node payload values. | Linked List Cycle (LC 141), Middle of Linked List (LC 876) |
3.2 — The Two Pointers Decision Rule (Problem Classification Checklist)
When facing an unseen problem in an interview, use this systematic checklist to classify the exact sub-family before writing code:
The diagram asks six questions in order, and the first "yes" names the family. Question 1 comes first because its problems are the easiest to spot: the array never changes, and each question names its range. Subarray Sum Equals K (LC 560) answers "no" there, because its ranges are not given. It answers "yes" at question 2. The later questions separate the pointer families by what they keep: a window, two ends of sorted data, a write position, or a fast and a slow pointer. When every answer is "no", the problem is not a two-pointers shape.
3.1 — Understanding Invariants: Monotonic Convergence & Window Validity
Why the invariant holds: pointers only ever move forward, so a position that has already been passed can never be revisited under a different pairing. Each pointer move is a proof step, not a guess — converging pointers eliminate a boundary because the discarded element is strictly dominated by the recorded answer, and a sliding window's left only advances when the window it would leave behind is provably no better than one still ahead.
Two Pointers collapses O(N²) pair comparisons into O(N) by exploiting monotonicity: converging pointers eliminate one boundary per step because outer pairs are strictly dominated, sliding windows advance right to accumulate state and contract left to restore constraints, and prefix sums transform non-monotonic windows into algebraic O(1) difference lookups.
In a sorted array, if nums[left] + nums[right] < target, no element paired with nums[left] can reach target, eliminating left permanently.
Shrinking left restores the feasible window invariant in O(1) amortized steps; skipping duplicate values prevents generating identical combinations.
Common Questions
"Why does the sliding window pattern stop working the moment the array can contain negative numbers?"
Because the whole technique is built on one assumption — that expanding the window can only make things "more," and shrinking it can only make things "less" — and negative numbers break that assumption in both directions at once.
With all non-negative elements, adding
nums[right]into the window sum can only increase it (or leave it unchanged at zero), and removingnums[left]can only decrease it. That monotonic relationship is exactly what lets you shrinkleftwith confidence: if the window is currently valid, you know shrinking it further will only make it less valid, never suddenly valid again after briefly getting worse — so you never have to backtrack and re-check positions you've already moved past.Once negative numbers are allowed, expanding
rightcan decrease the running sum (if the new element is negative), and shrinkingleftcan increase it (if the element you're removing was negative). The sum stops moving in one predictable direction, so "the window is currently too big, shrinkleft" is no longer a sound conclusion — the answer you're looking for could be sitting on either side of your current window, in a way two pointers has no way to discover without checking every possibility again. That's why Subarray Sum Equals K (LC 560, which allows negatives) abandons the shrinking window entirely and switches to a prefix-sum hash map instead — trading the two-pointer's "never look back" guarantee for one that doesn't depend on monotonicity at all.
Complexity analysis
Time: O(n).
The right index takes exactly n steps. The left index also takes at most n steps in total across the whole run — it only ever increases and can never exceed right. Total pointer movement is bounded by 2n, so the cost is linear even though the code contains a loop inside a loop. This is the amortised argument the interviewer wants to hear: "the inner while is not O(n) per outer step — it is O(n) for the entire algorithm."
Space: O(1) for scalar-state windows (4.1, 4.2, 4.4). O(k) for set/map-state windows (4.3), where k is the number of distinct values that can be in the window at once — O(min(n, alphabet)) for strings.
The alternative worth naming: with negative numbers allowed, sliding window is invalid, and the correct approach is prefix sums plus a monotonic deque or a hash map — O(n) time but O(n) space. Knowing when the pattern does not apply is a Staff-level signal.
In streaming telemetry and rate limiters, monitoring rolling time windows — for example, finding the shortest consecutive burst of seconds that accounts for a traffic spike — uses two pointers moving in the same direction to maintain window state in one linear pass, instead of re-checking every candidate window from scratch.
💡 Don't worry if pointer movement rules feel subtle right now! Two Pointers is a universal state-elimination technique that turns pair searches into single-pass scans. As you progress through the Archetype Variants (from Container With Most Water and 3Sum to Dynamic Sliding Window and Trapping Rain Water), each hands-on challenge will cement this intuition until advancing left += 1 or shrinking right -= 1 based on monotonicity becomes second nature.
Applying two-pointer convergence to unsorted data: Two-pointer convergence strictly requires monotonicity ( increases when advancing , decreases when decrementing ). If the array is unsorted, pointer convergence skips potential pairs unpredictably. Always sort first or use a hash map.
Using
<vs<=in loop condition: When finding pairs of distinct elements (index1 < index2), the loop condition must bewhile left < right:. Usingleft <= rightallows an element to pair with itself when2 * nums[left] == target.32-bit signed integer overflow on sum: In typed languages (Java, C++, C#), adding two large integers (
nums[left] + nums[right]) can overflow . Cast to 64-bit int (long long) before comparing.
Staff+ Systems Architecture & Hardware Considerations
Triggers: "sorted array pair search", "subarray / substring satisfying condition", "sliding window max/min", "in-place partitioned reordering". Transforms brute-force nested iterations into optimal linear scans by tracking coordinated index cursors across contiguous memory.
Array lengths . A quadratic double loop times out when . Two pointers ensure each element is visited at most a constant number of times (typically 2), guaranteeing strict runtime with auxiliary space.
Index out-of-bounds on empty inputs; off-by-one window length calculations ( vs ); failing to update auxiliary window state (hash maps or frequency counts) symmetrically upon both expansion and contraction.
Conceptual Foundation & Intuitive Analogy
🧭 Conceptual Foundation & Pattern Intuition
When an array is sorted, elements possess a strict monotonic spatial order: moving to the right guarantees larger numbers, while moving to the left guarantees smaller numbers. In an unsorted array, locating a pair that sums to a target requires an hash set. But with sorted data, the space overhead can be eliminated entirely: by placing two pointers at opposite ends, the sum of the boundary elements acts as an infallible guide. If their sum is too small, the left boundary is permanently inadequate and must advance. If their sum is too large, the right boundary must retreat.
🏟️ The Analogy: The Balancing Seesaw
Imagine two people on a giant seesaw trying to balance a target weight. On the left side is a line of light weights arranged from lightest to heaviest; on the right side is a line of heavy weights arranged from heaviest to lightest. If the scale tips too low (sum is less than target), replacing the current light weight with an even lighter weight would make the deficit worse; you must step forward to a heavier light weight. If the scale tips too high, you must step back to a lighter heavy weight. You never need to restart or reconsider discarded weights.
🔑 Why It Works
The proof of correctness is absolute: at step cur_sum < target, numbers[left] + numbers[k] < target for all because numbers[k] <= numbers[right]. Therefore, numbers[left] can never participate in any valid solution. Discarding it permanently via left += 1 is mathematically airtight.
The invariant to say out loud: "Everything I have moved past can never be part of a better answer than the one I already recorded — so I never have to look at it again." If you cannot say that sentence about your problem, two pointers is unsound and you need prefix sums, a hash map, or a heap instead.
Opposite boundaries step inward. Outer pairs are strictly dominated by sortedness or geometric width. Works with negative numbers (Two Sum II, 3Sum, Squares of Sorted Array) because monotonicity relies on sorted positional order (A[i] ≤ A[j]), not element signs.
Same-direction traversal maintaining contiguous state. FAILS on negative numbers for sum/product: evicting a negative increases sum and adding one decreases it, destroying window monotonicity!
The negative numbers rescue. When negative numbers break sliding window monotonicity, prefix sums transform contiguous range searches into algebraic point lookups: P[L] = P[R+1] - target, recovering strict O(N) via hash map.
YES for Converging / Squeeze: On sorted arrays (e.g. Two Sum II, 3Sum, Squares of Sorted Array), negative numbers work natively because monotonicity is governed by sorted index order (A[i] ≤ A[j]), not signs.
NO for Sliding Window Sums: If elements can be negative, expanding can decrease the sum and contracting can increase it. Monotonicity collapses! Pivot immediately to Prefix Sum + Hash Map (LC 560) or Monotonic Deque (LC 862).
The 15 Mental Models of Two Pointers & Sliding Window
Two Pointers problems divide by how the pointers move, what the window holds, and what a lookup remembers. Name the model before coding.
1Hash Map
items ➔ computed key ➔ dict lookup or count in O(1)Hashing & Frequency Maps (Group Anagrams, Two Sum)
| 1 | from collections import defaultdict |
| 2 | |
| 3 | |
| 4 | def group_anagrams(strs: list[str]) -> list[list[str]]: |
| 5 | """Group Anagrams: words with the same sorted letters share one key in a hash map. |
| 6 | Time: O(N * K log K) | Space: O(N * K) |
| 7 | """ |
| 8 | groups: dict[str, list[str]] = defaultdict(list) # key -> every word read so far with that key |
| 9 | # 1. File Each Word Under Its Key: |
| 10 | # Words with the same letters and the same counts produce the same sorted-letters key ("eat", "tea" -> "aet"), so every anagram lands in the same group without comparing any two words. |
| 11 | for s in strs: |
| 12 | key = "".join(sorted(s)) |
| 13 | groups[key].append(s) |
| 14 | return list(groups.values()) |
| 15 | |
| 16 | |
| 17 | def two_sum(nums: list[int], target: int) -> list[int]: |
| 18 | """Two Sum: remember each value's index, and look up the partner each new value needs. |
| 19 | Time: O(N) | Space: O(N) |
| 20 | """ |
| 21 | index_of: dict[int, int] = {} # value -> an index where it was seen |
| 22 | # 1. Look Up The Partner Before Storing: |
| 23 | # If target - num was already seen, its stored index completes the pair; storing num only after the lookup keeps num from ever pairing with itself. |
| 24 | for i, num in enumerate(nums): |
| 25 | partner = target - num |
| 26 | if partner in index_of: |
| 27 | return [index_of[partner], i] |
| 28 | index_of[num] = i |
| 29 | return [] # LeetCode guarantees exactly one answer, so this line is never reached |
A hash map finds a key's entry in one step, so pick the key the question is about and store under it what the answer needs: in group_anagrams the key is a word's sorted letters and the value is every word read so far with that key; in two_sum the key is a number and the value is its index. Items that belong together produce equal keys, so groups[key].append(s) files every anagram in one pass without comparing any two words, and partner in index_of finds an earlier number that completes the pair without a second loop. The trap is a lossy key: it must be equal only for items that truly belong together, so key on "".join(sorted(s)), which keeps repeated letters, never on frozenset(s) or set(s), which drop them and put "aab" and "abb" in one group.
Gotcha 1 of 4
- The trap
Gotcha 1: Keying on
frozenset(s)instead of the sorted lettersMistakekey = frozenset(s)Fixkey = "".join(sorted(s))What happens: A set keeps each letter once and drops the repeats.
"aab"and"abb"both give the set ofaandb. They land in one group, but they are not anagrams."".join(sorted(s))keeps every letter, repeats included.Example: strs = ["aab", "abb"]Mistake: returns [['aab', 'abb']]Fix: returns [['aab'], ['abb']]
Bucket Sort (Top K Frequent, Maximum Gap)
min to max), and you need their order, the top k, or the largest gap in linear time, without an O(n log n) sort.| 1 | def maximum_gap(nums: list[int]) -> int: |
| 2 | """Maximum Gap: pigeonhole buckets, compare neighbours across buckets only. |
| 3 | Time: O(N) | Space: O(N) |
| 4 | """ |
| 5 | # 1. Handle Too Few Values: |
| 6 | # With fewer than two values there is no neighbour at all, so no gap can be measured. |
| 7 | n = len(nums) |
| 8 | if n < 2: |
| 9 | return 0 |
| 10 | |
| 11 | # 2. Size The Buckets From The Pigeonhole Bound: |
| 12 | # The largest gap is at least the average gap (hi - lo) / (n - 1); max(1, ...) keeps every |
| 13 | # bucket at least one value wide so the later division never hits zero. |
| 14 | lo, hi = min(nums), max(nums) |
| 15 | width = max(1, (hi - lo) // (n - 1)) |
| 16 | count = (hi - lo) // width + 1 # Enough buckets to hold hi as well |
| 17 | bucket_min = [float("inf")] * count # Smallest value that fell in each bucket |
| 18 | bucket_max = [float("-inf")] * count # Largest value that fell in each bucket |
| 19 | |
| 20 | # 3. Drop Each Value Into Its Bucket, Keeping Only The Extremes: |
| 21 | # No two values are compared here; because width is at most the smallest possible gap, the |
| 22 | # answer can never sit inside one bucket, so only its smallest and largest value matter. |
| 23 | for x in nums: |
| 24 | b = (x - lo) // width |
| 25 | bucket_min[b] = min(bucket_min[b], x) |
| 26 | bucket_max[b] = max(bucket_max[b], x) |
| 27 | |
| 28 | # 4. Walk The Buckets In Order And Measure Cross-Bucket Gaps: |
| 29 | # Skipping empty buckets and carrying prev_max forward means each gap is measured from the |
| 30 | # last non-empty bucket's maximum to the next non-empty bucket's minimum. |
| 31 | best = 0 |
| 32 | prev_max = lo |
| 33 | for b in range(count): |
| 34 | if bucket_min[b] == float("inf"): |
| 35 | continue |
| 36 | best = max(best, bucket_min[b] - prev_max) |
| 37 | prev_max = bucket_max[b] |
| 38 | |
| 39 | return best |
Bucket Sort drops each value straight into the bucket that covers its range, b = (x - lo) // width, so placing a value needs no comparison with other values and the buckets come out in order. The key can be any bounded number: bucket by value range to find gaps, or by count to order items by frequency. For the largest gap between neighbours, keep only bucket_min[b] and bucket_max[b], walk the buckets once, and measure bucket_min[b] - prev_max, where prev_max is the largest value of the last non-empty bucket. That is enough because of the pigeonhole principle: n values from lo to hi leave n - 1 gaps that add up to hi - lo, so the largest gap is at least their average, and being a whole number it is at least width whenever hi > lo. Two values in the same bucket differ by at most width - 1, so the maximum gap is never inside one bucket: it always runs from one bucket's maximum to a later bucket's minimum, and the values in between never matter. The trap is the floor of 1: when hi - lo < n - 1, for example with repeated values, (hi - lo) // (n - 1) is 0 and (x - lo) // width divides by zero, so write width = max(1, (hi - lo) // (n - 1)).
Gotcha 1 of 4
- The trap
Gotcha 1: Computing
widthwithout the floor of 1Mistakewidth = (hi - lo) // (n - 1)Fixwidth = max(1, (hi - lo) // (n - 1))What happens: With repeated values,
hi - locan be smaller thann - 1. Then(hi - lo) // (n - 1)is 0. The next division,(hi - lo) // width, divides by zero.max(1, ...)keeps every bucket at least one value wide.Example: nums = [1, 1, 1, 4, 2]Mistake: raises ZeroDivisionErrorFix: returns 2
3Converging Pointers
left -> <- right (Opposite Boundary Contraction)Two Pointers (Opposite Ends)
| 1 | from typing import Callable, List, Optional, Tuple |
| 2 | |
| 3 | |
| 4 | def converge(n: int, compare: Callable[[int, int], int]) -> Optional[Tuple[int, int]]: |
| 5 | """Converging Pointers: squeeze a pair of indices (left, right) inward from both ends of a sorted sequence of length n. |
| 6 | compare(left, right) returns 0 to stop at this pair, below 0 to move left, and above 0 to move right. |
| 7 | Precondition: each step can rule out the element at left or the element at right for good, and compare says which one. |
| 8 | For a pair sum on a sorted sequence, move left when the pair is too small and move right when it is too big. |
| 9 | compare may also record an answer and return a nonzero value to keep going, as in Container With Most Water and 3Sum. |
| 10 | In Valid Palindrome, a match moves both pointers, so that loop moves left and right together. |
| 11 | T = the cost of one compare call. |
| 12 | Time: O(N * T) | Space: O(1) |
| 13 | """ |
| 14 | left, right = 0, n - 1 # left and right only ever move toward each other |
| 15 | |
| 16 | # 1. Squeeze Inward While Not Met: |
| 17 | # compare rules out the element at left or at right for good on every step, so only the ruled-out end moves and the pair found, if any, is always still between left and right. |
| 18 | while left < right: |
| 19 | order = compare(left, right) |
| 20 | if order == 0: |
| 21 | return (left, right) |
| 22 | elif order < 0: |
| 23 | left += 1 # The pair is too small: the element at left cannot pair with any remaining element |
| 24 | else: |
| 25 | right -= 1 # The pair is too big: the element at right cannot pair with any remaining element |
| 26 | |
| 27 | return None |
Start one pointer at each end of a sorted array. If the pair's sum is too small, only moving left right can raise it; if it is too big, only moving right left can lower it.
Each step rules out one element for good: when curr_sum < target, numbers[left] is already paired with the largest value left, so no remaining partner can reach target (and the mirror holds for right). This works with negative numbers too, because it relies on sorted order, not on signs.
The trap is unsorted input: there, moving a pointer no longer raises or lowers the sum, so the squeeze can walk past the answer; sort first, and keep the original indices if the problem asks for them.
Gotcha 1 of 5
- The trap
Gotcha 1: Running the squeeze on an unsorted array
MistaketwoSum(nums, target)FixtwoSum(sorted(nums), target)What happens: When
curr_sum < target, the loop movesleftone step right to raise the sum. A larger value atleftis certain only whennumsis sorted. On unsorted input, a move can lower the sum, and the loop walks past the pair. Sorting first finds the pair, but it returns positions in the sorted list. Two Sum (LC 1) wants the original indices, so sort(value, index)pairs instead.Example: nums = [1, 4, 2, 3], target = 5Mistake: returns []Fix: returns [1, 4]
4Dummy Node
list whose head may change ➔ dummy.next = head ➔ rewire through prev, return dummy.nextSentinel / Dummy Node
| 1 | from typing import Optional |
| 2 | |
| 3 | class ListNode: |
| 4 | def __init__(self, val: int = 0, next: Optional["ListNode"] = None): |
| 5 | self.val = val |
| 6 | self.next = next |
| 7 | |
| 8 | def remove_elements(head: Optional[ListNode], val: int) -> Optional[ListNode]: |
| 9 | """Remove Linked List Elements: a dummy head makes deleting the real head ordinary. |
| 10 | Time: O(N) | Space: O(1) |
| 11 | """ |
| 12 | dummy = ListNode(0, head) # Every real node now has a previous node |
| 13 | prev = dummy |
| 14 | |
| 15 | # 1. Walk And Unlink Matching Nodes: |
| 16 | # prev always stays on the last kept node, so prev.next = prev.next.next removes the head the same way it removes any other node, and staying put after a removal lets the new prev.next be checked too. |
| 17 | while prev.next: |
| 18 | if prev.next.val == val: |
| 19 | prev.next = prev.next.next |
| 20 | else: |
| 21 | prev = prev.next |
| 22 | |
| 23 | # 2. Return Through The Dummy, Not head: |
| 24 | # head itself may have been removed, so dummy.next, not head, is always the current first real node. |
| 25 | return dummy.next |
The head is the only node without a previous node, which is why deleting or inserting at the head usually needs its own if. A dummy node placed before head gives every real node a previous node, so prev.next = prev.next.next removes the head like any other node. The sentinel does not have to be a node. It can be a virtual index, value or bar that is never stored in the data. It gives the first and the last element the same rule as every other element. Missing Ranges (LC 163) starts with prev = lower - 1 and ends with curr = upper + 1, so the gap before the first number and the gap after the last number use the same check as every gap between two numbers. Largest Rectangle in Histogram (LC 84) adds a bar of height 0 at the end, so the bars still on the stack are handled by the same rule. The trap is returning head: when the first node is removed, head still points at the deleted node, so return dummy.next.
Gotcha 1 of 5
- The trap
Gotcha 1: Returning
headinstead ofdummy.nextMistakereturn headFixreturn dummy.nextWhat happens:
headstill points at the first node of the input. When that node holdsval, the loop unlinks it fromdummy, butheaddoes not change. Returningheadreturns a list that starts with a deleted node.Example: head = [6, 6, 1, 2, 6, 3], val = 6Mistake: returns [6, 6, 1, 2, 3]Fix: returns [1, 2, 3]
Boyer-Moore Voting (Majority Element)
n / k for a small k), and you must find it in one pass with O(1) extra space, so no count per value.| 1 | def majority_element(nums: list[int]) -> int: |
| 2 | """Majority Element: pair off different values; the majority is the value left standing. |
| 3 | Time: O(N) | Space: O(1) |
| 4 | """ |
| 5 | # candidate, count: the value currently "standing" and how many of its copies are not yet |
| 6 | # paired off against a different value. |
| 7 | candidate, count = None, 0 |
| 8 | |
| 9 | # 1. Decide This Value's Role, Then Update The Tally: |
| 10 | # Everything read before a count of 0 is already paired off, so x starts a new run; |
| 11 | # counting after that check means x always counts as its own first copy, and count never |
| 12 | # goes below 0. |
| 13 | for x in nums: |
| 14 | if count == 0: |
| 15 | candidate = x |
| 16 | count += 1 if x == candidate else -1 |
| 17 | |
| 18 | # 2. Report The Value Left Standing: |
| 19 | # A value that fills more than half of nums has more copies than everything else combined, |
| 20 | # so pairing off different values can never cancel it; it is the one still standing at the end. |
| 21 | return candidate |
Let every value cancel one copy of a different value: a value that fills more than half of nums has more copies than all the others together, so it can't be cancelled out, and the code only has to remember what is still standing, candidate and count. When count == 0 everything read so far is paired off, so x becomes the new candidate; then count += 1 if x == candidate else -1 either adds a copy or removes a pair of two different values, at most one of them the majority, which is why the majority is the candidate left at the end. The trap is trusting that survivor: it is the answer only when a majority is promised (in the middle of [2,2,1,1,1,2,2] the candidate is 1, and on [1, 2, 3] the survivor occurs once), so when the promise is missing, count the survivor again in a second pass.
Gotcha 1 of 4
- The trap
Gotcha 1: Returning
candidatewhen no majority is promisedMistakereturn candidateFixif nums.count(candidate) > len(nums) // 2: return candidate return NoneWhat happens: The last
candidateis the majority only when a majority exists. Majority Element (LC 169) promises one, so the blueprint can return it. Without that promise, the survivor can be any value. Count it in a second pass before returning it.Example: nums = [1, 2, 3], with no majority promisedMistake: returns 3Fix: returns None
6KMP
Knuth-Morris-Pratt (KMP) String Matching
| 1 | def str_str(haystack: str, needle: str) -> int: |
| 2 | """KMP: find needle in haystack without ever moving back in haystack. |
| 3 | Time: O(N + M) | Space: O(M) |
| 4 | """ |
| 5 | m = len(needle) |
| 6 | # lps[i]: the longest proper prefix of needle[:i + 1] that is also its suffix (its longest border). |
| 7 | lps = [0] * m |
| 8 | k = 0 # Length of the prefix of needle matched so far |
| 9 | |
| 10 | # 1. Build The Border Table From needle Against Itself: |
| 11 | # Building lps runs the same search on needle against itself, so a mismatch falls back to a |
| 12 | # shorter border the same way the main search below does. |
| 13 | for i in range(1, m): |
| 14 | while k > 0 and needle[i] != needle[k]: |
| 15 | k = lps[k - 1] |
| 16 | if needle[i] == needle[k]: |
| 17 | k += 1 |
| 18 | lps[i] = k |
| 19 | |
| 20 | # 2. Scan haystack Once, Falling Back Instead Of Restarting: |
| 21 | # On a mismatch, the k letters just matched are needle[:k], already known, so k falls back |
| 22 | # to the longest border that still fits; the match ends at i, so it starts i - m + 1 letters |
| 23 | # earlier. |
| 24 | k = 0 |
| 25 | for i, ch in enumerate(haystack): |
| 26 | while k > 0 and ch != needle[k]: |
| 27 | k = lps[k - 1] |
| 28 | if ch == needle[k]: |
| 29 | k += 1 |
| 30 | if k == m: |
| 31 | return i - m + 1 |
| 32 | return -1 |
KMP never reads a character of the text twice: when a mismatch comes after k matched letters, those letters are needle[:k], which you already know, so the search keeps their longest border, k = lps[k - 1], and tries the same letter again instead of moving the start forward by one and re-reading. It is correct because a match that is still possible must begin at a suffix of what was read that is also a prefix of needle, and lps[k - 1] is the longest such part; falling back again while k > 0 and ch != needle[k] visits every shorter one in order, and lps itself is built by running the same loop on needle against itself. The trap is resetting k = 0 on a mismatch: on haystack = "abababc", needle = "ababc" it throws away the border "ab" at i = 4, where the only match begins, and returns -1 instead of 2.
Gotcha 1 of 4
- The trap
Gotcha 1: Resetting
k = 0on a mismatchMistakewhile k > 0 and ch != needle[k]: k = 0Fixwhile k > 0 and ch != needle[k]: k = lps[k - 1]What happens: After
kmatched letters, the text just read isneedle[:k]. Its end can also be the start ofneedle. A match can then begin inside the failed attempt.k = 0throws that start away, and the search can miss the match.k = lps[k - 1]keeps it.Example: haystack = "abababc", needle = "ababc"Mistake: returns -1Fix: returns 2
7Fixed Window
i >= k -> (Absorb Incoming, Evict Outgoing)Fixed-Size Sliding Window
k is given and you measure every window: averages, counts, anagram matches.| 1 | from typing import Callable, List |
| 2 | |
| 3 | |
| 4 | def slide_fixed(n: int, k: int, add: Callable[[int], None], remove: Callable[[int], None], record: Callable[[int], None]) -> None: |
| 5 | """Fixed Window: visit every window of exactly k indices in 0..n-1, one index in and one out per step. |
| 6 | Precondition: n, the number of indices, is known before the loop starts, and k >= 1. |
| 7 | record(start) is called once per window, after the window holds indices start..start + k - 1. |
| 8 | T = the cost of one add, remove or record call. |
| 9 | Time: O(N * T) | Space: O(1) besides the window's state |
| 10 | """ |
| 11 | # 1. Handle Impossible Case: |
| 12 | # Fewer than k indices exist, so no window of length k can ever form. |
| 13 | if n < k: |
| 14 | return |
| 15 | |
| 16 | # 2. Build First Window: |
| 17 | # Add every index from 0 to k - 1 so the window holds its first k indices before any sliding starts. |
| 18 | for i in range(k): |
| 19 | add(i) |
| 20 | record(0) |
| 21 | |
| 22 | # 3. Slide One Step At A Time: |
| 23 | # Add the incoming index i, remove the outgoing index i - k, then record only after both updates land so the window always holds exactly k indices when it is read. |
| 24 | for i in range(k, n): |
| 25 | add(i) |
| 26 | remove(i - k) |
| 27 | record(i - k + 1) |
Every window has the length k = len(p), so build the first window's counts once, then slide one step at a time: add the letter entering on the right and remove the one leaving on the left. Each slide changes exactly two letters of the window, so updating window_count for s[i] and s[i - k] keeps it equal to the counts of the k characters ending at i without recounting the whole window, and window_count == p_count then says whether that window is an anagram of p. The trap is the index of the leaving letter: when s[i] enters, s[i - k] leaves; an off-by-one there shifts every window, so the windows compared are the wrong ones.
Gotcha 1 of 5
- The trap
Gotcha 1: Removing
s[i - k + 1]instead ofs[i - k]Mistakewindow_count[ord(s[i - k + 1]) - ord('a')] -= 1Fixwindow_count[ord(s[i - k]) - ord('a')] -= 1What happens: Before the step, the window is
s[i - k..i - 1]. Whens[i]enters, the letter that leaves iss[i - k]. Removings[i - k + 1]takes out a letter that is still in the window. The counts then match no real window. The result lists wrong start indices.Example: s = "cbaebabacd", p = "abc"Mistake: returns [0, 3, 4, 5]Fix: returns [0, 6]
8Longest Window
left -> right -> (Check Before Growing, Contract To Repair)Variable-Size Sliding Window (Longest Window)
| 1 | from typing import Callable |
| 2 | |
| 3 | |
| 4 | def longest_window(n: int, add: Callable[[int], None], remove: Callable[[int], None], would_be_valid: Callable[[int], bool]) -> int: |
| 5 | """Longest Window: the length of the longest valid window [left, right] of indices 0..n-1. |
| 6 | Precondition: every shorter window inside a valid window is valid too, and the empty window is valid. |
| 7 | add(i) and remove(i) update the window's state for index i. |
| 8 | would_be_valid(i) reads whether adding index i to the current window would keep it valid, without changing the window's state. |
| 9 | T = the cost of one add, remove or would_be_valid call. |
| 10 | Time: O(N * T) | Space: O(1) besides the window's state |
| 11 | """ |
| 12 | left = 0 |
| 13 | max_len = 0 |
| 14 | |
| 15 | for right in range(n): |
| 16 | # 1. Repair By Evicting From left: |
| 17 | # would_be_valid(right) asks whether adding index right would still be a valid window, without changing the window's state. Every window [j, right] with j < left contains everything [left, right] contains, so if adding right to [left, right] would still be invalid, no later left can keep right out of it; evicting left is the only way back to a window that right can be added to. |
| 18 | while not would_be_valid(right): |
| 19 | remove(left) |
| 20 | left += 1 |
| 21 | # 2. Absorb Index right: |
| 22 | # Once would_be_valid(right) confirms the window stays valid, right is actually added. |
| 23 | add(right) |
| 24 | # 3. Record Only After The Add: |
| 25 | # The window [left, right] is now valid and fully updated, so its length can be measured. |
| 26 | max_len = max(max_len, right - left + 1) |
| 27 | |
| 28 | return max_len |
Before you add right to the window, check whether adding it would break the rule. If it would, move left forward until adding right is safe, then add right and record the window's length.
The window is always valid at the moment you add right, because right is only added once the check says adding it keeps the window valid, so the largest measurement is the answer. Moving left never loses a longer answer: any window that starts before left already contains everything [left, right] contains, so adding right to it would break the rule too.
The trap is answering the check by mutating the window's state to test it: the check must read what adding right would do without changing the window, or the add call right after it double-counts right.
Gotcha 1 of 4
- The trap
Gotcha 1: Measuring the window before the
whileloop repairs itMistakefor right in range(len(s)): max_len = max(max_len, right - left + 1) while s[right] in seen_chars:Fixfor right in range(len(s)): while s[right] in seen_chars:What happens: Before the
whileloop,s[right]may already be in the window. Then the windows[left..right]holds a letter twice. A length measured there counts an invalid window, somax_lencan become too large. Thewhileloop movesleftuntil the repeat is gone. After that loop,right - left + 1is the length of a valid window.Example: s = "abcabcbb"Mistake: returns 4Fix: returns 3
9Fast & Slow Pointers
slow (1x) vs fast (2x) (Velocity Differential)Fast & Slow Pointers (Floyd's Tortoise and Hare)
next = nums[i]) may contain a loop, or you need its middle in one pass with O(1) extra space.| 1 | from typing import Optional |
| 2 | |
| 3 | class ListNode: |
| 4 | def __init__(self, val: int = 0, next: Optional["ListNode"] = None): |
| 5 | self.val = val |
| 6 | self.next = next |
| 7 | |
| 8 | def find_cycle_entrance(head: Optional[ListNode]) -> Optional[ListNode]: |
| 9 | """Linked List Cycle II: Floyd's tortoise and hare, then find the cycle's first node. |
| 10 | Time: O(N) | Space: O(1) |
| 11 | """ |
| 12 | if not head or not head.next: |
| 13 | return None |
| 14 | |
| 15 | slow = fast = head # both pointers start together; fast will take exactly twice slow's steps |
| 16 | has_cycle = False |
| 17 | |
| 18 | # 1. Phase 1 - Detect Collision: |
| 19 | # fast gains exactly one step on slow per move, so inside a cycle it cannot jump over slow: they must meet. Testing fast and fast.next (not just fast) keeps fast.next.next from reading an attribute of None. |
| 20 | while fast and fast.next: |
| 21 | slow = slow.next # 1 step |
| 22 | fast = fast.next.next # 2 steps |
| 23 | if slow == fast: |
| 24 | has_cycle = True |
| 25 | break |
| 26 | |
| 27 | if not has_cycle: |
| 28 | return None # fast fell off the end: no cycle |
| 29 | |
| 30 | # 2. Phase 2 - Locate Cycle Origin: |
| 31 | # head and the meeting point are the same number of steps from the cycle's first node, up to whole laps, so walking both one step at a time lands them on it together. |
| 32 | ptr1 = head |
| 33 | ptr2 = slow |
| 34 | while ptr1 != ptr2: |
| 35 | ptr1 = ptr1.next |
| 36 | ptr2 = ptr2.next |
| 37 | |
| 38 | return ptr1 |
Inside a cycle, fast gains exactly one step on slow per move, so it can't jump over it: if there is a cycle they meet, and if fast runs off the end there is none (and slow is then at the middle).
Walking from the head and walking from the meeting point reach the cycle's first node after the same number of steps (the second walk may add whole laps), so ptr1 from head and ptr2 from the meeting point, one step at a time, both land on it.
The trap is the loop test: write while fast and fast.next, because fast.next.next crashes when fast.next is None; testing only fast crashes on every list without a cycle that has an odd number of nodes.
Gotcha 1 of 4
- The trap
Gotcha 1: Writing
while fastinstead ofwhile fast and fast.nextMistakewhile fast:Fixwhile fast and fast.next:What happens: Each step moves
fasttwo nodes withfast.next.next. Whenfastis the last node,fast.nextisNone. Thenfast.next.nextreads an attribute ofNone, and Python raises an AttributeError. This happens on every list without a cycle that has an odd number of nodes.Example: head = [1, 2, 3], pos = -1 (no cycle)Mistake: raises AttributeErrorFix: returns None
10Merge Two Sorted
two sorted sequences ➔ take the smaller head, move only its pointer ➔ drain the other sequence ➔ one passTwo-Sequence Merge Pointers
| 1 | from typing import Optional |
| 2 | |
| 3 | class ListNode: |
| 4 | def __init__(self, val: int = 0, next: Optional["ListNode"] = None): |
| 5 | self.val = val |
| 6 | self.next = next |
| 7 | |
| 8 | def merge_two_lists(list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]: |
| 9 | """Merge Two Sorted Lists: relink the smaller head of the two lists, one node at a time. |
| 10 | Time: O(M + N) | Space: O(1) extra |
| 11 | """ |
| 12 | # list1 and list2 are the two pointers: each one is the first unread node of its own list |
| 13 | dummy = ListNode(0) # Fake first node, so the first real node is attached like every other |
| 14 | tail = dummy # Last node of the merged list built so far |
| 15 | |
| 16 | # 1. Take The Smaller Head: |
| 17 | # Both lists are sorted, so the smaller head is the smallest unread node of both. Attach it, then move only the pointer of the list it came from. |
| 18 | while list1 and list2: |
| 19 | if list1.val <= list2.val: |
| 20 | tail.next = list1 |
| 21 | list1 = list1.next |
| 22 | else: |
| 23 | tail.next = list2 |
| 24 | list2 = list2.next |
| 25 | tail = tail.next |
| 26 | |
| 27 | # 2. Attach The Rest Of The Other List: |
| 28 | # The loop stops when one list is empty. The other list is already sorted and already linked, so one assignment attaches all of it. |
| 29 | tail.next = list1 if list1 else list2 |
| 30 | |
| 31 | # 3. Return The Node After The Dummy: |
| 32 | # dummy only marks the start, so the merged list begins at dummy.next. |
| 33 | return dummy.next |
Each list is sorted, so its first unread node is its smallest, and the smaller of list1 and list2 is the smallest unread node of both lists: attach that node to tail and move only the pointer of the list it came from. The other pointer stays where it is, because its node is not smaller than the node just attached and still has to be compared with the next node of the other list. Each step attaches the smallest node that is left, so the merged list grows in sorted order and every node is attached exactly once. When list1.val equals list2.val, <= takes the node from list1 first, so equal values keep the order in which the two lists were given. The trap is the end of the loop: while list1 and list2 stops as soon as one list is empty, and the other list still holds unread nodes. Attach them with tail.next = list1 if list1 else list2, or every node after the last comparison is lost. Two arrays have no links to reuse, so they need a drain loop that copies the leftover values one by one.
Gotcha 1 of 5
- The trap
Gotcha 1: Leaving out the attach of the other list after the loop
Mistake# nothing after the loopFixtail.next = list1 if list1 else list2What happens:
while list1 and list2stops as soon as one list is empty. The other list still holds nodes that were never compared. Without the linetail.next = list1 if list1 else list2,tail.nextstaysNoneand those nodes are not in the result.Example: list1 = [1, 2, 4], list2 = [1, 3, 4]Mistake: returns [1, 1, 2, 3, 4]Fix: returns [1, 1, 2, 3, 4, 4]
11Linked List Reversal
head ➔ rewire each next pointer ➔ reversed listIn-Place Linked List Reversal (Reverse Linked List II, Reverse Nodes in k-Group)
| 1 | from typing import Optional |
| 2 | |
| 3 | |
| 4 | class ListNode: |
| 5 | def __init__(self, val: int = 0, next: Optional["ListNode"] = None): |
| 6 | self.val = val |
| 7 | self.next = next |
| 8 | |
| 9 | |
| 10 | def reverse_list(head: Optional[ListNode]) -> Optional[ListNode]: |
| 11 | """Reverse Linked List: flip every next pointer in one pass. |
| 12 | Time: O(N) | Space: O(1) |
| 13 | """ |
| 14 | prev = None # Head of the reversed part: empty at the start |
| 15 | curr = head # First node not flipped yet |
| 16 | while curr: |
| 17 | nxt = curr.next # Save the rest BEFORE the flip overwrites curr.next |
| 18 | curr.next = prev # Flip: curr now points back at the reversed part |
| 19 | prev = curr # The reversed part grows by one node |
| 20 | curr = nxt # Step into the saved rest |
| 21 | return prev # The old tail is the new head |
| 22 | |
| 23 | |
| 24 | def reverse_between(head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]: |
| 25 | """Reverse Linked List II: reverse positions left..right (1-indexed) in one pass. |
| 26 | Time: O(N) | Space: O(1) |
| 27 | """ |
| 28 | dummy = ListNode(0, head) # The segment may start at the head: give it a node before it |
| 29 | before = dummy |
| 30 | for _ in range(left - 1): # Walk to the node just before position left |
| 31 | before = before.next |
| 32 | prev = None |
| 33 | curr = before.next |
| 34 | for _ in range(right - left + 1): # The same flip, exactly right - left + 1 times |
| 35 | nxt = curr.next |
| 36 | curr.next = prev |
| 37 | prev = curr |
| 38 | curr = nxt |
| 39 | tail = before.next # The segment's old first node is now its last |
| 40 | before.next = prev # Reattach the reversed segment... |
| 41 | tail.next = curr # ...and hang the untouched rest behind it |
| 42 | return dummy.next |
Reversing a singly linked list only needs every next pointer to point the other way, so walk the list once with two pointers: prev heads the part already reversed (it starts as None) and curr is the first node not flipped yet; each step points curr.next back at prev, then moves prev and curr one node forward. Each step moves exactly one node from the front of the untouched part to the front of the reversed part, so no node is lost or visited twice, and when curr falls off the end, prev is the new head. reverse_between runs the same steps right - left + 1 times from the node before position left, then reconnects both ends with before.next = prev and tail.next = curr. The trap is the order of the lines: curr.next = prev overwrites the only link to the rest of the list, so save nxt = curr.next first; flip first and every node after curr is lost.
Gotcha 1 of 4
- The trap
Gotcha 1: Writing
curr.next = prevbefore savingnxtMistakewhile curr: curr.next = prev nxt = curr.nextFixwhile curr: nxt = curr.next curr.next = prevWhat happens:
curr.nextis the only link fromcurrto the rest of the list.curr.next = prevoverwrites that link. Thennxt = curr.nextsavesprev, which isNoneon the first step. The loop ends after one node, and every node aftercurris lost.Example: head = [1, 2, 3]Mistake: returns [1]Fix: returns [3, 2, 1]
12Read-Write Pointers
reader -> writer -> (Compaction Frontier)Read/Write Pointers (In-Place Array Modification, Dutch National Flag)
| 1 | from typing import Callable, List, TypeVar |
| 2 | |
| 3 | Item = TypeVar("Item") |
| 4 | |
| 5 | |
| 6 | def read_and_write(items: List[Item], keep: Callable[[Item, int], bool]) -> int: |
| 7 | """Read-Write Pointers: move every kept item to the front of items, in order, in place. |
| 8 | keep(value, writer) returns True to keep value. writer is the number of items kept so far. |
| 9 | items[:writer] holds those items, so keep may compare value with items[writer - 1]. |
| 10 | Precondition: keep reads only value and items[:writer], never a slot at writer or later. |
| 11 | Returns writer. The slots from writer on still hold old values. Move Zeroes writes its zeros there afterwards. |
| 12 | N = len(items). T = the cost of one keep call. |
| 13 | Time: O(N * T) | Space: O(1) |
| 14 | """ |
| 15 | writer = 0 # items[:writer] holds the kept items, in order |
| 16 | # 1. Read Every Item, Write Only The Kept Ones: |
| 17 | # writer never gets ahead of reader, so items[writer] = items[reader] always lands on a slot whose old value has already been read, never one still waiting to be read. |
| 18 | for reader in range(len(items)): |
| 19 | if keep(items[reader], writer): |
| 20 | items[writer] = items[reader] |
| 21 | writer += 1 |
| 22 | |
| 23 | return writer # The number of kept items |
writer marks where the next kept element goes; everything before it is final. reader visits every element and copies it to writer only when it should be kept.
Since writer never passes reader, a write never lands on an element that still has to be read, so the array can be rewritten in place. For sorted deduplication, start both at 1, because nums[0] is always kept.
The trap is comparing with the wrong slot: check nums[reader] against nums[writer - 1], the last element kept, not nums[writer], the next free slot, which still holds an old value; on LeetCode Example 2 of Remove Duplicates from Sorted Array (LC 26), [0,0,1,1,1,2,2,3,3,4], the wrong slot keeps 7 values instead of 5.
Gotcha 1 of 4
- The trap
Gotcha 1: Comparing with
items[writer]instead ofitems[writer - 1]Mistakeif nums[reader] != nums[writer]:Fixif nums[reader] != nums[writer - 1]:What happens:
nums[writer - 1]is the last value kept.nums[writer]is the next free slot. It still holds an old value from the input. Comparing with that old value can keep a duplicate. It can also drop a value that is new.Example: Remove Duplicates from Sorted Array (LC 26), Example 2: nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]Mistake: returns 7Fix: returns 5
13Prefix Sums
nums ➔ prefix with n + 1 slots, prefix[0] = 0 ➔ prefix[right + 1] - prefix[left]Prefix Sum Array
left..right. Or you need the running total at each position, counted from the start.| 1 | class NumArray: |
| 2 | """Range Sum Query - Immutable: build the prefix array once, then answer each range with one subtraction. |
| 3 | Time: O(N) to build, O(1) per sumRange | Space: O(N) |
| 4 | """ |
| 5 | |
| 6 | def __init__(self, nums: list[int]) -> None: |
| 7 | # prefix[i]: sum of the first i elements of nums; prefix[0] = 0, the sum of no elements |
| 8 | self.prefix = [0] * (len(nums) + 1) |
| 9 | # 1. Build The Prefix Array Once: |
| 10 | # Each next slot adds one more element to the previous running total, so prefix[i + 1] is always one element ahead of prefix[i]. |
| 11 | for i, num in enumerate(nums): |
| 12 | self.prefix[i + 1] = self.prefix[i] + num |
| 13 | |
| 14 | def sumRange(self, left: int, right: int) -> int: |
| 15 | # 1. Subtract The Two Running Totals: |
| 16 | # The first right + 1 elements are the first left elements followed by nums[left..right], so removing the first left elements' sum leaves exactly that range. |
| 17 | return self.prefix[right + 1] - self.prefix[left] |
Build self.prefix once, with one more slot than nums has elements. self.prefix[0] = 0, and each next slot adds one element: self.prefix[i + 1] = self.prefix[i] + num. Then sumRange answers any range with one subtraction, self.prefix[right + 1] - self.prefix[left]. This is correct because the first right + 1 elements are the first left elements followed by nums[left..right]. Subtracting the sum of the first left elements leaves exactly the range. The leading 0 is the sum of no elements, so left = 0 uses the same formula with no special case. The trap is the index shift. self.prefix[i] stops just before nums[i], so the range ends at self.prefix[right + 1]. Writing self.prefix[right] leaves nums[right] out of every answer.
Gotcha 1 of 3
- The trap
Gotcha 1: Writing
self.prefix[right]instead ofself.prefix[right + 1]Mistakereturn self.prefix[right] - self.prefix[left]Fixreturn self.prefix[right + 1] - self.prefix[left]What happens:
self.prefix[i]is the sum of the elements before indexi. Soself.prefix[right]stops just beforenums[right]. The subtraction then returnsnums[left..right - 1], one element short. On a one-element range it returns 0.Example: nums = [-2, 0, 3, -5, 2, -1], sumRange(0, 2)Mistake: returns -2Fix: returns 1
14Greedy Subsequence Match
i -> s, j -> t (claim s[i] only on a match, i reaches len(s))Subsequence Matching (Earliest-Match Two Pointers)
| 1 | def isSubsequence(s: str, t: str) -> bool: |
| 2 | """Is Subsequence: walk t once with j, and advance i in s only when the current characters match. |
| 3 | Time: O(len(t)) | Space: O(1) |
| 4 | """ |
| 5 | i = 0 # Characters of s already claimed, in order |
| 6 | for j in range(len(t)): |
| 7 | if i < len(s) and s[i] == t[j]: |
| 8 | i += 1 # The earliest available match for s[i] in t never costs a later match |
| 9 | |
| 10 | return i == len(s) |
i counts how many characters of s are already claimed, in order; walking t once with j, advance i only when t[j] equals s[i], the next character of s still unclaimed. s is a subsequence of t exactly when i reaches len(s) by the time the walk ends. Claiming the earliest copy of s[i] in t is always safe: every character of t after that point is still free for the rest of s, so no earlier choice can ever cost a later match, and a later copy would only leave less of t behind for what comes next. The trap is advancing i on every character of t instead of only on a match: i += 1 outside the if claims characters that were never actually matched, so the final check i == len(s) can pass even when s is not really a subsequence of t.
Gotcha 1 of 4
- The trap
Gotcha 1: Advancing
ion every character oft, not only on a match (the card's trap)Mistakefor j in range(len(t)): i += 1Fixfor j in range(len(t)): if i < len(s) and s[i] == t[j]: i += 1What happens:
iis supposed to count only the characters ofsthat were actually matched int, in order. Movingi += 1outside theifmakesicount every character oftinstead.ithen reacheslen(s)as soon astis at least as long ass, no matter what characters either string holds, so the final checki == len(s)saysTruefor pairs that are not a real subsequence match.Example: s = "abc", t = "ahbgdc"Mistake: returns FalseFix: returns True
15Circular Array
circular array ➔ walk indices 0..2n-1 with i % n ➔ see past the endCircular Array Handling (Virtual Doubling)
| 1 | def next_greater_elements(nums: list[int]) -> list[int]: |
| 2 | """Next Greater Element II: scan the virtually doubled array right to left. |
| 3 | Time: O(N) | Space: O(N) |
| 4 | """ |
| 5 | n = len(nums) |
| 6 | res = [-1] * n |
| 7 | stack: list[int] = [] # Candidate values, decreasing from bottom to top |
| 8 | |
| 9 | # 1. Scan The Doubled Array Right To Left: |
| 10 | # i % n reads the circular array twice without copying it, so by the time i reaches a real index, every value that wraps around to its right has already been seen. |
| 11 | for i in range(2 * n - 1, -1, -1): |
| 12 | val = nums[i % n] |
| 13 | # 2. Drop Candidates val Blocks: |
| 14 | # A stacked value that is not strictly greater than val can never be the answer for anything further left, since val stands in front of it and is at least as big. |
| 15 | while stack and stack[-1] <= val: |
| 16 | stack.pop() |
| 17 | # 3. Record Only On The Real Pass: |
| 18 | # i >= n is only priming the stack with the wrap-around values, so the answer is written exclusively when i < n, a real index. |
| 19 | if i < n: |
| 20 | res[i] = stack[-1] if stack else -1 |
| 21 | stack.append(val) |
| 22 | |
| 23 | return res |
A circular array written twice in a row contains every wrap-around, so loop i from 2 * n - 1 down to 0 and read nums[i % n] instead of copying. Scanning right to left, the steps with i >= n fill stack with the values that wrap around, so when i reaches a real index, everything after it on the circle has already been seen; that is why res[i] is written only when i < n. The trap is equal values: pop while stack[-1] <= val, or a value equal to val stays on top and is reported as its next greater element.
Gotcha 1 of 3
- The trap
Gotcha 1: Popping with
stack[-1] < valinstead of<=Mistakewhile stack and stack[-1] < val:Fixwhile stack and stack[-1] <= val:What happens: A value equal to
valis not greater thanval. With<, an equal value stays on the stack. It is then on top, and it is reported as the next greater element.Example: nums = [5, 5, 5]Mistake: returns [5, 5, 5]Fix: returns [-1, -1, -1]
Built on the mental models above
- Hash-Set Sequence ScanningStart-Element Pruning (Longest Consecutive Sequence)
Store the values in a set and walk a run only from its first value, so every value is visited once.
- Counting SortCounting Sort (H-Index, Maximum Ice Cream Bars)
The values are small whole numbers, so each value gets its own slot instead of a range of values.
- Longest Palindromic SubstringExpand Around Center (Longest Palindromic Substring)
Start both pointers at a center and move them outward while the two ends still match.
- Staircase SearchSaddleback Search (Staircase Search in a Sorted Matrix)
The pointers are a row and a column in a sorted grid, and each comparison discards a whole row or a whole column.
- Next PermutationNext Lexicographic Permutation (Narayana Pandita's Algorithm, std::next_permutation)
Find the pivot from the right, swap it with the next larger value, then reverse the suffix with two pointers.
- Three-Reversals AlgorithmIn-Place Array Rotation (Rotate Array)
Reverse the whole range, then reverse each of the two parts, so the items rotate in place.
- Monotonic DequeMonotonic Deque (Sliding Window Maximum)
The window state is a deque of candidate indices whose values only decrease, so the window maximum is always at the front.
- Dual Monotonic DequeDual Monotonic Deque (Longest Subarray Within a Max-Min Limit)
Keep a second deque for the minimum, and move the left end while the maximum minus the minimum is above the limit.
- Shortest WindowVariable-Size Sliding Window (Minimum Window)
Shrink the window while it is still valid and record its length each time, instead of shrinking only when it becomes invalid.
- At-Most TrickExactly K = At Most K − At Most (K−1)
Count the windows that end at each right end with an at-most count, then subtract two at-most counts to get an exact count.
- Fixed-Offset PointersFixed-Offset Pointers (Nth Node From End)
Start one pointer n steps ahead, then move both one step at a time, so the gap between them stays fixed.
- Cyclic SortCyclic Sort (Index as Hash, First Missing Positive)
Swap each value to the index where it belongs, so the array itself records which values are present.
- Prefix-Suffix ScanPrefix & Suffix Passes (Left-Right Scans)
The operation has no inverse, so keep one pass from the left and one pass from the right instead of subtracting prefixes.
- Prefix Sum MapPrefix Sum + Hash Map
Keep a map from each earlier prefix sum to how often it occurred, so a range with the target sum is found in one pass.
- Difference ArrayDifference Array (Range Updates)
Write a mark at each end of a range, then take one prefix sum to read the total at every position.
The Two Pointers Decision Rule (Problem Classification Checklist)
When facing an unseen array, string or linked-list problem, ask in this order:
Build prefix with n + 1 slots and prefix[0] = 0, where prefix[i + 1] = prefix[i] + nums[i]; then the sum of nums[left..right] is prefix[right + 1] - prefix[left].
Keep a map of prefix sums seen, seeded with {0: 1}; at each prefix p, add count[p - k] before recording p.
Add nums[i]; once i >= k, remove nums[i - k]; read the window after both.
Before growing right, check whether adding it would break the limit; while it would, shrink left; once it would not, grow right and record right - left + 1.
Grow right until the window is valid; while it stays valid, record its length and shrink left.
exactly(K) = atMost(K) - atMost(K - 1), where each atMost window adds right - left + 1 per right.
Keep a deque of indices with decreasing values: pop smaller values from the back, drop the front once it leaves the window; the front is the maximum.
Run two deques side by side, one decreasing (front = max) and one increasing (front = min); while the gap between the fronts exceeds the limit, shrink from the left, checking both fronts.
Start left = 0, right = n - 1 and move the pointer whose side can no longer be part of an answer.
Keep one pointer per sequence, take the smaller head and advance only that pointer; drain the leftovers.
Start at the top-right corner: a value too big moves left, a value too small moves down.
The reader scans every element; the writer marks where the next kept element goes; copy on keep.
Swap each value v into index v - 1 until it is home or a duplicate; then the first i with nums[i] != i + 1 answers.
One pass left to right fills the prefix part, one pass right to left combines the suffix part; neither includes nums[i].
diff[l] += v and diff[r + 1] -= v per update, then one running sum recovers every value.
Choose the key (the value, its complement, or a canonical form) and read or update dict[key] in O(1) per item.
Put every value in a hash set; for each value whose predecessor is absent, walk upward while the next value is present, and keep the longest walk.
Walk the second string once with j; advance i in the first string only when the current characters match; the first string is matched once i reaches its length.
Loop i over 0..2n - 1 and read nums[i % n], recording answers only for i < n.
slow moves 1 step, fast moves 2; they meet inside a cycle; restart one at head and move both 1 step to meet at the entry.
Move lead n steps ahead of trail, then move both one step at a time; when lead is the last node, trail is n steps behind it.
Set dummy.next = head, edit through prev starting at dummy, and return dummy.next.
Save nxt = curr.next, point curr.next = prev, then move prev and curr forward.
Expand around each of the 2n - 1 centers (every letter and every gap) while the two ends match.
k %= n; reverse the whole array, then the first k elements, then the rest.
Start at i = n - 2 and move i left while nums[i] >= nums[i + 1]. If i >= 0, swap nums[i] with the rightmost value in nums[i + 1:] that is larger than nums[i]. Then reverse nums[i + 1:]; when there is no such i (i = -1), this reverses the whole array.
Make one slot for each value. Add each value with count[v] += 1. Then walk the slots in order of value.
Put each value into a bucket indexed by its value or count, then read the buckets in order.
Keep k - 1 candidates with counts: a match adds 1, a free slot takes the value, otherwise every count drops by 1; verify in a second pass.
Build the failure table lps; on a mismatch fall back to lps[j - 1] instead of restarting.
Pattern Architecture & Invariant Design Masterclass
The brute-force way to examine every pair or every contiguous stretch of a list is two nested loops: O(n²). Two Pointers is the observation that in many problems you never need to move an index backwards. If you can prove that, then both indices together take at most 2n steps across the entire run, and the whole problem collapses to O(n).
There are two shapes, and confusing them is where most students lose time:
- Converging pointers. One index starts at the far left, one at the far right, and they walk toward each other. Each comparison lets you eliminate one end permanently. Used when the data is sorted or symmetric.
- Sliding window. Both indices start at the left.
rightalways moves forward, adding elements into a running "window state" (a sum, a character count, a max).leftmoves forward only to fix a window that has become invalid or to try shrinking a valid one. The window is always a contiguous stretch.
1.3 — Invariant-First Pointer Boundaries: Deriving < vs <= from Candidate State
A frequent source of off-by-one errors in two-pointer algorithms is guessing whether to write while left < right or while left <= right. The choice is not a matter of memorization—it is dictated by the state semantics of left == right: does the singleton state represent a valid candidate state that must be evaluated, or an invalid/redundant state?
1. When < is Appropriate (Distinct Pair Heuristic)
- Problem Archetypes: Two Sum II (LC 167), Valid Palindrome (LC 125), Container With Most Water (LC 11).
- The Candidate Set: The problem specifically seeks an answer formed by a pair of distinct indices with .
- Why
<Holds: Whenleft == right, the two pointers converge on the exact same element. A single element cannot form a two-sum pair with itself (the problem forbids reusing the same element), cannot hold water between two boundary walls, and a single character in a palindrome is symmetrically identical to itself. Because the candidate pair set is completely exhausted whenleft == right, terminating immediately withwhile left < right:is mathematically sound and avoids wasted computation.
2. When <= is Required (Critical Counterexamples Where < Fails)
- Counterexample 1: Three-Way In-Place Partitioning (Dutch National Flag / LC 75 Sort Colors)
In 3-way partitioning, we maintain pointers
low,mid, andhigh. The subarraynums[mid..high]represents the unexamined candidate elements. The loop must runwhile mid <= high:. If you mistakenly usedmid < high, the loop would stop one iteration too early, leaving the final element atmid == highcompletely uninspected and unpartitioned! - Counterexample 2: Odd-Length Palindromic Center Expansion (LC 5, LC 647)
When expanding outward from prospective centers, odd-length palindromes initialize
left = i, right = i(the singleton stateleft == right). The loop expands whileleft >= 0 and right < len(s) and s[left] == s[right]. Here, evaluatingleft == rightis not a waste—it is the foundational base case. - Counterexample 3: Residual Singleton Evaluation & Hoare Partitioning In quickselect or Hoare-style array partitioning, pointers sweep inward until they cross. The singleton meeting state often holds a pivot element or residual value that must be categorized into one of the two partitions before halting.
3. Framing the Heuristic in Interviews
- The "Pair vs. Target" Rule of Thumb: It is fine to use the "Pair vs. Target" trick as a quick mental intuition check (distinct pairs stop at
<, closed-interval single targets stop at<=). However, it is a memorable heuristic, not a universal law for pointer or binary-search loops. Correct boundary conditions depend on the precise invariant, whether endpoints are inclusive or exclusive, whether a problem needs the first/last valid position, and the update rules forleft,right, andmid. - The Senior Interview Standard: State the candidate state invariant out loud: "The unexamined candidates are in the range
[mid..high]. Because the candidate atmid == highhas not yet been inspected, my loop condition must bewhile mid <= high:."
3.1 — Understanding Invariants & The 5 Invariant Shapes
Before tackling specific problems, the single most critical idea to master is the loop invariant:
An invariant is a statement about your program's state that is True before the loop starts, is temporarily broken during internal state updates, and is strictly restored before the next iteration begins.
The Box Transfer Analogy
Imagine transferring items from Box A to Box B one by one:
- Held (Pre-condition): .
- Broken (In-flight): You pick up an item in your hand. Visible .
- Restored (Post-condition): You place the item into Box B. is true again.
total = len(A) + len(B)while A: item = A.pop() # Invariant temporarily broken (item in hand) B.append(item) # Invariant restored assert len(A) + len(B) == total The 5 Canonical Invariant Shapes in Two Pointers
The Kept-Prefix Boundary Partition (Reader-Writer Shape):
nums[0..writer-1]: The Kept Frontier ("Kept-Prefix Boundary") — Contains only verified, deduplicated elements in finalized order.nums[writer..reader-1]: Discardable Debris — Elements already scanned that were duplicates or filtered out.nums[reader..n-1]: Untrusted Raw Stream — Unprocessed elements waiting to be scanned.- Key Invariant Rule: Every candidate decision
nums[reader]is evaluated against the trusted boundary of truth (nums[writer - 1]ornums[writer - k]), never against the raw stream.
The Prefix Sum Rescue (when values can be negative):
- The Prefix Sum Algebraic Rescue: By shifting from contiguous physical pointers to prefix accumulators , any contiguous subarray sum equals . We convert the window search into the algebraic identity . Storing prefix occurrences in a hash map solves the problem in single-pass time and space, completely immune to negative values.
The "Negative Numbers" Gotcha Matrix: When Two Pointers Works vs. When It Fails
| Pointer Archetype | Allows Negative Numbers? | Why? Underlying Invariant Mechanism | Canonical Archetypes |
|---|---|---|---|
| Converging Squeeze (Opposite Direction) | YES | Monotonicity comes from sorted positional order (A[i] <= A[j]), not element signs. Advancing left increases the pair sum; advancing right decreases the pair sum. | Two Sum II (LC 167), 3Sum (LC 15), 4Sum (LC 18), Container With Most Water (LC 11) |
| Symmetrical Extremes (Squares) | YES | Largest absolute values reside at outer boundaries. Squaring negative extremes yields the largest positive values at the far-left boundary. | Squares of a Sorted Array (LC 977) |
| Partitioning & Compaction (Reader-Writer) | YES | Invariant evaluates an element-wise predicate (nums[i] < 0 or nums[i] == pivot), completely independent of cumulative arithmetic. | Move Zeroes (LC 283), Sort Colors / Dutch Flag (LC 75), Rearrange Array Elements by Sign (LC 2149) |
| Sliding Window (Sum / Product) | NO (Fatal Trap!) | Adding negative numbers causes window sum to decrease; shrinking can cause sum to increase. Window monotonicity broken. | Fails on LC 209 with negatives; MUST pivot to LC 560 (Prefix Sum) or LC 862 (Monotonic Deque) |
| Sliding Window (Frequency / Strings) | YES | Window state tracks character frequencies/sets, which are purely combinatorial and unaffected by numerical arithmetic. | Longest Substring (LC 3), Minimum Window Substring (LC 76), Character Replacement (LC 424) |
| Fast & Slow (Cycle / Midpoint) | YES | Traversal depends on node pointers / relative step speeds (1x vs 2x), completely independent of node payload values. | Linked List Cycle (LC 141), Middle of Linked List (LC 876) |
3.2 — The Two Pointers Decision Rule (Problem Classification Checklist)
When facing an unseen problem in an interview, use this systematic checklist to classify the exact sub-family before writing code:
The diagram asks six questions in order, and the first "yes" names the family. Question 1 comes first because its problems are the easiest to spot: the array never changes, and each question names its range. Subarray Sum Equals K (LC 560) answers "no" there, because its ranges are not given. It answers "yes" at question 2. The later questions separate the pointer families by what they keep: a window, two ends of sorted data, a write position, or a fast and a slow pointer. When every answer is "no", the problem is not a two-pointers shape.
3.1 — Understanding Invariants: Monotonic Convergence & Window Validity
Why the invariant holds: pointers only ever move forward, so a position that has already been passed can never be revisited under a different pairing. Each pointer move is a proof step, not a guess — converging pointers eliminate a boundary because the discarded element is strictly dominated by the recorded answer, and a sliding window's left only advances when the window it would leave behind is provably no better than one still ahead.
Two Pointers collapses O(N²) pair comparisons into O(N) by exploiting monotonicity: converging pointers eliminate one boundary per step because outer pairs are strictly dominated, sliding windows advance right to accumulate state and contract left to restore constraints, and prefix sums transform non-monotonic windows into algebraic O(1) difference lookups.
In a sorted array, if nums[left] + nums[right] < target, no element paired with nums[left] can reach target, eliminating left permanently.
Shrinking left restores the feasible window invariant in O(1) amortized steps; skipping duplicate values prevents generating identical combinations.
Common Questions
"Why does the sliding window pattern stop working the moment the array can contain negative numbers?"
Because the whole technique is built on one assumption — that expanding the window can only make things "more," and shrinking it can only make things "less" — and negative numbers break that assumption in both directions at once.
With all non-negative elements, adding
nums[right]into the window sum can only increase it (or leave it unchanged at zero), and removingnums[left]can only decrease it. That monotonic relationship is exactly what lets you shrinkleftwith confidence: if the window is currently valid, you know shrinking it further will only make it less valid, never suddenly valid again after briefly getting worse — so you never have to backtrack and re-check positions you've already moved past.Once negative numbers are allowed, expanding
rightcan decrease the running sum (if the new element is negative), and shrinkingleftcan increase it (if the element you're removing was negative). The sum stops moving in one predictable direction, so "the window is currently too big, shrinkleft" is no longer a sound conclusion — the answer you're looking for could be sitting on either side of your current window, in a way two pointers has no way to discover without checking every possibility again. That's why Subarray Sum Equals K (LC 560, which allows negatives) abandons the shrinking window entirely and switches to a prefix-sum hash map instead — trading the two-pointer's "never look back" guarantee for one that doesn't depend on monotonicity at all.
Complexity analysis
Time: O(n).
The right index takes exactly n steps. The left index also takes at most n steps in total across the whole run — it only ever increases and can never exceed right. Total pointer movement is bounded by 2n, so the cost is linear even though the code contains a loop inside a loop. This is the amortised argument the interviewer wants to hear: "the inner while is not O(n) per outer step — it is O(n) for the entire algorithm."
Space: O(1) for scalar-state windows (4.1, 4.2, 4.4). O(k) for set/map-state windows (4.3), where k is the number of distinct values that can be in the window at once — O(min(n, alphabet)) for strings.
The alternative worth naming: with negative numbers allowed, sliding window is invalid, and the correct approach is prefix sums plus a monotonic deque or a hash map — O(n) time but O(n) space. Knowing when the pattern does not apply is a Staff-level signal.
In streaming telemetry and rate limiters, monitoring rolling time windows — for example, finding the shortest consecutive burst of seconds that accounts for a traffic spike — uses two pointers moving in the same direction to maintain window state in one linear pass, instead of re-checking every candidate window from scratch.
💡 Don't worry if pointer movement rules feel subtle right now! Two Pointers is a universal state-elimination technique that turns pair searches into single-pass scans. As you progress through the Archetype Variants (from Container With Most Water and 3Sum to Dynamic Sliding Window and Trapping Rain Water), each hands-on challenge will cement this intuition until advancing left += 1 or shrinking right -= 1 based on monotonicity becomes second nature.
Applying two-pointer convergence to unsorted data: Two-pointer convergence strictly requires monotonicity ( increases when advancing , decreases when decrementing ). If the array is unsorted, pointer convergence skips potential pairs unpredictably. Always sort first or use a hash map.
Using
<vs<=in loop condition: When finding pairs of distinct elements (index1 < index2), the loop condition must bewhile left < right:. Usingleft <= rightallows an element to pair with itself when2 * nums[left] == target.32-bit signed integer overflow on sum: In typed languages (Java, C++, C#), adding two large integers (
nums[left] + nums[right]) can overflow . Cast to 64-bit int (long long) before comparing.
Staff+ Systems Architecture & Hardware Considerations
Triggers: "sorted array pair search", "subarray / substring satisfying condition", "sliding window max/min", "in-place partitioned reordering". Transforms brute-force nested iterations into optimal linear scans by tracking coordinated index cursors across contiguous memory.
Array lengths . A quadratic double loop times out when . Two pointers ensure each element is visited at most a constant number of times (typically 2), guaranteeing strict runtime with auxiliary space.
Index out-of-bounds on empty inputs; off-by-one window length calculations ( vs ); failing to update auxiliary window state (hash maps or frequency counts) symmetrically upon both expansion and contraction.