Arrays and strings: hashing, two pointers, sliding window

Before this lesson: basic Python (loops, lists, dicts, functions). Big-O notation is defined below. The Foundations track covers Python and complexity in more depth. Time: about 80 minutes, plus the notebook.

Why this matters #

The ML interview loop at a glance. Interviews for ML roles have several types of rounds. The table shows the usual round types, the roles that usually see them, and the lessons of this track that prepare each one. Companies differ, so treat it as a map, not a rule. MLE = machine learning engineer, RE = research engineer, RS = research scientist.

Why the coding round matters for ML people. Strong researchers often fail this round. The cause is rarely a missing algorithm. It is the routine under time pressure: a slow brute force, an off-by-one error, a wrong complexity claim. Arrays and strings are the most common inputs, and the four patterns of this lesson solve a large share of these problems. The same ideas run in ML code: hashing to remove duplicate documents from a training set, prefix sums and sliding windows over time series.

How to use this track so that you do not forget. Reading a solution feels like learning, but it fades in days. What lasts is retrieval: answering from memory, spaced over time. Each lesson asks you to predict before you read, has quizzes inside the text, and ends with recall cards. Add the cards to your review deck and answer them when they come back. Then solve the notebook exercises without looking at the lesson, and do the timed problems in section 10 aloud.

1. Predict first #

2. The picture #

The routine for every coding problem #

Interviewers grade the process, not only the final code. Follow the same six steps every time:

1. Clarify. Restate the problem. Ask about edge cases: empty input, repeated values, negative numbers, the size of $n$, what to return when there is no answer.
2. Brute force. Say the simplest correct method and its cost in one sentence.
3. Better plan. Say the faster idea, its time and extra space, and why it is correct (the invariant).
4. Code while you talk. Use clear names.
5. Test by hand. Run one normal case, then the edge cases.
6. Final complexity. State time and extra space again.

The brute force is not wasted. It is your test oracle: in the notebook, every fast solution is compared with a brute force on many random inputs.

Size decides the method #

We count basic steps as a function of the input size $n$. CPython (the standard Python) does roughly $10^7$ simple steps per second. For $n = 10^5$, an $O(n^2)$ method needs about $10^{10}$ steps, which is about 1,000 seconds. An $O(n \log n)$ method needs about $n \log_2 n \approx 1.7 \cdot 10^6$ steps, a fraction of a second. So the constraints in the problem tell you what the interviewer expects.

Four ways to remove the inner loop #

The simplest case. Does [3, 1, 4, 1] contain a repeated value? The brute force compares all $n(n-1)/2 = 6$ pairs. With a set: see 3, see 1, see 4, then 1 is already in the set, so the answer is yes. One pass, one $O(1)$ lookup per element. This is the whole idea of the first pattern. The other three patterns remove the inner loop in other ways:

• Hash map: remember what you have seen. A dict summarizes nums[0..j-1]. One lookup replaces the loop over all earlier indices i < j.
• Prefix sums: a range sum is a difference. The sum of a subarray is the difference of two prefix sums. A question about subarrays becomes a question about pairs of numbers, and a hash map answers it.
• Two pointers: use the order. On sorted data, one comparison shows that one end cannot be part of a better answer. Drop it. Each step removes one element, so there are at most $n$ steps.
• Sliding window: reuse the last window. Add the element that enters, remove the element that leaves. Both pointers only move forward, so the total work is $O(n)$.

3. Definitions and main results #

The cost model #

$f(n) = O(g(n))$ means: there are constants $c > 0$ and $n_0$ with $f(n) \le c\,g(n)$ for all $n \ge n_0$. In an interview you state the time and the extra space: the memory you use besides the input and the output.

Two words hide details, and interviewers like to ask about them:

• Amortized $O(1)$: one operation can be slow, but any sequence of $m$ operations costs $O(m)$ in total. Example: list.append sometimes copies the whole list into a larger buffer, but the buffer grows by a constant factor, so the copies add up to $O(m)$.
• Average $O(1)$: the expected cost when the hash function spreads the keys well. A hash table (Python's dict and set) stores each key in a slot chosen by its hash. When many keys land in the same slots (a collision), lookups must compare with all of them. In the worst case (all keys collide) one operation costs $O(n)$. Also, hashing a string of length $L$ costs $O(L)$, so "$O(1)$" really means "$O(1)$ hash computations".

Pattern 1: the hash map #

A hash map has three common uses:

• Complement lookup. "Is there an earlier element that pairs with nums[j]?" Store value → index. Two Sum: for each x, look up target - x.
• Counting. Store value → count, with d.get(x, 0) + 1 or collections.Counter.
• Grouping by a canonical key. A canonical key is a value that is equal exactly for the members of one group. For anagrams, the sorted letters of a word, or the tuple of its 26 letter counts. Keys must be hashable: use a tuple, not a list.

def two_sum(nums, target):
    seen = {}                        # value -> index, for nums[0..j-1] only
    for j, x in enumerate(nums):
        if target - x in seen:       # look up first ...
            return seen[target - x], j
        seen[x] = j                  # ... then insert
    return None                      # O(n) average time, O(n) extra space

Invariant. At the start of step $j$, the map summarizes nums[0..j-1] and nothing else. So every pair $i < j$ is examined exactly once, at step $j$. This is why you look up first and insert second: in the other order, element $j$ can pair with itself (with target = 6 and x = 3).

Pattern 2: prefix sums plus a hash map #

Define the prefix sums $P_0 = 0$ and $P_j = \text{nums}[0] + \dots + \text{nums}[j-1]$ for $j = 1, \dots, n$. Then, for $0 \le i < j \le n$,

Claim. The number of subarrays with sum $k$ equals the number of pairs $i < j$ with $P_i = P_j - k$. One pass computes it in $O(n)$ average time and $O(n)$ extra space.

Proof.

1. Each non-empty subarray nums[i..j-1] corresponds to exactly one pair $(i, j)$ with $i < j$, and its sum is $P_j - P_i$.
2. Walk $j = 1, \dots, n$ and keep count[v] = the number of indices $i < j$ with $P_i = v$. Start with count = {0: 1}: this entry is $P_0$, the empty prefix.
3. At step $j$, add count[P_j - k] to the total. These are exactly the pairs $(i, j)$ whose subarray sums to $k$. Then increase count[P_j].
4. Each pair is counted once, at the step of its right end $j$. Each step does $O(1)$ average work. $\blacksquare$

No sign condition is needed: negative numbers are fine. The same idea answers "subarray sum divisible by $k$" (store $P_j \bmod k$), "longest subarray with sum $k$" (store the first index of each prefix value), and "equal numbers of 0s and 1s" (map 0 to $-1$, then look for sum 0).

Pattern 3: two pointers #

From both ends (sorted input). Start with i = 0 and j = n - 1. At each step, the order shows that nums[i] or nums[j] cannot be part of any better answer, so that pointer moves. Two Sum II on a sorted list: if nums[i] + nums[j] is too small, no partner of nums[i] inside the range is large enough, so i += 1; if it is too large, j -= 1. 3Sum sorts the list, fixes the first element, and runs this two-pointer search on the rest: $O(n^2)$ instead of $O(n^3)$. Skip equal neighbours to avoid repeated triplets.

Container With Most Water. Given heights $h_0, \dots, h_{n-1}$, choose $i < j$ to maximize the area $(j - i) \cdot \min(h_i, h_j)$.

Claim. Start with $i = 0$, $j = n - 1$. Record the area, then move the pointer at the shorter side inward (either one if equal). This finds the maximum in $O(n)$.

Proof.

1. Invariant: every pair that is better than the best area recorded so far has both ends in $[i, j]$.
2. Suppose $h_i \le h_j$. Every pair $(i, k)$ with $i < k < j$ has a smaller width $k - i < j - i$ and a height $\min(h_i, h_k) \le h_i$. So its area is less than $(j - i)\,h_i$, the area just recorded.
3. So no pair that uses $i$ with an end inside the range can beat the record. Pairs with an end outside $[i, j]$ were excluded before (step 1). Dropping $i$ keeps the invariant. The case $h_j < h_i$ is symmetric.
4. Each step moves one pointer inward, so there are $n - 1$ steps. $\blacksquare$

Read/write pointers (same direction). r reads every element and w marks the end of the part you keep. Invariant: nums[0..w-1] is the answer for nums[0..r-1]. Examples: remove all copies of a value in place, remove repeats from a sorted list in place, move all zeros to the end.

Fast and slow pointers on a linked list. A singly linked list is a chain of nodes; each node has a value val and a pointer next to the next node (the last one points to None). To reach the $k$-th node you must walk $k$ steps. Two rules prevent most bugs:

• Save next before you re-link. Reversal moves three pointers together: nxt = cur.next; cur.next = prev; prev = cur; cur = nxt.
• Use a dummy head when the head may change (merge, removal): put a node dummy in front of the list and return dummy.next. Then there is always a node before the one you change.

With a slow pointer that moves 1 node per step and a fast pointer that moves 2: when fast reaches the end, slow is at the middle. Two pointers $k$ nodes apart find the $k$-th node from the end in one pass. And on a list that may end in a cycle, the same two pointers detect the cycle:

Theorem (Floyd's cycle detection). Number the nodes in the order of the walk: $x_0$ is the head and $x_{t+1}$ is the node after $x_t$. If the list has a cycle, let $\mu$ be the index of its first node ($\mu = 0$ if the head is on the cycle) and $\lambda \ge 1$ the number of nodes on it, so the list has $n = \mu + \lambda$ nodes. Phase 1: slow moves 1 node and fast moves 2 nodes per step, so after $t$ steps they are at $x_t$ and $x_{2t}$. Phase 2: after they meet, put one pointer back at the head and move both by 1 node per step.

Claim. Without a cycle, fast reaches None. With a cycle, phase 1 meets after $t^*$ steps, where $t^*$ is the smallest positive multiple of $\lambda$ with $t^* \ge \mu$. Phase 2 meets exactly at the first cycle node $x_\mu$, after $\mu$ steps. Time $O(n)$, extra space $O(1)$.

Proof.

1. For $s, t \ge \mu$: $x_s = x_t$ if and only if $s \equiv t \pmod{\lambda}$, because after $\mu$ the walk repeats with period $\lambda$. Each node $x_0, \dots, x_{\mu-1}$ before the cycle appears only once in the walk.
2. Phase 1 meets at step $t \ge 1$ when $x_t = x_{2t}$. If $t < \mu$, the node $x_t$ appears only at index $t \ne 2t$, so there is no meeting. If $t \ge \mu$, step 1 gives a meeting exactly when $2t \equiv t \pmod{\lambda}$, that is, when $\lambda$ divides $t$. So the first meeting is at $t^*$.
3. Multiples of $\lambda$ are $\lambda$ apart, so $t^* \le \mu + \lambda = n$: phase 1 is $O(n)$.
4. Phase 2 starts with pointer A at $x_0$ and pointer B at $x_{t^*}$. After $k$ steps they are at $x_k$ and $x_{t^* + k}$. For $k = \mu$: $t^* + \mu \equiv \mu \pmod{\lambda}$, because $\lambda$ divides $t^*$. So both are at $x_\mu$.
5. For $k < \mu$, A is still before the cycle and B is on it, so they cannot meet earlier. $\blacksquare$

Pattern 4: the sliding window #

A sliding window is a contiguous range nums[left..right] that moves from left to right.

• Fixed size $k$. After the first window, each step adds one element and removes one: $O(1)$ per step instead of $O(k)$. Example: the maximum sum of $k$ consecutive values.
• Variable size. Move right one step at a time. For "longest": while the window is invalid, move left; then record. For "shortest": while the window is valid, record it and move left.

The variable window needs a property of the condition. Call a condition on windows monotone under shrinking if every window inside a valid window is also valid ("no repeated character" has this property). Call it monotone under growing if every window that contains a valid window is also valid ("sum $\ge$ target" with positive numbers has this property).

Theorem (variable window, longest version). If "valid" is monotone under shrinking, then the loop

left = 0
for right in range(n):
    add(nums[right])
    while not valid():
        remove(nums[left]); left += 1
    best = max(best, right - left + 1)

returns the length of the longest valid window. The loop body runs $n$ times, and left moves at most $n$ times in total, so the time is $O(n)$ when add, remove and valid are $O(1)$.

Proof.

1. For each right $= r$, let $\ell(r)$ be the smallest $l$ such that the window $[l, r]$ is valid (the empty window is valid, so $\ell(r) \le r + 1$). Because valid is monotone under shrinking, $[l, r]$ is valid exactly when $l \ge \ell(r)$.
2. $\ell$ never decreases: if $[l, r+1]$ is valid, then its part $[l, r]$ is valid. So $\ell(r) \le \ell(r+1)$.
3. By induction on $r$: when step $r$ starts, left $= \ell(r-1) \le \ell(r)$. The while loop moves left until the window is valid, so it stops exactly at $\ell(r)$.
4. So the recorded length at step $r$ is the longest valid window that ends at $r$. The maximum over all $r$ is the answer.
5. Cost: left only increases and never passes $n$, so the inner loop runs at most $n$ times over the whole run, although it sits inside a for loop. $\blacksquare$

from collections import Counter

def min_window(s, t):
    need, missing = Counter(t), len(t)
    left, best = 0, (0, float("inf"))         # best = (start, end) of the shortest window
    for right, ch in enumerate(s):
        if need[ch] > 0:
            missing -= 1                       # ch was still needed
        need[ch] -= 1
        while missing == 0:                    # valid: record, then shrink
            if right - left < best[1] - best[0]:
                best = (left, right)
            need[s[left]] += 1
            if need[s[left]] > 0:
                missing += 1                   # we just removed a needed character
            left += 1
    return "" if best[1] == float("inf") else s[best[0]:best[1] + 1]

print(min_window("ADOBECODEBANC", "ABC"))      # BANC

Answers to section 1. (1) Yes. Store a dict of prefix-sum counts, starting with {0: 1}. At each step add count[P_j - k] to the total. This is $O(n)$ time and $O(n)$ space, and negative numbers are fine. (2) No. With negative numbers a larger window can have a smaller sum, so "sum $\ge$ target" is no longer monotone under growing, and step 4 of the proof fails. Example: [1, -1, 5] with target 5. The window method returns 3 (the whole list), but [5] has length 1. Use prefix sums instead; for "shortest subarray with sum $\ge$ target" with negatives, prefix sums plus a monotonic deque solve it in $O(n)$ (LeetCode 862; the deque appears in lesson 02).

4. Worked example #

Count the subarrays of nums = [2, 1, -1, 1, 2] with sum $k = 3$. The prefix sums are $P = (0, 2, 3, 2, 3, 5)$. At step $j$ we need earlier prefixes equal to $P_j - 3$.

The answer is 4:

• [2, 1] $= P_2 - P_0 = 3 - 0$,
• [2, 1, -1, 1] $= P_4 - P_0 = 3 - 0$,
• [1, -1, 1, 2] $= P_5 - P_1 = 5 - 2$,
• [1, 2] $= P_5 - P_3 = 5 - 2$.

At step 5 one lookup adds 2, because two earlier prefixes ($P_1$ and $P_3$) have the value 2. A set of prefix values, instead of counts, would find only one of them. A sliding window would fail here too, because the list has a negative number.

A second example: the longest substring without repeating characters. For s = "abcabcbb", the condition "no repeated character" is monotone under shrinking, so the longest version applies. Keep a set of the characters in the window.

The answer is 3. right moved 8 times and left moved 7 times: 15 moves, at most $2n = 16$.

5. In code #

Three templates, each checked against a brute force on random inputs. Copy this habit: in an interview, the brute force is your test oracle.

import random


def count_subarrays_with_sum(nums, k):
    """Number of contiguous subarrays with sum k. O(n) time, O(n) space."""
    count = {0: 1}          # prefix-sum value -> number of prefixes with that value; P[0] = 0
    prefix = total = 0
    for x in nums:
        prefix += x                         # prefix = P[j]
        total += count.get(prefix - k, 0)   # earlier prefixes P[i] = P[j] - k
        count[prefix] = count.get(prefix, 0) + 1
    return total


def sorted_squares(nums):
    """Squares of a sorted list, in sorted order. O(n) time: two pointers from both ends."""
    out = [0] * len(nums)
    i, j = 0, len(nums) - 1
    for w in range(len(nums) - 1, -1, -1):  # fill from the largest square down
        if abs(nums[i]) > abs(nums[j]):     # the largest remaining square is at an end
            out[w] = nums[i] * nums[i]
            i += 1
        else:
            out[w] = nums[j] * nums[j]
            j -= 1
    return out


def shortest_window_at_least(nums, target):
    """All nums > 0: length of the shortest subarray with sum >= target, 0 if none."""
    best = float("inf")
    left = window = 0                       # window = sum(nums[left:right + 1])
    for right, x in enumerate(nums):
        window += x                         # x enters
        while window >= target:             # valid: record it, then shrink from the left
            best = min(best, right - left + 1)
            window -= nums[left]            # nums[left] leaves
            left += 1
    return 0 if best == float("inf") else best


# Brute-force references: slow but clearly correct.
def brute_count(nums, k):
    return sum(sum(nums[i:j]) == k for i in range(len(nums)) for j in range(i + 1, len(nums) + 1))


def brute_shortest(nums, target):
    lengths = [j - i for i in range(len(nums)) for j in range(i + 1, len(nums) + 1)
               if sum(nums[i:j]) >= target]
    return min(lengths, default=0)


rng = random.Random(0)
for _ in range(2000):
    nums = [rng.randint(-3, 3) for _ in range(rng.randint(0, 10))]
    k = rng.randint(-4, 4)
    assert count_subarrays_with_sum(nums, k) == brute_count(nums, k)
    assert sorted_squares(sorted(nums)) == sorted(x * x for x in nums)
    pos = [rng.randint(1, 5) for _ in range(rng.randint(0, 10))]
    t = rng.randint(1, 15)
    assert shortest_window_at_least(pos, t) == brute_shortest(pos, t)

print(count_subarrays_with_sum([2, 1, -1, 1, 2], 3))     # 4
print(sorted_squares([-4, -1, 0, 3, 10]))                # [0, 1, 9, 16, 100]
print(shortest_window_at_least([2, 3, 1, 2, 4, 3], 7))   # 2
print(shortest_window_at_least([1, -1, 5], 5), brute_shortest([1, -1, 5], 5))  # 3 1
print("2000 random tests passed")

The fourth line shows the failure with negative numbers: the window answers 3, the brute force 1.

6. Where it shows up #

• Data pipelines. Exact deduplication of a training corpus keeps a set of document hashes: one pass, $O(1)$ average per document. Near-duplicate detection (MinHash) also hashes, then groups documents by a key. Vocabularies and the hashing trick for features are hash maps.
• Time series and science. A moving average over a signal is a fixed-size window: $O(1)$ per sample instead of $O(k)$. The classic STA/LTA earthquake trigger is the ratio of a short-term and a long-term moving average of the signal energy: two windows. With np.cumsum (a prefix sum), the mean of any window is one subtraction; summed-area tables (integral images) do the same for 2-D images.
• Sorted streams. Matching detected events to a catalog, both sorted by time, within a tolerance, is one two-pointer pass instead of a double loop.
• Cycle detection beyond lists. Floyd's method finds cycles in any sequence $x_{t+1} = f(x_t)$ with $O(1)$ memory: in pseudo-random number generators and in Pollard's rho factoring method. The problem "find the duplicate number" (LeetCode 287) is this idea on an array.

7. Common mistakes #

• Insert before lookup in a complement search: the element pairs with itself.
• Hidden linear costs. x in some_list, a.pop(0) or string += inside a loop make the code quadratic. Use a set, a collections.deque, or "".join.
• Forgetting $P_0 = 0$ (count = {0: 1}): you miss every subarray that starts at index 0.
• A sliding window on data with negative numbers for a sum condition: the monotonicity it needs is gone. Use prefix sums.
• Off by one in the window length: it is right - left + 1.
• Wrong complexity claims. A while inside a for is not automatically $O(n^2)$: count the total pointer moves. Dict operations are $O(1)$ on average, not in the worst case.
• Unhashable keys. A list cannot be a dict key; use a tuple (for example, of 26 counts).
• Losing the rest of a linked list by overwriting cur.next before saving it.

8. Check yourself #

1. a has $n$ elements and b has $m$. What does [x for x in a if x in b] cost when b is a list, and when it is a set?
   Answer

   List: $O(nm)$, because each in scans b. Set: $O(m)$ to build it plus $n$ lookups of $O(1)$ average, so $O(n + m)$ average.
2. Run the prefix-sum count on nums = [1, 1, 1], $k = 2$. Give the total after each step.
   Answer

   Start {0: 1}. $P = 1$: need $-1$, total 0. $P = 2$: need 0, total 1. $P = 3$: need 1, total 2. The answer is 2: [1, 1] twice.
3. Run shortest_window_at_least([2, 3, 1, 2, 4, 3], 7) by hand. Which windows are recorded, and how many times does left move?
   Answer

   Recorded lengths: 4 ([2,3,1,2]), 4 ([3,1,2,4]), 3 ([1,2,4]), 3 ([2,4,3]), 2 ([4,3]). left moves 5 times, at most $n = 6$. The answer is 2.
4. Why does sorted_squares need $O(n)$ time and not $O(n \log n)$?
   Answer

   The squares of a sorted list first decrease, then increase (a valley). The largest remaining square is always at one of the two ends, so each step places one value in its final position: $n$ steps of $O(1)$.
5. All $n$ keys of a dict have the same hash. What does building the dict cost?
   Answer

   Each insert compares with all keys stored so far: $O(n)$ per insert, $O(n^2)$ in total. CPython randomizes string hashes per process, so such inputs are hard to build on purpose.
6. "Longest subarray with sum exactly $k$", with negative numbers. What do you store in the dict, and why the first index?
   Answer

   For each prefix value, the first index where it occurs (start with {0: 0}). At step $j$, if $P_j - k$ was first seen at $i$, the subarray nums[i..j-1] has sum $k$ and is the longest one that ends at $j$, because a smaller $i$ gives a longer subarray. Never overwrite a stored index.

9. Interview angle #

Recognize the pattern from the wording.

What to say aloud (about 30 seconds before you code): "The brute force checks all pairs, $O(n^2)$. I will keep a dict of the prefix sums I have seen, with their counts. At step $j$, every earlier prefix equal to $P_j - k$ gives one subarray with sum $k$. That is one pass: $O(n)$ time and $O(n)$ space. I start the dict with $P_0 = 0$ so that subarrays from index 0 count."

Typical questions and short model answers.

1. "What is the complexity of a Python dict lookup?" — "$O(1)$ on average, if the hash function spreads the keys well. In the worst case, when many keys collide, it is $O(n)$. Also, hashing a string costs time linear in its length. CPython randomizes string hashes, so an attacker cannot easily build colliding keys."
2. "Find two numbers that sum to a target." — "Unsorted: one pass with a dict from value to index; for each number I look up the complement before I insert the number. $O(n)$ time and space. If the input is sorted, or if I must use $O(1)$ extra space, I sort and use two pointers from both ends: $O(n \log n)$ time, because the sort dominates."
3. "Why is your sliding window $O(n)$? There is a loop inside a loop." — "Both pointers only move forward. right moves $n$ times, and left can move at most $n$ times in total over the whole run. So the inner loop body runs at most $n$ times overall, not $n$ times per step."
4. "Does your window work with negative numbers?" — "No. With negatives, a longer window can have a smaller sum, so shrinking the window can make it valid again, and the greedy shrink can miss the answer. For sums with negatives I use prefix sums and a hash map, or a monotonic deque for the 'at least target' version."
5. "Detect a cycle in a linked list with $O(1)$ memory." — "Tortoise and hare: one pointer moves 1 node, the other 2 nodes per step. If there is no cycle, the fast one reaches the end. If there is a cycle, once both are on it the gap between them changes by one node per step, so they meet within $O(n)$ steps. To find the cycle start, I put one pointer back at the head and move both by one; they meet at the start, because the meeting step is a multiple of the cycle length."

Typical follow-ups. "$O(1)$ extra space?" (sort, then two pointers; say that the sort costs $O(n \log n)$). "The data is a stream?" (one pass with a dict or a window; you cannot sort). "Too big for memory?" (hash-partition into files so that equal keys land in the same file, then solve each file). "Many queries on the same array?" (precompute prefix sums once, then each range sum is $O(1)$).

10. Practice #

The notebook for this lesson runs in Colab. Try each exercise from memory before you look back at the lesson. Each one is tested against a brute force on random inputs:

1. two_sum: complement lookup with a dict.
2. subarray_sum_k: count subarrays with sum $k$ (negative numbers included).
3. length_of_longest_substring: the longest window without a repeated character.
4. cycle_start: Floyd's algorithm on a linked list built from $\mu$ and $\lambda$.
5. three_sum (optional): all triplets with sum 0, without repeats, in $O(n^2)$.

Timed practice (25 minutes each, talking aloud; the names are the usual problem titles): Contains Duplicate, Valid Anagram, Group Anagrams, Longest Consecutive Sequence, Two Sum II, 3Sum, Container With Most Water, Longest Repeating Character Replacement, Linked List Cycle II, Minimum Window Substring (hard).

Say it aloud drill. Pick one problem from the list. Set a 2-minute timer and explain the brute force, the pattern, the invariant, and the time and space, without code. Record yourself once a week and listen for unclear steps.

11. Watch and read #

• MIT 6.006 Introduction to Algorithms, Spring 2020, course page with notes and problem sets: lecture 2 (dynamic arrays and amortized cost) and lecture 4 (hashing).
• Python documentation, Time complexity of operations on built-in types: list, dict, set and deque costs, with the notes on amortized and average cost.
• Tech Interview Handbook, cheatsheets for arrays, strings, hash tables and linked lists.
• Public problem lists: Grind 75 (choose the topics Array, String, Hash Table, Linked List) and NeetCode 150 (sections Arrays & Hashing, Two Pointers, Sliding Window).
• Wikipedia, Cycle detection: Floyd's and Brent's algorithms, with the same $\mu$ and $\lambda$ notation as this lesson.