Arrays & Strings — Indexing, Slicing, Two-Pointer

Review boundary and corrected contracts

Corrected the two-pointer elimination proof: nums[left] is the smallest remaining partner for nums[right]. General slicing/concatenation may copy; CPython sometimes optimizes +=, so timing is not an unconditional quadratic claim. Sliding positive sums require a positive target and nonnegative values; sorting needs memory too.

The examples below teach the stated input contracts; fragments and deliberately incorrect counterexamples are exercises, not production implementations. Complexity counts elementary operations unless a bit-cost or allocation caveat is stated. Practice times are suggestions, not measured performance or hiring guarantees.

Learning objective: Own arrays and strings so completely that you reach for the two-pointer / sliding-window template before you reach for a for-loop.

Why this session exists

Arrays and strings are common sequences, but their element models matter: a CPython list stores references, a typed array stores fixed-dtype values, and a Python str is an immutable sequence of Unicode code points, not necessarily user-perceived characters. This session isn't about the syntax (you already know a[3]) — it's about the two-pointer and sliding-window patterns that turn painful O(n²) loops into elegant O(n) solutions. Once you see these patterns, you can't un-see them.

You will be able to

• Explain in one breath why arrays give O(1) index access and O(n) middle-insert.

• Write a two-pointer solution for reverse-in-place, two-sum-on-sorted, and remove-duplicates.

• Write a sliding-window solution for longest-substring-without-repeats in one sitting.

• Explain string immutability, prefix-copy costs and why join gives a portable construction strategy rather than a fixed speedup.

• Recognise storage and boundary errors in parsers and string processing without assuming every tokenizer or path grammar is a sliding-window problem.

Prerequisites

• S005–S007 · Python data types (list, str, tuple).
• S015 · Big-O notation is useful background; the amortized pointer-count arguments below are deterministic, while hash-table operation costs are expected-case.
• No formal Big-O background required — we'll build it here.

Pre-read · skim before the session (25 min total)

Further reading: Python Docs · Data Structures

Further reading: TimeComplexity — Python Wiki

Further reading: LeetCode · Array & String Explore Card

(a) Intuition · 5 min

Arrays are shelves; strings are shelves of letters

Real: An array is a row of numbered lockers. Locker #7 is exactly 7 lockers from the start — you can walk there in one step. Adding a new locker at #7 means shifting every locker after it one to the right — a lot of moving. A two-pointer approach is two people walking down the row from opposite ends, meeting in the middle. Each pointer advances at most n positions, giving O(n) pointer moves when the work per move is bounded; an element may be examined more than once.

 
    Under the hood, a Python list is a contiguous block of pointer slots in memory. a[i] is arithmetic: base_address + i * pointer_size — an O(1) slot lookup plus bounds/type/reference work, not literally one machine read.
    Two-pointer and sliding-window turn many O(n²) brute-force loops into O(n) by exploiting the fact that when a pointer moves forward, some prior work can be reused. That single realisation is the entire pattern.
  

The three ideas that unlock this whole family

What you're really learning

• Random access — arrays give O(1) index because memory is a giant array under the hood. Everything else in DSA is a trade-off vs this.

• Two-pointer — instead of nested for-loops, walk two indices along the array. Each pointer moves at most n times → O(n) total.

• Sliding window — a special two-pointer where left and right bound a subarray whose property (sum, distinct chars, min/max) is maintained incrementally.

Python strings are IMMUTABLE — a career-long tripwire

s = "hello"; s[0] = "H" raises TypeError: a str cannot be mutated through indexing. General repeated immutable concatenation may copy accumulated prefixes, leading to quadratic total work. CPython can optimize some unaliased local += patterns, so a timing demo is not a universal quadratic proof. "".join(pieces) gives an explicit output-construction strategy with O(k+L) work for k pieces totaling L code points, plus the result allocation.

Timeline — how arrays became the default

The conceptual progression runs from Fortran's indexed numerical arrays to C's low-level address arithmetic, Python's dynamic sequence of object references, and NumPy's typed multidimensional arrays. C arrays are not literally pointers: many expressions convert an array to a pointer to its first element, but array types and sizes still differ. NumPy's own overview contrasts homogeneous array storage with Python sequences. NumPy views may be strided, so “array” does not imply C-contiguity.

Typed arrays and WebAssembly bring numerical buffers and compiled computation to browsers; they do not make every workload near-native or establish an invented 2015 SIMD launch. The storage questions survive each platform change: element width, indexing rule, bounds, ownership, strides and copying. Those are the useful historical connections, without unsupported first-invention or universal-speed claims.

(b) From memory layout to pointer movement · 15 min

Python's choice of a dynamic array gives us cheap indexed access, but that alone does not make an algorithm fast. First separate the costs imposed by the storage layout from the work imposed by the way we traverse it.

Array vs linked list — the trade-off in one diagram

Compare two operations in the diagram: reaching an existing position and making room for a new item. The array computes a position directly but shifts slots for a middle insertion; the linked list follows links to a position but can change the connections once the relevant node is known.

The linked-list insertion advantage means insertion after a known singly linked node, or suitable known neighbour links in a doubly linked list. Inserting before an arbitrary singly linked node may require finding its predecessor; finding a position can cost O(n). For the array problems here, the more useful advantage is cheap access at two indices, which lets us retain progress instead of restarting a scan.

The two-pointer pattern — three shapes

Opposite ends

Desc: left=0, right=n-1. Move whichever pointer is at the ‘wrong’ end. Use for: reverse in place, two-sum on sorted array, valid palindrome.

Same start, one lagging

Desc: slow=0, fast=0. Advance fast; when a condition is met, bump slow and swap. Use for: remove-duplicates-in-place, move zeros to end.

Sliding window

Desc: Retain state for an interval. Longest-unique repairs duplicates; minimum qualifying sum records while valid; a fixed-width sum evicts an element whenever width exceeds k. Their update/recording orders differ.

When to reach for which

Name: Two-pointer (opposite)

Tagline: Opposite ends with a proved elimination rule; pair-sum specifically needs sorted order

• Palindrome check

• Two-sum on sorted

• Trapping rain water

• Container with most water

Name: Two-pointer (same start)

Tagline: In-place mutation without extra memory

• Remove duplicates from sorted array

• Move zeros to end

• Partition around a pivot

• Any ‘compact this array’ task

Name: Sliding window

Tagline: Contiguous subarray / substring property

• Longest substring without repeating chars

• Minimum window substring

• Max sum of k consecutive

• Longest subarray with at most k distinct

Name: Not two-pointer

Tagline: Bail to a different tool

• Unsorted + no way to sort → hashmap (S024)

• For 3-sum, fixing one index and scanning two others is one option; “more than two” does not automatically require DP

• Random access alone does not imply a graph; derive the state and allowed transitions first

• Structural mutation while iterating needs an explicit invariant; value overwrites and two-index compaction can be safe

The sliding-window state machine

For a longest substring without repeats, the two indices enclose the current candidate. Adding a character may break uniqueness; moving the left boundary repairs it. Read the steps below as a loop that maintains that condition, not as five separate passes over the string.

The 5 states of a sliding window

Name: 1. Initialise

Desc: Set left=0 and an empty state. The loop will enumerate right starting at 0; the current inclusive window has not yet consumed an element.

Name: 2. Grow right

Desc: Take the next right index, starting at 0, and add arr[right] to state.

Name: 3. Check invariant

Desc: If the window is now INVALID (e.g. duplicate char, sum too big), enter shrink mode.

Name: 4. Shrink left

Desc: While invalid: remove arr[left] from state, advance left. Stop when valid again.

Name: 5. Record answer

Desc: For this longest-valid-window version, maximize right−left+1 after repair. Continue while the for loop supplies another right index; other objectives require their own counting/recording rule.

Choose the invariant before the template

For a longest valid window, expand, repair invalidity, then record a valid length. For a shortest window satisfying a lower sum bound, record while valid, then shrink to seek a shorter one. These are different recording points. Both need a monotonic reason that advancing a boundary can safely discard candidates; negative numbers break the simple nonnegative-sum version.

Keeping the boundaries moving forward controls the number of pointer moves, but the work inside each move matters too. Copying a slice or rebuilding a growing string can erase the gain; after that cost check, we will examine why sorted pair search can safely discard candidates.

Myth: "Building a string in a loop with s += part is fine — it's one operation per iteration, so it's linear. And slicing a string or list to grab a piece is cheap because I'm only taking a few characters."

Truth: Count copied elements, not operators. A list slice of k selected elements costs O(k) time and extra reference slots; n fixed-size slices can still cost O(n), while slicing prefixes of lengths 1 through n copies n(n+1)/2 slots. NumPy basic slices can be views, so do not transfer Python-list costs blindly.

For strings, repeated concatenation can copy prefixes, but CPython's local += optimization may make the archived microbenchmark look nearly linear. Measure the real aliasing and interpreter conditions; do not assert “doubling always quadruples.”

import timeit
setup = 'parts = ["x"] * 40000'
bad = 's = ""\nfor p in parts: s += p'
good = 's = "".join(parts)'
print(timeit.timeit(bad, setup, number=5))
print(timeit.timeit(good, setup, number=5))
# Timings describe this run only; compare correctness separately.

Question: Why can opposite-end sorted pair-sum search discard one endpoint? Reversal and palindrome checks do not require sorted input, and this scan does not discard half the candidates per step.

Premise: Consider finding a pair summing to a target, with pointers at the smallest element (left) and the largest (right).

Because: sortedness gives us a known ordering to exploit, which is the only extra information we have

Premise: If a[left] + a[right] > target, the sum is too large. Every remaining partner is ≥ a[left], so pairing a[right] with any of them gives a sum ≥ the current one... no smaller than what we already rejected as too large.

Because: sortedness guarantees a[right] is the largest remaining, so it is already paired with the smallest available partner

Premise: Therefore a[right] cannot participate in any valid pair within the remaining window, and can be discarded entirely — not just skipped for this comparison.

Because: its best case (pairing with the current minimum) has already failed

Premise: Symmetrically, if the sum is too small, a[left] is already paired with the largest available partner and still falls short, so it can be discarded.

Because: no remaining partner is larger than a[right]

Premise: Each comparison eliminates exactly one element permanently, so the window shrinks by one per step and the scan terminates in at most n steps — O(n) after the sort.

Because: the window can only shrink, and it starts at size n

Conclusion: Therefore the technique isn't a trick: sortedness converts one comparison into a proof about an entire set of candidates. On unsorted input this elimination proof fails; a complement hash table can still give expected O(n) time. And note what this predicts: the same argument underlies binary search (one comparison eliminates half), the merge step of mergesort, and interval-overlap sweeps — all of them are "sort first, then let ordering license bulk elimination". It also predicts the real decision point, which is a cost comparison rather than a cleverness one: the scan needs O(1) auxiliary space on already sorted data. Sorting costs O(n log n) comparisons; CPython list.sort may need O(n) temporary references and sorted makes a new list. A hash-table approach has expected O(n) time and O(n) storage, with collision and integer-cost qualifications. So on already-sorted or memory-constrained data two pointers wins, and on unsorted data where memory is free the hash set wins.

Name: Contiguous memory: cheap at the end, expensive at the front

Picture: An array is a single unbroken run of memory. That layout is what makes a[i] a one-step address computation, and it's what lets the CPU prefetch your next elements — which can favor sequential locality; actual speed depends on elements, cache behavior and implementation, not just Big-O. The same layout is what makes the front expensive. Inserting or removing at index 0 requires physically shifting every subsequent element. Appending has amortized O(1) cost under geometric growth, but a resizing append can copy O(n) reference slots. Location, resizing, element operations and allocation all matter.

• Prefer join for many known string pieces: O(k+L) construction, with O(L) output storage; generating/materializing pieces has its own cost.

• Need efficient operations at both ends → collections.deque offers approximately O(1) endpoint appends/pops and endpoint indexing, but middle indexing is O(n).

• List slices copy the selected references. Sum their lengths to count work; fixed-width windows are not automatically quadratic. A memoryview can share a byte buffer, with a different mutation/lifetime contract.

• The three workhorse patterns cover most array problems: two pointers (sorted, pair/partition), sliding window (contiguous subarray with a constraint), and prefix sums (O(1) range queries after O(n) setup).

Trigger: Fire this model the moment you see: string concatenation in a loop · list.pop(0) or insert(0, x) · a nested loop recomputing a sum over a range · df = df.append(row) inside a loop · a job whose runtime quadrupled when input doubled.

Decision: You must find whether any two elements sum to a target. Sort and use two pointers, or use a hash set in one pass?

Name: Sort + two pointers

Gain: O(1) extra space beyond the sort, cache-friendly sequential access, and it generalises directly to three-sum, closest-pair, and interval problems; the sorted array is often reusable for other queries

Cost: O(n log n) from the sort, and it destroys the original ordering — so if you need the original indices you must carry them along, which reintroduces the memory you saved

Pick: the data is already sorted, or memory is the binding constraint, or you need several order-dependent queries over the same data and can amortise one sort across them

Name: Hash set, single pass

Gain: expected O(n) time using complements without reordering input. A set answers existence; use a value-to-index dictionary if the answer must include original positions

Cost: O(n) extra memory with substantial per-entry overhead in Python; random access patterns are cache-hostile; and it requires hashable elements, ruling out unhashable keys

Pick: the data is unsorted, memory is available, and you need this answer once — the correct default for the standard design review version of the problem

Name: Push it into a database or dataframe join

Gain: a database can plan joins using statistics and, when supported/configured, spill beyond memory. For pair sums enforce distinct row identities and avoid returning duplicate pairs

Cost: fixed overhead that dominates for small inputs, less control over the execution strategy, and debugging moves into query plans

Pick: the data doesn't fit in memory or already lives in a table — at which point pulling it into Python to loop over it is the actual mistake

Verdict: Hash set unless memory or existing sort order says otherwise. The decision is a straightforward time-versus-space trade, and in most application code space is the cheaper resource — but that inverts sharply at scale, which is precisely why both external sorting and partitioned hash joins can handle data beyond RAM, depending on the engine and query plan. The judgement worth carrying: recognise which of the three regimes you are in before optimising. Hand-optimising a Python loop over data that should have been a SQL join is effort spent on the wrong layer entirely, and no amount of two-pointer cleverness recovers it.

(c) Hands-on · 25 min

Save as arrays_strings.py. Runs top to bottom, prints results, no dependencies beyond stdlib.

"""arrays_strings.py — the two-pointer + sliding-window canon.
 
Run:  python arrays_strings.py
"""
from __future__ import annotations
 
 
# ------------------------------------------------------------------
# 1) Reverse in place — the classic opposite-ends two-pointer
# ------------------------------------------------------------------
def reverse_in_place(a: list) -> list:
    """Reverse the list in-place, O(n) time, O(1) extra memory."""
    left, right = 0, len(a) - 1
    while left < right:
        a[left], a[right] = a[right], a[left]
        left += 1
        right -= 1
    return a
 
 
# ------------------------------------------------------------------
# 2) Two-sum on a sorted array — opposite-ends with a condition
# ------------------------------------------------------------------
def two_sum_sorted(a: list[int], target: int) -> tuple[int, int] | None:
    """Sorted nondecreasing integer input; return any distinct-index pair, else None. O(n)."""
    left, right = 0, len(a) - 1
    while left < right:
        s = a[left] + a[right]
        if s == target:
            return left, right
        if s < target:
            left += 1        # need a bigger sum → move left up
        else:
            right -= 1       # need a smaller sum → move right down
    return None
 
 
# ------------------------------------------------------------------
# 3) Remove duplicates from a sorted array — same-start two-pointer
# ------------------------------------------------------------------
def remove_duplicates(a: list[int]) -> int:
    """Sorted input: stable unique prefix, unchanged length; return prefix length. O(n)."""
    if not a:
        return 0
    slow = 0
    for fast in range(1, len(a)):
        if a[fast] != a[slow]:
            slow += 1
            a[slow] = a[fast]
    return slow + 1
 
 
# ------------------------------------------------------------------
# 4) Valid palindrome (ignoring non-alphanumerics + case)
# ------------------------------------------------------------------
def is_palindrome(s: str) -> bool:
    left, right = 0, len(s) - 1
    while left < right:
        while left < right and not s[left].isalnum():
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1
        if s[left].lower() != s[right].lower():
            return False
        left += 1
        right -= 1
    return True
 
 
# ------------------------------------------------------------------
# 5) Longest substring without repeating characters — sliding window
# ------------------------------------------------------------------
def longest_unique_substring(s: str) -> int:
    """Return length of the longest substring with all distinct chars. O(n)."""
    seen: dict[str, int] = {}   # char -> most recent index
    left = 0
    best = 0
    for right, ch in enumerate(s):
        if ch in seen and seen[ch] >= left:
            left = seen[ch] + 1     # jump left past the previous occurrence
        seen[ch] = right
        best = max(best, right - left + 1)
    return best
 
 
# ------------------------------------------------------------------
# 6) Minimum-size subarray with sum >= target — classic sliding window
# ------------------------------------------------------------------
def min_subarray_len(target: int, nums: list[int]) -> int:
    """Positive integer target, nonnegative integer elements; return shortest length or 0."""
    if target <= 0 or any(x < 0 for x in nums):
        raise ValueError("positive target and nonnegative values required")
    left = 0
    total = 0
    best = float("inf")
    for right, x in enumerate(nums):
        total += x
        while total >= target:
            best = min(best, right - left + 1)
            total -= nums[left]
            left += 1
    return 0 if best == float("inf") else best
 
 
# ------------------------------------------------------------------
# 7) Construction comparison — timing is implementation-dependent
# ------------------------------------------------------------------
def slow_join(pieces: list[str]) -> str:
    out = ""
    for p in pieces:
        out += p              # may copy prefixes; CPython can optimize some cases
    return out
 
 
def fast_join(pieces: list[str]) -> str:
    return "".join(pieces)    # O(k + L) for k pieces, L output code points
 
 
# ------------------------------------------------------------------
# Runner
# ------------------------------------------------------------------
if __name__ == "__main__":
    print("reverse:", reverse_in_place([1, 2, 3, 4, 5]))
    print("two_sum_sorted:", two_sum_sorted([1, 3, 4, 7, 11, 15], 18))
    a = [1, 1, 2, 2, 3, 4, 4, 5]
    k = remove_duplicates(a)
    print(f"remove_duplicates: k={k}  compacted={a[:k]}")
    print("palindrome 'A man, a plan, a canal: Panama':", is_palindrome("A man, a plan, a canal: Panama"))
    print("longest_unique 'abcabcbb':", longest_unique_substring("abcabcbb"))
    print("min_subarray_len target=7 nums=[2,3,1,2,4,3]:", min_subarray_len(7, [2, 3, 1, 2, 4, 3]))
 
    # Measure this environment only; timing does not prove an asymptotic bound
    import time
    pieces = ["x"] * 200_000
    t = time.perf_counter(); slow_join(pieces);  print(f"slow_join  200k: {time.perf_counter()-t:.3f}s")
    t = time.perf_counter(); fast_join(pieces);  print(f"fast_join  200k: {time.perf_counter()-t:.3f}s")

Anatomy of the script

What each function teaches

Name: reverse_in_place

Desc: The canonical opposite-ends two-pointer. O(n) time, O(1) extra memory. Note the tuple-swap idiom — Pythonic and fast.

Name: two_sum_sorted

Desc: The core insight: if the sum is too small, only the left pointer can fix it (moving right would shrink the sum further). This monotonicity is why O(n) is possible.

Name: remove_duplicates

Desc: The prefix through slow contains the distinct values of the processed sorted prefix. Values may be copied to lower indices; the scan and write head advance only forward, giving O(n) work.

Name: is_palindrome

Desc: Two-pointer with skip logic — non-alphanumerics get skipped without extra memory. Watch the nested while loops that keep left < right.

Name: longest_unique_substring

Desc: Sliding window with a hashmap of last-seen index. Left jumps past the previous occurrence — never backwards.

Name: min_subarray_len

Desc: Sliding window with a running sum. Shrink from the left as long as the window remains valid — the classic template.

Name: slow_join / fast_join

Desc: Compare equal outputs first, then treat measured timings as local observations. The benchmark does not prove a speed ratio or growth rate.

What to observe when you run it

reverse: [5, 4, 3, 2, 1] — one pass, one line of swaps. two_sum_sorted on [1,3,4,7,11,15], target 18 returns (1,5) = values (3,15) in zero-based indexing. (3,4) = (7,11) is another valid pair, but not this scan’s first return. remove_duplicates: k=5, compacted [1,2,3,4,5]. The tail contains valid Python values but is unspecified by the compaction contract; read only a[:k]. longest_unique on "abcabcbb" → 3 ("abc"). min_subarray_len target 7 on [2,3,1,2,4,3] → 2 (subarray [4,3]). Both joins return the same string. No fixed speed ratio or growth rate is promised by this single timing.

Goal: Add ‘longest substring with at most K distinct characters’ using the same sliding-window skeleton

Hint: State = dict of char -> count. Window is invalid when len(state) > K. Shrink from the left, decrementing counts, and pop keys that hit 0. Same three-line rhythm as longest_unique_substring.

Completed exercise (k must be a nonnegative integer; k=0 returns 0):

def longest_at_most_k_distinct(s: str, k: int) -> int:
    if not isinstance(k, int) or k < 0:
        raise ValueError("k must be a nonnegative integer")
    from collections import defaultdict
    counts: dict[str, int] = defaultdict(int)
    left = 0
    best = 0
    for right, ch in enumerate(s):
        counts[ch] += 1
        while len(counts) > k:
            counts[s[left]] -= 1
            if counts[s[left]] == 0:
                del counts[s[left]]
            left += 1
        best = max(best, right - left + 1)
    return best
 
# Test:
print(longest_at_most_k_distinct("eceba", 2))   # expected 3 ("ece")

Contracts, invariants and costs

All integer algorithms here count arithmetic/comparisons as O(1); arbitrary-size Python integers add bit-cost. two_sum_sorted and remove_duplicates assume sorted input and do not sort or validate it. Reverse returns the same list object; compaction mutates only prefix slots and preserves list length. The pair/window functions do not mutate input. Empty input gives the natural empty/zero/None results; a palindrome of only punctuation is true.

is_palindrome compares each retained Unicode alphanumeric code point after per-code-point lower(), not whole-string casefolding or grapheme normalization. Thus “ßs” is false here even though full casefolding produces “sss”. longest_unique_substring also counts code points. For “abba”, the final a must not move left backwards from 2 to 1; the seen[ch] >= left guard preserves the invariant. Its last-seen dictionary can retain every distinct character seen: O(min(n, alphabet size)) storage, not merely current-window size.

For a positive target and nonnegative values, removing the leftmost value cannot increase the sum. While the sum qualifies, record its length then shrink; for [2,3,1,2,4,3] and target 7, [4,3] gives 2. If negatives were allowed, [1,-1,3] with target 3 would wrongly return 3 instead of 1 in the unguarded algorithm; the guard now rejects that domain. Negative targets were not safe empty-window extensions. The guard is another O(n) pass and uses O(1) auxiliary state.

The at-most-k exercise returns 3 for “eceba”, k=2, and 0 for k=0 or empty input. Each right pointer visits n positions and each left pointer advances at most n times; expected constant-time dict operations give expected O(n) time. The count dictionary has at most k+1 entries during repair. A fixed-width-window sum uses a different invariant: add the entering value, subtract the leaving one, then compare complete windows.

Rain-water stretch: an executable answer

For nonnegative integer heights, a location holds min(max height to its left, max height to its right) minus its own height. A lower established boundary is enough to settle that side without inspecting the whole other side.

def trapped_water(heights: list[int]) -> int:
    if any(h < 0 for h in heights):
        raise ValueError("nonnegative heights required")
    left, right = 0, len(heights)-1
    left_max = right_max = water = 0
    while left <= right:
        if left_max <= right_max:
            left_max = max(left_max, heights[left])
            water += left_max - heights[left]
            left += 1
        else:
            right_max = max(right_max, heights[right])
            water += right_max - heights[right]
            right -= 1
    return water
 
assert trapped_water([3,0,2,0,4]) == 7

O(n) time and O(1) auxiliary space, input unchanged. If the new current height exceeds the opposite established maximum, its contribution is zero, so updating the local maximum is still safe. Otherwise the opposite side already supplies a tall-enough wall.

(d) Production reality · 15 min

Caption construction without an invented benchmark

Use " ".join(tags) to create separated tags, then add a trailing space only if the format requires it. Joining ['a','b'] gives 'a b'; the original loop adding tag + ' ' gave 'a b ', so a performance rewrite can alter output. Preserve formatting and escaping semantics before timing. The archived Instagram latency numbers are not established; the portable mechanism is controlled construction instead of potentially copying prefixes.

Parser bounds: the Cloudflare report and a safe model

Cloudflare's incident report describes an HTML-parser memory leak disclosed in 2017, including a bounds check using equality rather than a greater-than-or-equal check. It does not support the archived claim that the fix was a wholesale Rust rewrite or that every CDN cache was purged. The operational lesson is to track the actual end condition and remediation, not invent an implementation history.

A local model is while pos < len(buffer): consume(buffer[pos]); pos += 1; validate any larger jump before accessing. With length 3 and pos=4, pos == len(buffer) is false but pos >= len(buffer) detects that the cursor is past the end. Python indexing raises IndexError, unlike an unchecked C memory read; Python negative indices are valid, so a parser must also reject a negative cursor. This fixture models a bounds condition, not the production exploit.

Parse a declared format, then validate fields

Whitespace splitting is valid for a format that forbids spaces inside fields; it is not a parser for quoted free text. The line GET "/a b" 500 cannot be interpreted by fixed indices after plain split. A declared JSON record such as {"method":"GET","path":"/a b","status":500} preserves the path. Parse it with json.loads, require a mapping, a string path and an integer HTTP status in 100..599, and reject or quarantine malformed records rather than silently count success. Structured logging has serialization/schema costs; it is not free, but gives named fields and an explicit validation boundary. Tokenizers and path normalizers likewise need an encoding/grammar contract, not generic slicing guesses.

Where this shows up in the rest of the plan

Root: Two-pointer + sliding-window shows up everywhere

Label: Hashmaps & Sets

Desc: Unsorted + two-pointer → falls back to hashmap. Complement pattern.

Label: Stacks & Queues

Desc: Monotonic stack/queue = sliding window's cousin (next-greater-element, sliding max).

Label: Binary Search

Desc: ‘Sorted array + condition’ is often binary search OR two-pointer — know both.

Label: Dynamic Programming

Desc: When windows aren't enough (choices per index), DP takes over.

Label: Log Parsing at Scale

Desc: Streaming parsers need stable record boundaries, validated fields and explicit handling of malformed lines.

Label: Tokenisation for LLMs

Desc: Tokenizers operate on defined byte/code-point/token sequences; BPE merges adjacent symbol pairs according to learned priorities, not this lesson’s uniqueness-window invariant.

(e) Recall + stretch · 10 min

Self-check (answer follows each question).

Recall — questions with written answers

Q: Why is Python list index access O(1)?

A: A CPython list stores contiguous reference slots, so indexing computes the slot directly and performs bounds/reference work without walking earlier slots. This O(1) complexity is not a literal machine-instruction count.

Q: Why is inserting at the front of a list O(n)?

A: Every existing element must shift one slot to the right to make room. Deque (collections.deque) offers O(1) appendleft using a doubly-linked block structure.

Q: When does two-pointer work on a sorted array but not an unsorted one?

A: When the condition (like ‘sum < target’) tells you unambiguously which pointer to move. Sorting gives you that monotonicity: if the sum is too small, only moving left up can grow it.

Q: Give the 3-line sliding-window template in pseudocode.

A: For a longest valid window, use this pseudocode; state-specific remove/add operations must maintain the invariant.

for right in range(n):
    add(a[right])
    while invalid():
        remove(a[left]); left += 1
    best = max(best, right - left + 1)

A minimum qualifying-sum window instead records while valid before shrinking.

Q: When can repeated immutable concatenation be quadratic, and what changes in CPython?

A: Repeated immutable concatenation can be quadratic; CPython optimizes some unaliased local += cases. Do not rely on that implementation detail for a portable bound. join copies the pieces into one result.

Q: What does list slicing (a[i:j]) cost in time and memory?

A: O(k) time and O(k) extra reference slots for k selected elements, after index normalization/clipping, plus O(1) overhead. A new shallow list is created; its nested objects remain shared. Summing slice lengths decides the loop cost.

Q: For ‘remove duplicates from a sorted array in place’, what invariant does the slow pointer maintain?

A: a[0..slow] contains only unique values in the original order. The fast pointer scans ahead; whenever it finds something different from a[slow], slow advances and we write into that slot.

Q: Which mutations are unsafe while iterating over a list?

A: Removing elements can shift later values beneath the iterator and skip them; appending can extend iteration and even prevent termination. A normal list iterator stops at the current end rather than raising IndexError merely because the list shrank. Value replacement or the explicit slow/fast compaction invariant can be safe. Use a copy or filtered result when changing membership.

Q: What's the difference between a Python list and a numpy array?

A: A CPython list stores object references and supports heterogeneous values. An ndarray has a dtype, shape and strides; basic views can be noncontiguous and object-dtype arrays store references too. NumPy supports vectorized numerical operations; choose by representation, copying and workload, not an unconditional fast/slow rule.

Q: Stretch — write a two-pointer solution for the ‘trapping rain water’ problem in your head, then explain the invariant.

Stretch: true

A: Track left_max and right_max from the processed boundaries. Process the side with the smaller established maximum, update that maximum with the current height, add the nonnegative difference, then advance. If the current height exceeds the opposite bound, its contribution is zero; otherwise the opposite bound already supplies a sufficient wall. The executable answer above checks nonnegative heights, preserves input, and uses O(n) time/O(1) auxiliary space.

Explain-out-loud test

Teach these three in one minute each, no notes:

1. Why does Python list index access cost O(1) but list-front-insert cost O(n)?
2. What is the sliding-window template, and give one problem it solves.
3. When can repeated concatenation cost quadratic work, and what does join change?

Grind this pattern in the LeetCode track

This session builds the mental model for arrays, hashing & two pointers. The full pattern treatment — templates, five graded problems each, and the design review follow-ups — lives in the dedicated LeetCode series:

L04 · Arrays & Strings · L05 · Hashing · L07 · Two Pointers I · L08 · Two Pointers II

Do the concept here, then go there to build the reflex.

Explain-out-loud answer guide

1. A CPython list indexes a reference slot by position in constant time; front insertion shifts all existing slots. A dynamic array's append is amortized constant time, not a guarantee for each resize.
2. Define a window and maintain its state as boundaries move. Longest-unique repairs duplicates then records length; shortest qualifying nonnegative sum records before shrinking, so one memorized recording order cannot solve both.
3. Copying accumulated prefixes can sum to quadratic work. CPython may optimize some concatenations, so no timing theorem follows from syntax. join plans one result from k pieces totaling L characters in O(k+L) work; preserve separators and formatting.

Optional archived videos

These are retained resource identities, not governing evidence. Playback, duration and suitability were not verified. The archived “Python Lists — In Depth” card incorrectly shares the 3Sum URL; do not treat it as a verified Corey Schafer lesson.

• 3Sum - Leetcode 15 - Python — archived label, unverified.
• Sliding Window Technique Explained — archived label, unverified.
• Python Lists — In Depth — archived label, unverified.

What comes next

Next: S024 · Hashmaps & Sets — Hash Functions, Collisions

Hub: The 6-Month Learning Plan

Part of a 130-session evergreen learning series. Session structure: intuition → visual → hands-on → production war stories → recall. Duration: 90 minutes.

Corrective source notes

• Python 3.12 sequence operations — immutable concatenation, slicing and Unicode strings.

• CPython 3.12.3 list implementation — growth, indexing, shifting and sorting storage are implementation-specific.

• NumPy ndarray — shape/stride/dtype model, including views.

• collections.deque — endpoint operations and middle-index cost.

• 5. Data Structures — Python 3.14.8 documentation — list.copy returns a shallow copy; nested mutable elements may remain shared. Checked 2026-10-07.

These citations support the named claims, not blanket certification of the lesson. Worked proofs are derived in the text; execution scope and finite-test limits are recorded separately.