Pointers and Sliding Windows

The proof comes before the pointers

Eliminate impossible pairs in sorted order

For sorted nondecreasing a, compare a[left]+a[right]. If the sum is below target, every eligible partner at or below right is also too small for that left value. Move left forward. If it is above target, every eligible partner at or above left is too large for that right value. Move right backward.

def has_pair_with_sum(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        total = nums[left] + nums[right]
        if total == target: return True
        if total < target: left += 1
        else: right -= 1
    return False

The function returns existence, not indices. Return the two current indices instead of True if positions are required. left<right enforces distinct elements. On unsorted input, these bounds do not hold. Sorting can make them valid but costs work, changes order and loses original indices unless those indices travel with their values. Complement hashing → avoids this sorted-order requirement.

Read/write pointers preserve a prefix

Read visits each original value; write is the next free output position. After handling the read position, the prefix before write contains exactly the accepted values in their required order. For sorted duplicate removal, adjacent equal values belong to one run.

def remove_duplicates(nums):
    write = 0
    for read in range(len(nums)):
        if write == 0 or nums[read] != nums[write - 1]:
            nums[write] = nums[read]
            write += 1
    return write

Writing at or behind read protects unread data. The function handles empty input and returns a logical length; it does not promise that the original container shrinks. On unsorted data it removes only adjacent repetitions, not every repeated value.

Fast/slow pointers solve a different family: linked-list cycle detection or a processed boundary. Relative motion on a cycle provides the meeting argument. Do not assume that moving at two speeds solves an arbitrary array relation.

Centers, merges and a fixed outer choice

A palindrome grows around either one character (odd length) or the gap between two characters (even length). Expand while both indices are in bounds and characters match. On stopping, [left+1,right) is the valid palindrome. Trying all centers takes O(n²) time in the worst case, not one globally linear scan.

def expand(s, left, right):
    while left >= 0 and right < len(s) and s[left] == s[right]:
        left -= 1
        right += 1
    return s[left + 1:right]

To merge two ordered inputs, compare their current heads and consume the smaller eligible value. Each item is consumed once; output size matters. For a three-value sum, fix one sorted position and apply opposite-end reasoning to its suffix. Repeating a linear suffix scan gives O(n²) overall.

When producing unique value triples, record a valid triple before skipping equal runs. When producing index triples, skipping equal values may discard required outputs. State what makes two answers distinct.

The shorter-boundary move in maximum container area uses another bound: reducing width cannot help while keeping the current shorter height. Trapping water uses known boundary maxima. Neither follows solely from the sum comparison rule; a superficially similar pair of pointers can require a different invariant.

Reuse a fixed contiguous range

A fixed-size window is a contiguous range, not an arbitrary subsequence. For sums, add the new right value and remove the item falling out of the left boundary. Record only once k items exist. Validate $1\le k\le n$ or define an explicit no-window result.

def max_sum_of_size_k(nums, k):
    if type(k) is not int or not 1 <= k <= len(nums):
        raise ValueError('window size outside input')
    total, best = 0, float('-inf')
    for right, value in enumerate(nums):
        total += value
        if right >= k:
            total -= nums[right - k]
        if right >= k - 1:
            best = max(best, total)
    return best

This implementation rejects an invalid window size rather than returning a numeric sentinel for no window. After adjustment during startup, the state describes at most k items; after startup it describes exactly k. Initializing best to zero would be wrong when every complete window has negative sum. Negative values do not invalidate this fixed-size additive update.

Maximum does not support removal by subtraction. A sliding maximum needs another structure, such as a monotonic deque that removes expired indices from the front and dominated candidates from the back. Counts require decrementing the outgoing value; a full recomputation defeats the reuse.

Longest and shortest use different loops

For the longest unique substring, expand right, then repeatedly remove from left while a duplicate exists. Record only after restoring uniqueness. Before expansion the window is unique, so only the entering character can newly violate that condition.

def longest_unique_substring(s):
    counts = {}
    left = best = 0
    for right, char in enumerate(s):
        counts[char] = counts.get(char, 0) + 1
        while counts[char] > 1:
            departing = s[left]
            counts[departing] -= 1
            left += 1
        best = max(best, right - left + 1)
    return best

For a shortest covering range, expand until all requirements are met, record that valid range, then shrink while it remains valid. The last removal can break validity; do not record an invalid range afterward.

Each removal needs a reason it can never become a better start for a later right boundary. A duplicate-containing range cannot become unique by appending more characters. Once a covering range at one start has been recorded, extending that same start only makes it longer.

Track satisfied frequency requirements

For covering a target multiset, keep required counts, current counts and formed: the number of distinct required characters whose count has reached its requirement. Increase formed only when an added required count crosses from need−1 to need; decrease it when removal crosses from need to need−1. Surplus copies do not add another satisfied requirement.

For target “AAB”, {A:1,B:1} is not coverage. {A:2,B:1} is. A scalar avoids comparing whole dictionaries after every move, but its crossing logic must still preserve exact multiplicities.

A fixed-length anagram window can maintain requirement differences or a mismatch count. Delete zero-count keys if dictionary size represents distinct characters. A stale maximum frequency is safe in certain replacement-length algorithms only with that algorithm's proof; it is not an exact summary of every current window.

Exactly K through at-most counts

For at most K distinct values, shrink while too many distinct values remain. After restoring validity, all suffixes starting from left through right are valid, giving $r-l+1$ new ranges, where l and r are the restored boundaries. Sum that number across right endpoints. Define atMost(K)=0 for K<0.

def at_most_k_distinct(nums, k):
    if type(k) is not int: raise ValueError('integer K required')
    if k < 0: return 0
    counts = {}
    left = total = 0
    for right, value in enumerate(nums):
        counts[value] = counts.get(value, 0) + 1
        while len(counts) > k:
            departing = nums[left]
            counts[departing] -= 1
            if counts[departing] == 0: del counts[departing]
            left += 1
        total += right - left + 1
    return total

For [1,2,1], atMost(2)=6 and atMost(1)=3, so exactly two distinct values occur in 3 ranges. Empty input contributes zero nonempty ranges. The count can grow quadratically even though computing it takes linear pointer movement.

Where forward-only boundaries fail

“Contiguous” is a recognition signal, not enough proof. For a shortest range with sum at least S, nonnegative values make sum monotone under expansion and contraction. Arbitrary signed values destroy that argument.

Counterexample: [1,−1,5], S=5. A naive shrink-while-valid sum method reaches [1,−1,5] with sum 5 and length 3, removes 1 and sees sum 4, then stops. It misses [5], length 1, because removing the next −1 would restore validity. The usual monotone argument cannot justify discarding that possibility.

Signed exact-sum counts often use prefix sums and frequency lookup. Signed shortest-threshold ranges can use ordered prefix candidates in a monotonic deque. These are different invariants, not permission to reuse the nonnegative shrink rule.

State the window and the cost model

Choose one range convention: this reader uses inclusive [left,right] for windows and half-open [l,r) for prefix queries. Define the empty state before reading length formulas. Use while when several removals may be needed; one if does not generally restore validity.

For forward-only windows, each item enters once and leaves at most once. A nested shrinking loop therefore has O(n) total moves. It has linear total work only when state updates and checks have the assumed bounded cost. Sorting adds O(n log n); iterating all centers or outer fixed values has its own larger cost.

Test empty input, k outside its domain, equal values, no feasible range, an all-valid range, a requirement with repetitions and signed-sum counterexamples. Explain what lies outside the active interval and why no lost candidate can improve the answer.

Connected patterns

Python string and code-point semantics ↗

These traces are new exact instructional examples, not quoted implementation diagrams.

Stored keys and prefix state → · Monotonic candidate reasoning → · Cycle detection and relative motion →