Foundation: Arrays & Strings
Master fundamental data structures and basic manipulation techniques essential for solving entry-level problems
The Array/String Cost Model: Reading Constraints as a Complexity Budget
You read the problem, you see a clean idea, you write forty lines, you hit submit — and you get Time Limit Exceeded. Nothing was wrong with your logic. The verdict was decided before you typed the first character, in a line most people skim past: 1 <= nums.length <= 10^5. That line is not decoration. It is the judge telling you, in advance, roughly how many operations you are allowed to spend.
This section teaches the reasoning step that separates people who guess at solutions from people who select them: reading the constraints as a complexity budget, and knowing the cost model of the array and string operations you're about to use. Along the way we'll expose the hidden-copy trap — the one-character edits that silently multiply your runtime by n — and treat auxiliary space as a second, independent budget that the words "in-place" can shrink to zero.
Step 1: Know what each operation actually costs
Most wrong complexity estimates come from treating every line of code as "one step." A Python list is a contiguous block of pointers; a string is an immutable block of characters. Those two facts generate the entire cost table.
arr = [4, 1, 7, 3]
arr[2] # O(1) random index — one pointer arithmetic step
arr[2] = 99 # O(1) in-place write
arr.append(9) # O(1) AMORTIZED — occasional resize, averaged away
arr.pop() # O(1) remove from the end
arr.insert(0, 5) # O(n) every element after position 0 shifts right
arr.pop(0) # O(n) every element after position 0 shifts left
del arr[2] # O(n) same shift, middle deletion
arr[1:3] # O(k) builds a NEW list of k elements (a copy!)
7 in arr # O(n) linear membership scan
arr + [8, 8] # O(n+m) new list, both sources copied
len(arr) # O(1) the length is stored, not counted
Strings behave the same on reads and worse on writes, because they cannot be mutated at all:
s = "algorithms"
s[3] # O(1) index into a character buffer
s[2:6] # O(k) new string, k characters copied
s + "!" # O(n+m) builds a whole new string
"go" in s # O(n*m) assume naive-search cost when budgeting
len(s) # O(1)
(That last line is the number to reason with in an interview. Modern CPython actually uses a two-way search algorithm with better worst-case behavior, but you should never rely on that, and the point stands regardless: in on a string is a scan, not a lookup.)
<table> <tr><th>Operation</th><th>Cost</th><th>Why</th></tr> <tr><td>🎯 Index read/write</td><td>O(1)</td><td>Contiguous memory</td></tr> <tr><td>➕ Append / pop end</td><td>O(1) amortized</td><td>Spare capacity at tail</td></tr> <tr><td>⚠️ Insert / delete front or middle</td><td>O(n)</td><td>Shifts every later element</td></tr> <tr><td>✂️ Slice / substring of length k</td><td>O(k)</td><td>It is a copy, not a view</td></tr> <tr><td>🔍 <code>x in list</code></td><td>O(n)</td><td>Linear scan</td></tr> <tr><td>🔗 Concatenation</td><td>O(n+m)</td><td>New buffer, both copied</td></tr> </table>
💡 Mental Model: The tail of a list is cheap; the front and middle are expensive; and any expression that produces a new sequence pays for every element it contains. "Amortized O(1)" for append means individual appends occasionally trigger a resize-and-copy, but the total cost of n appends is O(n) — safe to treat as constant inside a loop.
Step 2: Convert the input limit into a budget
A competitive judge will comfortably execute on the order of tens of millions of elementary operations inside a typical time limit — in Python, assume something closer to a few million for interpreted loop iterations. That rule of thumb (it is a rule of thumb, not a guarantee; heavy per-iteration work shrinks it) turns the constraint line into a shortlist of admissible complexities.
n ≤ 12 → O(n!) permutations are fine
↓
n ≤ 20–25 → O(2^n) subset enumeration / bitmask DP is fine
↓
n ≤ 100–500 → O(n³) is fine (triple loops, Floyd-style)
↓
n ≤ 2000–5000 → O(n²) is fine (nested loops, interval DP)
↓
n ≤ 10^5 → you need O(n log n) or O(n). O(n²) = 10^10 → dead
↓
n ≤ 10^6–10^7 → O(n) or O(n log n) with a small constant only
Read this ladder in both directions. Downward, it tells you what you may spend. Upward, it leaks the intended solution: a constraint of n ≤ 20 is practically an announcement that the answer involves trying all subsets, because no one caps n at 20 when a linear algorithm exists. Likewise n ≤ 2000 on a subarray problem quietly permits the O(n²) double loop that would be hopeless at 10^5.
🎯 Key Principle: Read the constraint before you brainstorm. The budget prunes the search space of approaches, so you brainstorm inside a smaller, correct set. Every later section in this lesson assumes you've done this arithmetic first.
Step 3: Worked triage on a real constraint line
Given an array of up to 10^5 integers and a target value, return the indices of two numbers that add up to the target.
Compute the brute-force cost first. The obvious idea is a double loop over all pairs: about n²/2 = 5 × 109 iterations. Even at an optimistic 108 operations per second that is a minute of runtime against a limit measured in seconds. Dead on arrival — and you know it in five seconds of arithmetic, not five minutes of typing.
Now enumerate what survives an O(n log n) / O(n) budget. For array problems there are four workhorse shapes, and it is worth learning them as a checklist:
- 🔧 Single pass with running state — one sweep, carrying a small amount of information (best so far, current sum, a counter). O(n) time, O(1) space.
- 🔧 Prefix aggregation — precompute cumulative sums/XORs so any range question becomes two lookups. O(n) preprocess, O(1) per query.
- 🔧 Sort first, then scan — pay O(n log n) to buy structure (order, adjacency of duplicates, converging pointers).
- 🔧 Hash-based lookup — trade O(n) memory to turn the O(n) membership scan into O(1) average.
For two-sum, options three and four both fit: sort + converging pointers is O(n log n) time / O(1) extra space, while a single-pass hash map is O(n) time / O(n) space. Both clear the budget, so the tiebreaker is problem wording — this one asks for indices, and sorting destroys them unless you sort (value, index) pairs. The head-to-head decision procedure for that choice belongs to "Choosing the Technique: Signals in the Problem Statement"; what matters here is that the budget already eliminated the brute force before any of that debate started.
💡 Pro Tip: Write your target on the scratchpad as a sentence before coding: "n up to 1e5 → I get one sort or a couple of linear passes." If your emerging solution needs a scan inside a scan, you have violated a constraint you already agreed to, and you'll notice immediately instead of at submit time.
Step 4: The hidden-copy trap
Here is the failure mode that fools people who did do the arithmetic. Your plan is O(n): one loop, one pass, no nesting. But a single operation inside that loop is secretly O(n), and the product is O(n²).
## ❌ O(n²): every pop(0) shifts the entire remaining list left one slot
def remove_zeros_bad(arr):
out = []
while arr:
x = arr.pop(0) # costs len(arr) — n, n-1, n-2, ...
if x != 0:
out.append(x)
return out
## ✅ O(n): scan by index, never mutate the front
def remove_zeros_good(arr):
out = []
for x in arr: # O(1) per element
if x != 0:
out.append(x)
return out
The loop in remove_zeros_bad runs n times and looks perfectly linear. But the shift costs sum to n + (n−1) + ... + 1 = n(n+1)/2. At n = 105 that is 5 × 109 element moves — the same wall the double loop hit. The fix changed no logic at all; it changed which end of the list gets touched.
Strings have the mirror-image version:
## ❌ Risks O(n²): each concatenation can allocate a fresh string and copy
## every character accumulated so far.
def shout_bad(s):
out = ""
for c in s:
out = out + c.upper()
return out
## ✅ O(n): collect the pieces, pay one copy at the end
def shout_good(s):
parts = []
for c in s:
parts.append(c.upper()) # O(1) amortized each
return "".join(parts) # single O(n) pass
🤔 Did you know? CPython contains an unofficial optimization that can resize a string in place when the variable being appended to is the only reference to it, which sometimes makes out += c behave linearly. It is an implementation detail, not a language guarantee: keep a second reference to out, run on a different interpreter, or build with out = c + out instead, and the quadratic behavior returns in full. Reason about the guaranteed cost, O(n+m) per concatenation. The mutable-buffer construction idiom itself is developed further in "String-Specific Mechanics: Building, Normalizing, and Scanning Characters."
⚠️ Common Mistake: Slicing inside a loop. for i in range(n): window = arr[i:i+k] looks like a single pass but copies k elements per iteration — O(n·k). Track a start index and a length instead, and materialize the slice at most once.
Step 5: Space is a separate budget
Time and space are independent axes, and problems often constrain only the second one. Three phrases in a problem statement are load-bearing:
- 🔒 "in-place" / "modify the array in place" — the caller's array must contain the answer when you return. Returning a fresh list fails the checker even if the contents are right.
- 🔒 "using O(1) extra space" — a constant number of scalars (indices, counters, a swap temp). One auxiliary array of size n disqualifies the solution.
- 🔒 "without using extra space for another array" — the common phrasing that specifically bans the copy-and-write-back shortcut.
By the usual accounting, the output you are required to return doesn't count against your space budget, but everything you allocate to compute it does — including recursion stack depth, which is O(n) for a linear recursive scan even though you never declared an array.
The classic trap is that the idiomatic Python one-liner is almost always the O(n)-space one:
## ❌ Correct contents, wrong contract: chars[::-1] builds a NEW list, so the
## caller's array is untouched and an in-place checker fails you.
def reverse_letters_bad(chars):
return chars[::-1]
## ✅ O(1) extra space, mutates the caller's list as required
def reverse_letters_good(chars):
left, right = 0, len(chars) - 1
while left < right:
chars[left], chars[right] = chars[right], chars[left] # 1 temp slot
left += 1
right -= 1
# no return value: the input list itself now holds the answer
The swap-based machinery in reverse_letters_good is the foundation of a whole family of problems, and it gets its full index-level treatment in "In-Place Transformation: Swaps, Reversal, Rotation, and Write Indices."
One more accounting subtlety worth knowing before you promise O(1) space: sorted(arr) allocates a new list of size n, while arr.sort() sorts in place — but CPython's sort still uses up to O(n) scratch memory in the worst case. If a problem demands strict O(1) auxiliary space, "just sort it" is not automatically free.
🧠 Mnemonic: C-B-C — Constraints (read the limit), Budget (name the target complexity out loud), Costs (audit every line inside your loop against the cost table). Skipping the third step is what produces a correct algorithm with a TLE verdict.
From here on, the budget you compute in this step is the input to every technique decision: each pattern in the following sections is chosen because it fits a specific cell of this ladder, not because it is clever.
In-Place Transformation: Swaps, Reversal, Rotation, and Write Indices
A large family of array and string problems doesn't ask you to compute something — it asks you to rearrange the buffer you were handed, using no meaningful extra memory. The judge often checks the input array itself rather than your return value. These problems all reduce to a small mechanical toolkit: swap two slots, reverse a range, or maintain a write cursor that trails behind a read cursor. Learn the four moves at index level and you stop re-deriving them under time pressure.
The Swap and the Range Reversal
The atomic operation is the swap: a[i], a[j] = a[j], a[i]. Everything else in this section is a disciplined schedule of swaps. The first schedule worth memorizing is range reversal: two indices converge from the ends of [i, j] inclusive, swapping as they go.
def reverse(a, i, j):
"""Reverse the inclusive range [i, j] in place. O(j-i) time, O(1) space."""
while i < j:
a[i], a[j] = a[j], a[i]
i += 1
j -= 1
The loop condition is i < j, not i <= j. With i == j you would swap an element with itself — harmless but pointless — and with i > j you would start un-reversing what you just reversed. Trace [1,2,3,4,5] with i=0, j=4:
start [1, 2, 3, 4, 5]
i=0 j=4 swap → [5, 2, 3, 4, 1]
i=1 j=3 swap → [5, 4, 3, 2, 1]
i=2 j=2 → loop exits (middle element stays put)
That same skeleton, with the swap replaced by a comparison, is a palindrome check: converge from both ends and return False on the first mismatch. Replaced by "reverse the whole buffer, then reverse each word-sized subrange," it is reverse words in a string — reversing the entire character array puts the words in the right order but each word backwards, and a second pass over each word-delimited range fixes them individually. The arithmetic cousin, digit reversal via rev = rev * 10 + x % 10, is the same idea without a buffer (the overflow hazard there belongs to the checklist section).
🎯 Key Principle: Reversal is not a trick you memorize per problem. It is the only O(1)-space primitive that can move an element an arbitrary distance, so any "rearrange without extra memory" problem is probably a composition of reversals.
Rotate by k: Three Reversals
"Rotate the array right by k steps, in place" is the canonical composition. The naive move — rotating one step k times — costs O(n·k), and a temp array costs O(n) space that the problem forbids. The three-reversal trick does it in O(n) time and O(1) space.
def rotate(nums, k):
n = len(nums)
if n == 0: # guard BEFORE the modulo: k %= 0 raises
return
k %= n # normalize: k=10, n=7 behaves exactly like k=3
if k == 0:
return
reverse(nums, 0, n - 1) # reverse everything
reverse(nums, 0, k - 1) # reverse the first k
reverse(nums, k, n - 1) # reverse the rest
Two guards, two different jobs. The n == 0 check exists because k %= n on an empty array is a ZeroDivisionError — a crash on the first row of the edge-case inventory. The k %= n line is not cosmetic either: constraints on these problems routinely allow k far larger than n, and without normalization reverse(nums, 0, k - 1) indexes past the end.
Full trace on nums = [1,2,3,4,5,6,7], k = 3 (expected result: the last three elements move to the front):
input [1, 2, 3, 4, 5, 6, 7]
reverse(0, 6):
i=0 j=6 swap 1↔7 → [7, 2, 3, 4, 5, 6, 1]
i=1 j=5 swap 2↔6 → [7, 6, 3, 4, 5, 2, 1]
i=2 j=4 swap 3↔5 → [7, 6, 5, 4, 3, 2, 1]
i=3 j=3 → exit
reverse(0, 2):
i=0 j=2 swap 7↔5 → [5, 6, 7, 4, 3, 2, 1]
i=1 j=1 → exit
reverse(3, 6):
i=3 j=6 swap 4↔1 → [5, 6, 7, 1, 3, 2, 4]
i=4 j=5 swap 3↔2 → [5, 6, 7, 1, 2, 3, 4]
i=5 j=4 → exit
result [5, 6, 7, 1, 2, 3, 4] ✓
💡 Mental Model: The first reversal gets both blocks into their final positions but internally backwards; the next two un-backward each block. Rotating left by k is the same code with the split point at n - k — or just call the right-rotation with k = n - (k % n).
⚠️ Memorize this one; don't plan to derive it. Most techniques in this lesson you can reconstruct under pressure — the write index falls out of "I need to keep some elements and drop others, so I'll track where the next keeper goes." Three-reversal rotation does not. It depends on noticing that reversing a block twice restores its order, which is not a move you go looking for, and on reframing "rotate right by k" as "the last k elements move to the front as a block," which is not how the problem states itself. Learn it as a unit, along with the two facts that make it usable: k %= n, and left-rotate = right-rotate by n - k.
The Compacting Write Index
The second schedule is a write index (sometimes called a slow pointer): a cursor write that marks the next slot to fill, trailing a read cursor that scans forward. Every element that survives the filter gets copied to nums[write], and write advances only then. At the end, write is the new logical length, and everything from index write onward is garbage the grader ignores.
def remove_element(nums, val):
"""Delete every occurrence of val. Returns the new logical length."""
write = 0
for read in range(len(nums)):
if nums[read] != val:
nums[write] = nums[read]
write += 1
return write
def dedupe_sorted(nums):
"""Sorted input: keep one copy of each value. Returns new length."""
if not nums:
return 0
write = 1 # nums[0] always survives
for read in range(1, len(nums)):
if nums[read] != nums[write - 1]: # compare against last KEPT value
nums[write] = nums[read]
write += 1
return write
Trace dedupe_sorted([1,1,2,2,3]):
write=1, array [1,1,2,2,3]
read=1 nums[1]=1 == nums[0]=1 → skip
read=2 nums[2]=2 != nums[0]=1 → nums[1]=2, write=2 → [1,2,2,2,3]
read=3 nums[3]=2 == nums[1]=2 → skip
read=4 nums[4]=3 != nums[1]=2 → nums[2]=3, write=3 → [1,2,3,2,3]
return 3 (caller reads only nums[0:3] = [1,2,3])
⚠️ Common Mistake: Comparing nums[read] against nums[read - 1] instead of nums[write - 1]. On a plain dedupe of sorted input both happen to work, but the moment the rule becomes "keep at most two copies" the previous read slot may already have been overwritten by a later write — you must always compare against the last value you actually kept.
Move zeros is the same idiom with a cleanup tail: copy every non-zero forward, then fill nums[write:] with zeros. On [0,1,0,3,12], the scan writes 1 to index 0, 3 to index 1, 12 to index 2, leaving write = 3; filling indices 3 and 4 with zeros yields [1,3,12,0,0]. Writing this as a swap of nums[read] and nums[write] instead of a copy avoids the second pass and is the version worth reaching for when the problem says "minimize total operations."
Overwrite Hazards: Which Direction to Scan
The write-index idiom is safe for one structural reason: write never exceeds read. You only ever stomp on a slot whose original value has already been consumed. Every left-shifting compaction inherits that guarantee for free.
The moment a transformation expands — duplicating elements, merging a second array into spare capacity, replacing each space with %20 — the write cursor runs ahead of the read cursor and left-to-right iteration destroys data you still need. The fix is to iterate from the right, where the free space lives.
The problem (Merge Sorted Array): you are handed two arrays that are each already sorted. nums1 has physical length m + n — its first m slots hold real values and the last n are padding zeros. nums2 holds n values. Merge them so that nums1 ends up sorted, in place, with no second array allocated.
That both inputs arrive sorted is the precondition everything below depends on. It means the largest value still unplaced is always sitting at one of the two tails, so you can fill nums1 from the back by repeatedly taking whichever tail is larger — and the back is exactly where the free space is.
def merge(nums1, m, nums2, n):
"""Both inputs are SORTED. nums1 holds m real values then n empty slots.
Fill nums1 from the back, each step taking the larger of the two tails."""
i, j, w = m - 1, n - 1, m + n - 1 # read nums1, read nums2, write
while j >= 0:
if i >= 0 and nums1[i] > nums2[j]:
nums1[w] = nums1[i] # nums1's tail is the larger
i -= 1
else:
nums1[w] = nums2[j] # nums2's tail wins, or nums1 is exhausted
j -= 1
w -= 1
Trace nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3, starting at i=2, j=2, w=5:
3 > 6? no → nums1[5]=6, j=1, w=4 [1,2,3,0,0,6]
3 > 5? no → nums1[4]=5, j=0, w=3 [1,2,3,0,5,6]
3 > 2? yes → nums1[3]=3, i=1, w=2 [1,2,3,3,5,6]
2 > 2? no → nums1[2]=2, j=-1, w=1 [1,2,2,3,5,6]
j < 0 → done. nums1[0..1] already correct in place.
Two properties make this work, and both are exactly what this section is about.
Why writing backwards is safe. The invariant is w == i + j + 1. It holds at the start ((m-1) + (n-1) + 1 = m+n-1) and every iteration preserves it, because each pass decrements w and exactly one of i or j. While the loop runs j >= 0, so w >= i + 1 — the write cursor is always strictly ahead of the nums1 read cursor. You can never clobber a value you haven't consumed. That is the same write ≤ read guarantee as left-shifting compaction, just mirrored.
Why the loop tests only j. When j hits -1, the invariant gives w == i: everything still unread in nums1[0..i] is already sorted and already sitting in precisely the slots it belongs in, so there is nothing left to move. The opposite exhaustion needs no special case either — once i goes negative, the i >= 0 guard short-circuits and every remaining iteration takes the nums2 branch until it drains.
Running the same merge forward would fail on the first step. Take nums1 = [4,5,6,0,0,0], m = 3, nums2 = [1,2,3]: a left-to-right merge wants to write 1 into nums1[0], destroying the 4 it has not read yet.
🧠 Mnemonic: Shrink left, grow right. If the result is no longer than the input, scan left-to-right with a write index; if the result grows into spare capacity, scan right-to-left from the last slot.
💡 Remember: The tell for a data-destroying technique is comparing the write index to the read index at the worst moment of the loop, not the first. Ask: "at the step where the cursors are closest, is the slot I'm about to write still holding a value I haven't read?"
In-Place 2D: Transpose Then Reverse
Rotating an n×n matrix 90° clockwise in place looks like it needs four-way index gymnastics, and it can be done that way — but the decomposition is far easier to remember: transpose, then reverse each row.
def rotate_matrix(matrix):
n = len(matrix)
# 1. Transpose: mirror across the main diagonal.
for i in range(n):
for j in range(i + 1, n): # j starts at i+1, NOT 0
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
# 2. Reverse each row left-to-right.
for row in matrix:
reverse(row, 0, n - 1)
[1 2 3] transpose [1 4 7] reverse rows [7 4 1]
[4 5 6] → [2 5 8] → [8 5 2]
[7 8 9] [3 6 9] [9 6 3]
⚠️ Common Mistake: Writing for j in range(n) in the transpose loop. Every pair (i, j) then gets swapped a second time as (j, i), and the matrix comes back unchanged — a silent no-op that passes no test and looks correct at a glance. Starting j at i + 1 visits each off-diagonal pair exactly once.
For counter-clockwise, reverse each row first, then transpose (equivalently, transpose and then matrix.reverse()). Note this decomposition relies on the matrix being square; a rectangular rotation cannot be done in place at all, because the output has different dimensions.
The other 2D pattern is layer-by-layer traversal, needed for spiral order and for rotation done as a genuine four-element cycle. You process concentric rings, tracking top, bottom, left, right boundaries and shrinking them inward:
layer 0: top=0, bottom=n-1, left=0, right=n-1
↓ walk right along top, then down right, then left along bottom, then up left
↓ top += 1, bottom -= 1, left += 1, right -= 1
layer 1: the inner ring
↓ repeat while top <= bottom and left <= right
The bookkeeping hazard here is the odd-sized centre: with n = 3 the innermost "ring" is a single cell, and a traversal that unconditionally walks all four sides will visit it up to four times. Guard the bottom and left walks with if top <= bottom and if left <= right respectively, or bound the loop with for layer in range(n // 2) when a lone centre cell needs no work (as in rotation, where it is already fixed).
These scans all share a shape — one cursor that consumes, one that produces — and the formal fast/slow two-pointer treatment, including cycle detection and the converging-pointer variants, is developed in the Two Pointers child lesson.
Prefix Sums and Difference Arrays: Precompute Once, Answer Fast
A huge family of medium problems asks the same question many times: what is the total of this stretch of the array? Answer each question by looping, and q queries over n elements cost O(n·q). The fix is to pay one linear pass up front so that every later question becomes two array reads and one subtraction. That trade — precompute an aggregate, then answer by differencing — is the whole idea, and the two directions of it (prefix sums for range queries, difference arrays for range updates) cover a large slice of the subarray problems you will see.
The prefix array and its sentinel
A prefix sum array P stores cumulative totals. Build it with length n + 1 and a leading 0 — that leading zero is the sentinel, and it is not decoration:
index : 0 1 2 3 4 5
arr : 3 -1 4 1 5 9
P index: 0 1 2 3 4 5 6
P : 0 3 2 6 7 12 21
P[k] means "the sum of the first k elements", so P[0] = 0 is the sum of nothing. The contract is:
sum(i..j) inclusive = P[j+1] − P[i]
Check it: sum(2..4) = 4 + 1 + 5 = 10, and P[5] − P[2] = 12 − 2 = 10. ✅
🎯 Key Principle: Without the sentinel you need P[j] - P[i-1], which explodes whenever i == 0 — you must special-case "range starts at index 0" at every call site. The sentinel makes the prefix of nothing a real, addressable entry, so the formula has no special case. One extra slot removes an entire class of off-by-one bugs.
It also makes empty ranges free: if j + 1 == i, the formula gives P[i] − P[i] = 0, which is the correct sum of an empty range. You get that for nothing instead of guarding for it.
class RangeSum:
def __init__(self, nums):
# P has n+1 entries; P[0] = 0 is the sentinel
self.P = [0] * (len(nums) + 1)
for i, v in enumerate(nums):
self.P[i + 1] = self.P[i] + v
def query(self, i, j):
"""Inclusive sum of nums[i..j]; O(1)."""
return self.P[j + 1] - self.P[i]
rs = RangeSum([3, -1, 4, 1, 5, 9])
print(rs.query(2, 4)) # 10
print(rs.query(0, 5)) # 21 <- no special case for i == 0
print(rs.query(3, 2)) # 0 <- empty range, falls out of the formula
Nothing here assumes the values are positive. Prefix sums work identically with negatives — P simply stops being monotonic (notice P dips from 3 to 2 above). That matters later: techniques that require monotonic prefixes, like sliding windows that shrink when the sum grows too large, quietly break on negatives, while prefix differencing does not.
Worked pattern: the pivot index
"Find the index where the sum of everything to the left equals the sum of everything to the right" (a classic warm-up) is prefix thinking without a prefix array. Keep a running left sum; the right sum is whatever is left over.
def pivot_index(nums):
total = sum(nums)
left = 0
for i, v in enumerate(nums):
# right = total - left - v ; compare without building P
if left == total - left - v:
return i
left += v
return -1
print(pivot_index([1, 7, 3, 6, 5, 6])) # 3
Trace on [1,7,3,6,5,6], total = 28: at i=0, left 0 vs right 28−0−1=27; i=1, left 1 vs 28−1−7=20; i=2, left 8 vs 28−8−3=17; i=3, left 11 vs 28−11−6=11 → return 3. ✅ The lesson: once you see "left side versus right side", you rarely need the full array — one running total plus the grand total is enough, in O(1) space.
Prefix and suffix in the same problem: product except self
"Return an array where out[i] is the product of all elements except nums[i]", with division disallowed, is the canonical two-directional version. Sweep left storing the product of everything before i, then sweep right multiplying in everything after i.
def product_except_self(nums):
n = len(nums)
out = [1] * n
prefix = 1
for i in range(n): # out[i] = product of nums[0..i-1]
out[i] = prefix
prefix *= nums[i]
suffix = 1
for i in range(n - 1, -1, -1): # multiply in product of nums[i+1..n-1]
out[i] *= suffix
suffix *= nums[i]
return out
print(product_except_self([1, 2, 3, 4])) # [24, 12, 8, 6]
After the forward pass out = [1, 1, 2, 6]. The backward pass then does: out[3] = 6·1 = 6 (suffix becomes 4), out[2] = 2·4 = 8 (suffix 12), out[1] = 1·12 = 12 (suffix 24), out[0] = 1·24 = 24. ✅
⚠️ Common Mistake: Reaching for "compute the total product once, then divide by nums[i]". Differencing needs an inverse operation, and multiplication has none for 0: a single zero destroys the total product and division by that element is undefined. The prefix/suffix formulation needs no inverse, which is exactly why it survives zeros (and why the problem statement bans division). Integer division would also lose precision even without zeros.
Any associative operation with an inverse
Subtraction is what lets you "cancel" a prefix. So the trick generalizes to every operation that is associative and invertible:
<table> <tr><th>🔧 Aggregate</th><th>🧠 Build step</th><th>🎯 Range formula</th><th>⚠️ Caveat</th></tr> <tr><td>➕ Sum</td><td><code>P[i+1] = P[i] + a[i]</code></td><td><code>P[j+1] − P[i]</code></td><td>Overflow on 64-bit-scale totals</td></tr> <tr><td>🔀 XOR</td><td><code>X[i+1] = X[i] ^ a[i]</code></td><td><code>X[j+1] ^ X[i]</code></td><td>None — XOR is its own inverse</td></tr> <tr><td>🔢 Count</td><td><code>C[i+1] = C[i] + pred(a[i])</code></td><td><code>C[j+1] − C[i]</code></td><td>One array per predicate</td></tr> <tr><td>✖️ Product</td><td><code>Q[i+1] = Q[i] * a[i]</code></td><td>Division — unsafe</td><td>Breaks on any zero</td></tr> </table>
Prefix XOR is the one interviewers reach for most after sums: X[j+1] ^ X[i] is the XOR of a[i..j], because XORing a value twice cancels it. On [4,2,2,6,4], X = [0,4,6,4,2,6], and the XOR of a[1..3] = 2^2^6 = 6, matching X[4] ^ X[1] = 2 ^ 4 = 6. ✅
Prefix counts answer "how many vowels / evens / capital letters in s[i..j]" — build C[i+1] = C[i] + (1 if predicate(a[i]) else 0) and query the same way. For a bounded alphabet you can build 26 such arrays (a 26×(n+1) table) and answer any per-letter frequency question over any range in O(1).
Running-balance problems are prefix counts in disguise: map one symbol to +1 and the other to −1, and the prefix becomes a balance. A parenthesis string is valid exactly when the running balance never dips below zero and ends at zero; a 01 string splits into the maximum number of balanced pieces by cutting every time the balance returns to 0. On "110100" (1 → +1, 0 → −1) the balances are 1, 2, 1, 2, 1, 0 — a single cut at the end, so the whole string is one balanced piece and no prefix is a shorter balanced one.
2D prefix sums: inclusion–exclusion
For "sum of this submatrix, many times", extend the idea to a padded (rows+1) × (cols+1) table where P[i][j] is the sum of the rectangle from (0,0) to (i-1, j-1). The padding row and column of zeros is the 2D sentinel: every boundary case becomes an ordinary case.
Building each cell means adding the cell above and the cell to the left, then subtracting the overlap you counted twice:
P[i+1][j+1] = grid[i][j]
+ P[i][j+1] (rectangle above)
+ P[i+1][j] (rectangle left)
− P[i][j] (the corner counted twice)
Querying the rectangle (r1,c1) to (r2,c2) inclusive is the same inclusion–exclusion shape, run backwards: take the big rectangle, remove the strip above, remove the strip to the left, add back the top-left corner you removed twice.
class Matrix2D:
def __init__(self, grid):
rows, cols = len(grid), len(grid[0])
self.P = [[0] * (cols + 1) for _ in range(rows + 1)]
for i in range(rows):
for j in range(cols):
self.P[i + 1][j + 1] = (grid[i][j]
+ self.P[i][j + 1]
+ self.P[i + 1][j]
- self.P[i][j])
def region_sum(self, r1, c1, r2, c2):
P = self.P
return (P[r2 + 1][c2 + 1]
- P[r1][c2 + 1]
- P[r2 + 1][c1]
+ P[r1][c1])
m = Matrix2D([[1, 2], [3, 4]])
print(m.region_sum(0, 0, 1, 1)) # 10 (whole matrix)
print(m.region_sum(1, 0, 1, 1)) # 7 (bottom row: 3 + 4)
With grid = [[1,2],[3,4]] the table is P[1][1]=1, P[1][2]=3, P[2][1]=4, and P[2][2] = 4 + 3 + 4 − 1 = 10. The bottom-row query is P[2][2] − P[1][2] − P[2][0] + P[1][0] = 10 − 3 − 0 + 0 = 7. ✅ Build costs O(rows·cols) once; every rectangle query after that is four lookups.
💡 Mental model: Every prefix formula is "the big thing minus the parts I don't want." In 1D that's one subtraction; in 2D it's two subtractions and one add-back for the double-counted corner. In 3D it would be four subtractions and three add-backs — the alternating-sign pattern continues, which is why the technique is named after inclusion–exclusion.
Difference arrays: the same idea, reversed
Now flip the problem. You are given m operations of the form "add v to every element in [l, r]" and asked for the final array. Applying each one directly is O(n) per operation, O(n·m) total. A difference array records only the edges of each change and reconstructs the array at the end.
Keep D of length n + 1. To add v on [l, r]:
D[l] += v (from index l onward, add v)
↓
D[r+1] -= v (from index r+1 onward, undo it)
↓
after all m ops: running sum of D gives the final array
The extra slot at index n is what lets r = n - 1 write D[n] without a bounds check — the same sentinel logic as before, on the other end.
def apply_ranges(n, ops):
"""ops = list of (l, r, v), inclusive; O(n + m)."""
D = [0] * (n + 1)
for l, r, v in ops:
D[l] += v
D[r + 1] -= v # safe: D has the extra slot
out, running = [], 0
for i in range(n):
running += D[i]
out.append(running)
return out
print(apply_ranges(5, [(1, 3, 2), (0, 1, 3), (2, 4, -1)]))
## [3, 5, 1, 1, -1]
Trace: start D = [0,0,0,0,0,0]. (1,3,+2) → [0,2,0,0,-2,0]. (0,1,+3) → [3,2,-3,0,-2,0]. (2,4,-1) → [3,2,-4,0,-2,1]. Accumulating gives 3, 5, 1, 1, -1, which matches doing it by hand: index 1 receives +2 and +3, index 2 receives +2 and −1. ✅
💡 Real-World Example: Interval-booking problems are pure difference arrays. Given flight bookings [[1,2,10],[2,3,20],[2,5,25]] over 5 flights (1-indexed), convert to 0-indexed ranges and mark edges: D[0]+=10, D[2]-=10; D[1]+=20, D[3]-=20; D[1]+=25, D[5]-=25, giving D = [10,45,-10,-20,0,-25]. One accumulation pass yields [10, 55, 45, 25, 25] — seats per flight, in O(n + m) instead of O(n·m). The same shape solves "can this shuttle pick up every group?" (add passengers on [start, end-1], then check no prefix exceeds capacity) and hotel-room occupancy.
🧠 Mnemonic: Queries → prefix. Updates → difference. They are inverses: prefix-summing a difference array recovers the array, and differencing a prefix array recovers it too. If a problem mixes many updates and many queries interleaved, neither is enough and you need a Fenwick/segment tree — out of scope here, but recognizing that boundary is what keeps you from forcing the wrong tool.
The edges that decide accepted vs. wrong answer
📚 Negatives are fine, but they change your options. Prefix differencing is indifferent to sign. Anything relying on "the sum only grows as the window widens" is not, so on a problem with negative values, prefer prefix reasoning over window shrinking.
🔒 Overflow is a real submission failure outside Python. With n = 10^5 values up to 10^9, P[n] reaches 10^14 — far past 32-bit range. In Java or C++ declare the prefix array as long/long long; Python's arbitrary-precision integers make this a non-issue, so a solution that passes locally in Python can still overflow when ported.
🔧 Space when you only need a total. If the problem asks a single question (pivot index, whether some cut point balances), keep a running sum instead of materializing P — O(1) extra space. Build the array only when the queries are repeated or when you need to look backwards at earlier prefixes.
⚠️ Common Mistake: Assuming prefix sums alone solve "count subarrays summing to k". They reduce the problem to "how many pairs i < j with P[j] − P[i] = k", which is still a pairwise search — O(n²) if you loop over pairs. Turning it into O(n) requires remembering the prefix values you have already seen, and that pairing of prefix sums with a hash map is developed in the Hash Maps & Sets child lesson. The prefix array is half the technique; recognizing which half you are holding is the skill.
When you meet a new problem, the trigger phrases are narrow enough to memorize: "multiple queries", "sum of subarray", "left part equals right part", "how many X in range" point at a prefix array, and "apply these ranges", "bookings", "how many are active at each point" point at a difference array.
String-Specific Mechanics: Building, Normalizing, and Scanning Characters
A string looks like an array of characters, and for reading purposes it is one. The differences show up the moment you try to write: in Python (and Java, and C#, and JavaScript) strings are immutable, so every apparent edit allocates a fresh string. On top of that, interview strings usually come with an alphabet guarantee — "lowercase English letters only" — which unlocks a family of fixed-size array tricks that would be impossible on arbitrary data. This section is about the handful of mechanics that follow from those two facts.
Construction: Build in a Buffer, Join Once
The single most common performance mistake in string problems is accumulating a result with += inside a loop. Because the string is immutable, result += c allocates a new string of length len(result) + 1 and copies the old contents into it. Do that n times and you have copied 1 + 2 + 3 + ... + n characters — the hidden-copy trap covered in "The Array/String Cost Model."
The fix is mechanical: accumulate into a list of pieces, then "".join(...) exactly once.
def run_length_encode(s: str) -> str:
"""'aaabbc' -> 'a3b2c1'. Builds into a list, joins once at the end."""
if not s: # empty input: state the assumption, handle it
return ""
parts = [] # buffer of fragments, not a growing string
run_char = s[0]
run_len = 1
for c in s[1:]:
if c == run_char:
run_len += 1
else:
parts.append(run_char)
parts.append(str(run_len)) # append pieces separately; join handles the rest
run_char, run_len = c, 1
parts.append(run_char) # flush the final run — the classic omission
parts.append(str(run_len))
return "".join(parts)
Two details deserve attention. First, the final flush after the loop: any "scan runs and emit" loop ends with an unemitted run, and forgetting it is one of the most common wrong-answer bugs in this problem family. Second, parts holds fragments of any length — you never need to append one character at a time, and joining a list of 3-character pieces is no more expensive than joining single characters.
When the problem demands in-place edits — "reverse the words in a character array using O(1) extra space," "modify the input array of characters" — you cannot use a builder at all, because the return contract is the mutated buffer itself. In Python you convert once with chars = list(s), operate with index assignments, and (if a string is required) join at the end. The swap and write-index machinery for that phase belongs to "In-Place Transformation: Swaps, Reversal, Rotation, and Write Indices"; here the point is just the conversion boundary.
<table> <tr><th>🎯 Situation</th><th>🔧 Representation</th><th>📤 Return</th></tr> <tr><td>🧱 Building output left to right</td><td>list of fragments</td><td><code>"".join(parts)</code></td></tr> <tr><td>✏️ Editing in place, O(1) space</td><td><code>list(s)</code> char array</td><td>the mutated list</td></tr> <tr><td>🔍 Read-only scanning</td><td>the string itself</td><td>indices or a count</td></tr> <tr><td>🔢 Counting a bounded alphabet</td><td>fixed-size int array</td><td>the array or a comparison</td></tr> </table>
Character Arithmetic: Turning Letters Into Indices
When a problem says "s consists of lowercase English letters," it is handing you a bounded alphabet — 26 possible values. That means a character can be turned into an array index with a subtraction, and a frequency table becomes a fixed 26-slot list rather than a hash map. Same asymptotic complexity, far smaller constants, and — more importantly for interviews — a much cleaner comparison step.
def is_anagram(s: str, t: str) -> bool:
"""O(n) time, O(1) space: 26 counters for a lowercase-only alphabet."""
if len(s) != len(t): # cheap rejection before any counting
return False
counts = [0] * 26
for c in s:
counts[ord(c) - ord('a')] += 1 # 'a' -> 0, 'b' -> 1, ... 'z' -> 25
for c in t:
idx = ord(c) - ord('a')
counts[idx] -= 1
if counts[idx] < 0: # t has a char s ran out of — early exit
return False
return True # equal lengths + no negatives => all zeros
The early-exit on a negative counter works only because the lengths are already known to be equal; without that check you would have to scan the array at the end. Trace s = "rat", t = "car": after the first loop, index 17 (r) = 1, index 0 (a) = 1, index 19 (t) = 1. Second loop: c → index 2 goes to −1 → return False. Correct.
The same subtraction trick generalizes:
- 🔤
ord(c) - ord('a')→ 0..25 for lowercase; use a 128-slot vector when the problem says "ASCII" or mixes cases, punctuation, and digits. - 🔢
ord(c) - ord('0')→ the numeric value of a digit character.'7'becomes7, not the codepoint 55. - 🔁
chr(idx + ord('a'))goes back the other way when you must emit the character.
⚠️ Common Mistake: reaching for a 26-slot array when the constraints actually say "s consists of printable ASCII" or nothing at all about the alphabet. An uppercase letter maps to a negative index; in Python 'Z' becomes counts[-7], which silently reads from the far end of the list instead of raising, so the bug produces a wrong answer rather than a crash. When the alphabet is unstated or Unicode, use a hash map — the extra flexibility costs you nothing asymptotically.
🤔 Did you know? The 26-slot count vector is why anagram checks are often described as O(1) space. The array size does not grow with n, so it is constant by the problem's own alphabet guarantee — a claim that quietly evaporates if the interviewer follows up with "now support Unicode." Saying "O(1) given the fixed 26-letter alphabet, O(k) in general" out loud is exactly the kind of precision that reads as senior.
Canonical Forms: Make Equivalent Things Identical
A large class of string problems asks whether two things are "the same" under some relaxed notion of sameness. The general solving strategy is to define a canonical form — a deterministic rewrite such that two inputs are equivalent exactly when their canonical forms are equal — and then compare or group on that form.
The canonical form for anagrams is the sorted-character signature: "eat", "tea", and "ate" all normalize to "aet". That key drops straight into a dictionary for grouping.
from collections import defaultdict
def group_anagrams(words: list[str]) -> list[list[str]]:
"""Signature = sorted characters. O(n * k log k) for n words of length <= k."""
groups = defaultdict(list)
for w in words:
signature = "".join(sorted(w)) # 'tea' -> 'aet'
groups[signature].append(w)
return list(groups.values())
def group_anagrams_counted(words: list[str]) -> list[list[str]]:
"""Alternative signature for a guaranteed lowercase alphabet: O(n * k)."""
groups = defaultdict(list)
for w in words:
counts = [0] * 26
for c in w:
counts[ord(c) - ord('a')] += 1
# tuple(counts) for 'tea' == tuple(counts) for 'eat';
# a tuple is hashable, a list is not, so it can be a dict key.
groups[tuple(counts)].append(w)
return list(groups.values())
The two versions differ only in the signature. Sorting is shorter to write and works on any alphabet; the count-tuple version trades a log k factor for a fixed 26-element key and only holds when lowercase is guaranteed. If words are short (k ≤ 100, which is typical), the sorted version is the pragmatic choice — say that trade-off out loud rather than pretending one dominates.
The other canonical form is a normalization pass: fold case and strip characters that the problem declares irrelevant. "Valid palindrome, considering only alphanumeric characters and ignoring case" is literally asking you to define one.
Input: "A man, a Plan: a canal — Panama!"
↓ keep only alphanumeric
"AmanaPlanacanalPanama"
↓ case fold
"amanaplanacanalpanama"
↓ compare against its reverse (or scan from both ends)
palindrome ✅
You have two implementation choices: materialize the cleaned string first (O(n) extra space, trivially readable), or skip non-alphanumerics on the fly while comparing (O(1) extra space, more index bookkeeping). Both are accepted answers; if the problem says O(1) extra space, only the second qualifies. The two-pointer formalization of that in-place scan is developed in the Two Pointer child lesson — the piece that belongs here is the normalization predicate itself: c.isalnum() to filter and c.lower() to fold, applied consistently to both sides of any comparison.
💡 Mental Model: A canonical form is a many-to-one function into a comparison key. Design it by asking, "what differences am I allowed to ignore?" Ignore order → sort. Ignore case → fold. Ignore punctuation → filter. Ignore starting position in a rotation → concatenate the string with itself and search. The key must destroy exactly the ignorable differences and nothing more.
Manual Scanning: Parsing Without split()
Interviewers frequently ban the built-in parser, because the parser is the problem. The core primitive is positional accumulation: num = num * 10 + d. Each new digit shifts the existing value one decimal place left and drops the new digit into the ones place.
Parsing "427":
start num = 0
read '4' num = 0*10 + 4 = 4
read '2' num = 4*10 + 2 = 42
read '7' num = 42*10 + 7 = 427
A full string-to-integer parser layers four concerns on top of that loop: leading whitespace, an optional sign, the digit run, and a clamp on overflow.
def my_atoi(s: str) -> int:
"""Whitespace, optional sign, digits, clamp to 32-bit signed range."""
INT_MIN, INT_MAX = -2**31, 2**31 - 1
i, n = 0, len(s)
while i < n and s[i] == ' ': # 1. skip leading spaces only
i += 1
sign = 1 # 2. at most one sign character
if i < n and s[i] in '+-':
if s[i] == '-':
sign = -1
i += 1
num = 0 # 3. digit run, stop at first non-digit
while i < n and s[i].isdecimal(): # isdecimal, NOT isdigit — see below
num = num * 10 + (ord(s[i]) - ord('0'))
if sign == 1 and num > INT_MAX: # 4. clamp as soon as we exceed
return INT_MAX
if sign == -1 and -num < INT_MIN:
return INT_MIN
i += 1
return sign * num
On " -42abc": the whitespace loop advances i to 3, the sign branch sets sign = -1 and i = 4, the digit loop builds 4 then 42, then 'a' fails the digit test and the loop stops. Return −42. On "words 12": no leading spaces at index 0 ('w'), no sign, 'w' is not a digit, so the digit loop never runs and the function returns 0 — which is the required behavior.
⚠️ isdigit() is the wrong predicate here. It returns True for superscripts like '²' and for non-ASCII numerals such as Arabic-Indic digits, none of which satisfy ord(c) - ord('0') — you'd compute 130 for '²' and silently produce garbage. isdecimal() is the narrowest of the three (isdigit, isnumeric, isdecimal) and is the one that matches what the arithmetic assumes. LeetCode constraints usually make this moot, but pairing a permissive test with a strict conversion is a bug waiting for a different input.
⚠️ Common Mistake: checking for overflow after the loop finishes. Python's integers are arbitrary precision so a post-loop check happens to work there, but in Java or C++ num * 10 + d wraps around mid-loop and the check is already too late. Clamping inside the loop is the portable habit, and it is the version an interviewer expects you to be able to explain. (Numeric overflow more broadly is covered in "Off-by-One Bugs, Edge Cases, and a Pre-Submit Checklist.")
Tokenizing on a delimiter uses the same shape — advance a start index, scan to the next delimiter, record the token — and the important discipline is handling consecutive and trailing delimiters. "a,,b," split on , yields four fields, two of which are empty; whether you emit them depends on the problem, and stating that choice is part of the answer.
Substrings vs Index Ranges
Slicing s[i:j] copies characters, so it costs O(j − i), not O(1). A loop that builds a candidate substring on every iteration inherits that factor: an O(n²) scan over substrings becomes O(n³) if each candidate is materialized. The fix is to carry (start, length) through the loop and slice exactly once at the end.
def longest_palindromic_substring(s: str) -> str:
"""Expand around each center; track indices, slice once."""
if not s:
return ""
best_start, best_len = 0, 1
def expand(left: int, right: int) -> None:
nonlocal best_start, best_len
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
# loop exits one step past the valid range
cur_len = right - left - 1
if cur_len > best_len:
best_start, best_len = left + 1, cur_len
for center in range(len(s)):
expand(center, center) # odd-length palindromes
expand(center, center + 1) # even-length palindromes
return s[best_start:best_start + best_len] # exactly one slice
Trace s = "babad", center 1 ('a'), odd call expand(1, 1): s[1] == s[1] so left→0, right→2; s[0]='b' == s[2]='b' so left→−1, right→3; the loop exits on left >= 0 failing. cur_len = 3 - (-1) - 1 = 3, best_start = 0. The final slice returns "bab". The +1 and −1 adjustments exist because the while always overshoots by one on each side — write that comment in your own code, because it is the single off-by-one that sinks this problem.
❌ Wrong thinking: "I'll keep best = s[left+1:right] inside the loop so I can compare lengths easily."
✅ Correct thinking: "Lengths are integers. Compare right - left - 1 against best_len, keep two ints, and pay for exactly one slice after the loop."
The same discipline applies to sliding-window answers ("longest substring without repeating characters" wants a length, so return the integer and never build a substring at all) and to "minimum window substring" (track best_start and best_len, slice at the end).
Assumptions to State Before You Code
Three ambiguities recur in nearly every string problem, and voicing them takes ten seconds:
- 🔤 Alphabet. Lowercase only, full ASCII, or arbitrary Unicode? This decides 26-slot array vs 128-slot array vs hash map — and with Unicode, whether "character" even means what you think, since a single user-perceived character can span multiple code points.
- 🕳️ Empty input. Is
""possible?s[0]on an empty string raises, and "is the empty string a palindrome?" is a real question with a conventional answer of yes. - 🔠 Case sensitivity.
"Listen"and"silent"— anagrams or not? If comparison is case-insensitive, fold before counting, not after, or your 26-slot index arithmetic breaks on the uppercase codepoints.
🧠 Mnemonic: A-E-C — Alphabet, Empty, Case. Three questions, asked before the first line of code, that eliminate the majority of string-problem rework.
These mechanics are cheap individually; their value is that they compose — a canonical form built with character arithmetic, accumulated into a buffer, and returned as an index range is the skeleton of a surprising number of accepted solutions.
Choosing the Technique: Signals in the Problem Statement
Every array/string problem statement leaks its intended solution. The words "contiguous", "sorted", "how many", "k-th", and "return the indices" are not decoration — each one eliminates most of the toolkit and points at one or two patterns. Reading those signals before writing code is what separates a five-minute solve from twenty minutes of thrashing. This section is the decision procedure: signal in, technique plus target complexity out.
The Signal-to-Technique Table
Start by scanning the statement for the phrase that describes the shape of the answer, then the phrase that describes the input. Those two fix the pattern more often than anything else in the problem.
<table> <tr><th>🔍 Phrase in the statement</th><th>🔧 First technique to reach for</th><th>🎯 Typical target</th></tr> <tr><td>🧩 "contiguous subarray", "substring", "window"</td><td>Sliding window (all-positive / monotone) or prefix sums (negatives allowed)</td><td>O(n)</td></tr> <tr><td>🔢 "the array is sorted" / "find a pair (or triplet)"</td><td>Converging pointers from both ends</td><td>O(n) after sort</td></tr> <tr><td>🧠 "has appeared before", "duplicate", "how many times"</td><td>Hash set (membership) or hash map (counts)</td><td>O(n) time, O(n) space</td></tr> <tr><td>🏅 "k-th largest", "top k", "group by value"</td><td>Sort, counting/bucket array, or size-k heap</td><td>O(n log n) or O(n)</td></tr> <tr><td>🔁 "in-place", "O(1) extra space", "return new length"</td><td>Write index / swaps / reversal</td><td>O(n), O(1) space</td></tr> <tr><td>📊 "many range-sum queries"</td><td>Prefix array built once</td><td>O(n) build, O(1) query</td></tr> </table>
This table covers the large majority of entry-to-medium array/string problems, not all of them — problems that ask for "the longest increasing subsequence" or "all permutations" are signalling dynamic programming and backtracking, which live outside this toolkit. Treat it as a strong first hypothesis, not a proof.
🎯 Key Principle: Two signals that both fire narrow things fast. "Contiguous subarray" + "array may contain negative numbers" kills the sliding window (shrinking the window can increase the sum, so there is no monotone invariant to exploit) and leaves prefix sums paired with a hash map. "Find a pair" + "return the indices" pushes you away from sorting and toward a hash lookup.
Head-to-Head: Three Solutions to One Pairing Problem
Take the canonical shape: given an array nums and a target, return the indices of two numbers that add up to target. Three legitimate approaches exist, and the input properties — not taste — decide the winner.
def pair_brute_force(nums, target):
"""O(n^2) time, O(1) extra space. Works on any input, sorted or not."""
n = len(nums)
for i in range(n - 1): # note: n - 1, the pair-scan bound
for j in range(i + 1, n):
if nums[i] + nums[j] == target:
return [i, j]
return []
def pair_hash(nums, target):
"""O(n) time, O(n) space. Single pass; preserves original indices."""
seen = {} # value -> index seen earlier
for i, value in enumerate(nums):
complement = target - value
if complement in seen:
return [seen[complement], i]
seen[value] = i # store AFTER the lookup, so i != j
return []
## nums = [8, 2, 11, 7, 3], target = 10
## pair_hash: i=0 value=8 need 2 -> not seen, store 8->0
## i=1 value=2 need 8 -> seen at 0 -> return [0, 1]
The third option pays for sorting. On a sorted array, a pair search becomes a converging scan: if the sum is too big, the only way to shrink it is to move the right pointer left; if too small, move the left pointer right. That gives O(n) with no extra memory. But sorting destroys index information, so if the problem wants indices you must sort (value, index) pairs:
def pair_sort_then_scan(nums, target):
"""O(n log n) time, O(n) space -- the (value, index) list is a new array.
If the problem wants VALUES rather than indices, sort nums in place
instead and this becomes O(1) extra space."""
pairs = sorted((value, i) for i, value in enumerate(nums))
left, right = 0, len(pairs) - 1
while left < right:
total = pairs[left][0] + pairs[right][0]
if total == target:
i, j = pairs[left][1], pairs[right][1]
return sorted([i, j]) # restore ascending index order
elif total > target:
right -= 1 # sum too large: shrink from the top
else:
left += 1 # sum too small: grow from the bottom
return []
## Trace on nums = [8, 2, 11, 7, 3], target = 10
## pairs sorted by value: [(2,1), (3,4), (7,3), (8,0), (11,2)]
## left=0 (2), right=4 (11): 2 + 11 = 13 > 10 -> right = 3
## left=0 (2), right=3 (8): 2 + 8 = 10 -> indices 1 and 0 -> [0, 1]
<table> <tr><th>🧩 Approach</th><th>⏱ Time</th><th>💾 Extra space</th><th>✅ Wins when</th></tr> <tr><td>🐌 Brute force</td><td>O(n²)</td><td>O(1)</td><td>n ≤ ~2000, or memory is hard-capped</td></tr> <tr><td>🔀 Sort + converging scan</td><td>O(n log n)</td><td>O(1) on values, O(n) if indices needed</td><td>Input already sorted, or answer is values not indices</td></tr> <tr><td>🗂 Hash lookup</td><td>O(n)</td><td>O(n)</td><td>Unsorted input, indices required, memory available</td></tr> </table>
Notice how the variant flips the ranking. "Two Sum" on an unsorted array returning indices → hash wins. "Two Sum II" where the array is given sorted and the problem demands O(1) extra space → converging pointers win outright, and the hash solution would be a wrong answer on the space constraint. "Does any pair sum to target?" (boolean, values only, input unsorted, O(1) space required) → sort in place and scan; the hash map is disqualified.
When Paying O(n log n) to Sort Is the Winning Move
Sorting is the cheapest structural upgrade available: it buys you monotonicity, and monotonicity is what makes converging pointers, binary search, and adjacent-duplicate detection legal. Three questions decide whether to pay for it.
🔧 Is the log n factor free? With n ≤ 10⁵ and a single test case, O(n log n) and O(n) sit in the same practical bucket — as established in the cost-model section, both fit comfortably. Sorting only becomes the bottleneck when the problem is called in a loop (m queries × n log n) or when n reaches 10⁷-ish scale.
🔒 Does the answer depend on original order? If yes, sorting is disqualified outright unless you carry indices along. "Move all zeros to the end while preserving the relative order of non-zero elements" cannot be solved by sorting — a sort would reorder the non-zeros. "Find the first non-repeating character" needs positions, so you count with a map and then rescan the original string in order.
📋 Do you need indices out? Then either sort (value, index) tuples as above, or skip sorting entirely. A frequent bug is sorting in place, finding the values, and then searching for them in the original array — which breaks silently when the array contains duplicates of the answer values.
💡 Pro Tip: When values are small integers in a bounded range (ages, lowercase letters, scores 0–100), "sort or counting" resolves to counting — a fixed-size count array replaces the comparison sort and drops you to O(n + range) with no log factor. That is why grouping and top-k problems over bounded alphabets have an O(n) answer:
from collections import Counter
def top_k_frequent(nums, k):
"""Group by value with a hash map, then bucket by frequency.
O(n) time, O(n) space -- no comparison sort anywhere."""
counts = Counter(nums) # value -> frequency
buckets = [[] for _ in range(len(nums) + 1)] # index = frequency
for value, freq in counts.items():
buckets[freq].append(value)
result = []
for freq in range(len(nums), 0, -1): # walk from most frequent down
for value in buckets[freq]:
result.append(value)
if len(result) == k:
return result
return result
## nums = [1, 1, 1, 2, 2, 3], k = 2
## counts = {1: 3, 2: 2, 3: 1}
## buckets[3] = [1], buckets[2] = [2], buckets[1] = [3]
## scan freq 6..1 -> collect 1, then 2 -> [1, 2]
The frequency of any value is at most n, which is exactly why a bucket array of length n + 1 is safe and why no sort is needed.
Subarray vs Subsequence vs Subset
One vocabulary slip sends learners down the wrong pattern for the entire attempt. These three words are not interchangeable.
Original: [1, 2, 3]
subarray = contiguous slice, order kept, no gaps
[1] [2] [3] [1,2] [2,3] [1,2,3] -> 6 non-empty
(count is n(n+1)/2)
subsequence = order kept, gaps allowed
[1] [2] [3] [1,2] [1,3] [2,3] [1,2,3] -> 7 non-empty
[1,3] is legal here but is NOT a subarray
(count is 2^n - 1)
subset = order irrelevant, gaps allowed
{1} {2} {3} {1,2} {1,3} {2,3} {1,2,3} -> 7 non-empty
{3,1} and {1,3} are the same subset
The pattern consequences are sharp. Subarray problems are window/prefix problems: there are only O(n²) candidates and both endpoints slide forward, so a linear scan can usually cover them. Subsequence problems have exponentially many candidates, order still constrains you, and the answer is almost always dynamic programming or a greedy scan (longest increasing subsequence, is s a subsequence of t). Subset problems drop the order constraint, which is precisely the licence to sort freely — and sorting first is the standard opening move for subset-sum, partitioning, and combination problems.
⚠️ Common Mistake: Reading "longest subsequence with sum ≤ k" and building a sliding window. The window enforces contiguity the problem never asked for, so it reports a shorter answer than the true optimum — for [10, 1, 10, 1] with k = 2 the window finds length 1 ([1]) while the real subsequence answer is length 2 ([1, 1]). Since order does not affect a sum, that problem wants a sort plus a greedy prefix scan.
🧠 Mnemonic: Sub-A-rray = Adjacent. Sub-S-equence = Sequence (order kept). Sub-S-et = Set (order gone).
Practice Triage: Commit Before You Code
Read each statement, then write down technique + target time + target space before touching the keyboard. Reasoning follows each one.
P1. Array of up to 10⁵ integers, values may be negative. Return the number of contiguous subarrays summing to k. → "Contiguous" + negatives present. Sliding window is illegal (no monotone sum), so it is prefix sums keyed into a hash map of prefix counts. Target: O(n) time, O(n) space. The pairing of prefix sums with a hash map is developed in the Hash Maps & Sets child lesson.
P2. Sorted array of up to 10⁵ integers, return the 1-based indices of the two numbers adding to target. Constant extra space. → "Sorted" + "find a pair" + O(1) space. Converging pointers; no sort to pay for, and indices come straight from the pointers (+1 for 1-based). Target: O(n) time, O(1) space. A hash map is a correctness failure here, not a stylistic one.
P3. Up to 10⁴ lowercase strings, group the anagrams together. → "Group by value" where the value is a canonical form. Hash map from sorted-character signature to list. Target: O(n · k log k) for strings of length k, O(n · k) space. Sorting the array of strings would not help at all; the sort belongs inside each string.
P4. Array of 10⁵ integers, return the k-th largest element. → "k-th largest". Three viable answers: full sort O(n log n), size-k min-heap O(n log k), quickselect O(n) average. At n = 10⁵ the full sort fits the budget, so lead with it, then offer the heap when the interviewer asks for better — and note that if the values were bounded (say scores 0–100), counting makes it O(n + range).
💡 Remember: Say the commitment out loud in an interview before coding — "contiguous plus negatives, so prefix sums with a hash map, O(n) time and O(n) space". If the constraint check fails you have lost thirty seconds, not the whole attempt.
1Off-by-One Bugs, Edge Cases, and a Pre-Submit Checklist
Most rejected submissions are not wrong ideas. They are right ideas with an index that reaches one slot too far, a base case that assumes the answer is non-negative, or a result list whose entries all alias the same buffer. This section is the debugging half of array and string work: broken code, the exact input that breaks it, the fix, and a verification routine you run before you ever press submit.
Boundary discipline: pick one interval convention and never mix them
Every scan you write implies an interval. Inclusive [i, j] means both endpoints hold real data, and its length is j - i + 1. Half-open [i, j) means j is one past the last element, and its length is j - i. Half-open is the convention Python slices, range(), and most window code already use, so mixing in an inclusive j mid-function is how a +1 gets lost.
Here is the single most common failure in the entire category — a pair scan that walks one element too far:
## BROKEN: reads nums[i + 1] on the last iteration
def has_adjacent_duplicate(nums):
for i in range(len(nums)):
if nums[i] == nums[i + 1]:
return True
return False
## has_adjacent_duplicate([1, 2, 3])
## i = 2 -> nums[3] -> IndexError: list index out of range
The fix is to bound the loop by the number of pairs, not the number of elements. There are n - 1 adjacent pairs, so i runs over range(n - 1):
def has_adjacent_duplicate(nums):
for i in range(len(nums) - 1): # n - 1 pairs, so i + 1 is always valid
if nums[i] == nums[i + 1]:
return True
return False
A pleasant side effect: for nums == [], range(-1) is empty, so the empty case needs no special branch. For nums == [7] there are zero pairs and the loop body never runs. One correct bound removed two edge cases.
The second boundary habit is ordering the bounds test before the value test. When you advance a scanner "while the element still matches", the guard must come first, because s[j] with j == n throws immediately:
def compress_runs(s):
"""Group equal adjacent characters: 'aaabbc' -> [('a', 3), ('b', 2), ('c', 1)]."""
res = []
i, n = 0, len(s)
while i < n:
j = i
while j < n and s[j] == s[i]: # bounds FIRST, then value
j += 1
res.append((s[i], j - i)) # half-open [i, j): length is j - i
i = j # next run starts exactly at j
return res
Swap the two conditions to s[j] == s[i] and j < n and the function raises IndexError on every input whose last run reaches the end of the string — which is every non-empty input. Python's and short-circuits exactly like && in Java, C++, and JavaScript, so the rule transfers unchanged: test the index, then dereference it. Notice also that the run is described as [i, j) throughout — j - i is the length, and i = j starts the next run with no +1 anywhere.
🎯 Key Principle: Write the interval convention in a comment above any loop with two indices. Half the off-by-one bugs in interview code come from a function that computes lengths as j - i in one place and j - i + 1 in another.
The edge-case inventory to run on every problem
Run the same short list against every array or string solution. It takes under a minute and it catches the cases graders love.
<table> <tr><th>🧪 Case</th><th>Concrete input</th><th>⚠️ What it usually breaks</th></tr> <tr><td>🕳️ Empty</td><td><code>[]</code>, <code>""</code></td><td><code>nums[0]</code> init, <code>k %= n</code>, division by n</td></tr> <tr><td>1️⃣ Single element</td><td><code>[5]</code></td><td>pair loops, two-pointer setup</td></tr> <tr><td>♊ All identical</td><td><code>[2,2,2,2]</code></td><td>dedupe, window shrink logic</td></tr> <tr><td>📈 Already sorted</td><td><code>[1,2,3,4]</code></td><td>worst-case quadratic paths</td></tr> <tr><td>📉 Reverse sorted</td><td><code>[4,3,2,1]</code></td><td>monotonic-scan assumptions</td></tr> <tr><td>➖ All negative</td><td><code>[-3,-1,-2]</code></td><td>answers initialized to 0</td></tr> <tr><td>🔢 k > n or k == 0</td><td>k=9, n=4; k=0</td><td>slicing, modulo, empty window</td></tr> </table>
The all-negative row has a canonical victim — maximum subarray sum written with a zero baseline:
## BROKEN on all-negative input
def max_subarray(nums):
best = cur = 0
for x in nums:
cur = max(x, cur + x)
best = max(best, cur)
return best
## max_subarray([-3, -1, -2]) -> 0, but no non-empty subarray sums to 0
Trace it: x = -3 gives cur = max(-3, -3) = -3, best = max(0, -3) = 0; the remaining steps never beat 0, so it returns 0 instead of -1. The best = 0 line silently encodes "the empty subarray is allowed", which is a different problem. Seed from real data instead:
def max_subarray(nums):
if not nums:
raise ValueError("contract: at least one element required")
best = cur = nums[0]
for x in nums[1:]:
cur = max(x, cur + x) # best sum ending exactly at x
best = max(best, cur) # best sum seen anywhere so far
return best
For k-shaped problems, decide the two degenerate answers explicitly: k == 0 usually means an empty window or a no-op, and k > n either means "impossible, return the empty answer" or needs the k %= n normalization introduced in the in-place transformation section. Which one it is comes from the problem statement, not from taste — and if the statement is silent, pick one and put it in a comment so your trace stays consistent.
Mutation hazards: iteration, aliasing, and shared buffers
Removing while iterating
nums = [3, 3, 4, 3]
for x in nums:
if x == 3:
nums.remove(x)
print(nums) # [4, 3] -- a 3 survived
The loop advances an internal position while the list shrinks underneath it. Position 0 sees 3 and removes it, leaving [3, 4, 3]; position 1 now sees 4, not the shifted 3; position 2 sees 3 and removes it, leaving [4, 3]; position 3 is past the end, so the loop stops with a 3 still present. Fixes: iterate a snapshot (for x in nums[:]), rebuild (nums[:] = [x for x in nums if x != 3]), or use the compacting write-index idiom when the problem demands O(1) extra space.
Aliasing: two names, one array
a = [1, 2, 3]
b = a # alias: same object
b[0] = 99 # a is now [99, 2, 3]
c = a[:] # copy: independent
grid = [[0] * 3] * 3 # BROKEN: three references to ONE row
grid[0][0] = 1 # -> [[1, 0, 0], [1, 0, 0], [1, 0, 0]]
grid = [[0] * 3 for _ in range(3)] # correct: three distinct rows
Appending a buffer you keep mutating
This is the bug that makes a correct enumeration return a list of identical (often empty) entries:
def subsets(nums):
res, path = [], []
def dfs(i):
if i == len(nums):
res.append(path[:]) # COPY -- res.append(path) would store the live buffer
return
dfs(i + 1) # skip nums[i]
path.append(nums[i])
dfs(i + 1) # take nums[i]
path.pop() # undo, restoring the invariant for the caller
dfs(0)
return res
With res.append(path), every entry points at the same list, and path is empty when dfs unwinds, so the output is [[], [], [], []] for nums = [1, 2]. 💡 Remember: any result that references a mutable buffer must be copied at the moment of capture. Same rule for slices you plan to overwrite and for character arrays you reuse across test cases.
Numeric traps
Python integers are arbitrary precision, so a prefix sum never silently wraps — but two related traps still bite. First, if you write the same solution in Java, C++, or Go, a prefix sum over 10⁵ elements of magnitude 10⁹ reaches 10¹⁴, far past the ~2.1×10⁹ ceiling of a 32-bit int; the accumulator must be 64-bit (long / long long). Second, many problems require clamping regardless of language: string-to-integer parsing typically specifies a 32-bit result range, so the guard belongs inside the digit loop, before the value grows unbounded.
INT_MAX, INT_MIN = 2**31 - 1, -2**31
def clamped_parse(digits, sign):
num = 0
for c in digits:
num = num * 10 + (ord(c) - ord('0'))
if sign > 0 and num > INT_MAX:
return INT_MAX # saturate and stop early
if sign < 0 and num > -INT_MIN:
return INT_MIN
return sign * num
In a fixed-width language you cannot check after the fact, because the overflow has already happened — the equivalent guard is num > (INT_MAX - d) // 10 before multiplying. The same reflex explains the mid = low + (high - low) // 2 habit: in Python (low + high) // 2 is safe, but writing the subtraction form costs nothing and keeps the muscle memory that ports correctly to languages where low + high can wrap negative and send a binary search into an out-of-bounds read.
The dry-run protocol
Before submitting, hand-execute the code on a 4–6 element input using a state table. Four steps, in order:
1. Pick an input that hits one inventory row (e.g. mixed signs)
↓
2. Fill a row per iteration: index, element, every mutable variable
↓
3. State the loop invariant in words, check it holds on EVERY row
↓
4. Check the return contract against the problem statement
Running it on the fixed max_subarray with nums = [-2, 1, -3, 4]. Initialization: best = cur = nums[0] = -2. Invariant: cur is the largest sum of a subarray ending exactly at the current element; best is the largest over all elements seen.
<table> <tr><th>i</th><th>x</th><th>cur = max(x, cur+x)</th><th>best</th><th>✅ Invariant</th></tr> <tr><td>0</td><td>-2</td><td>-2 (init)</td><td>-2</td><td>holds</td></tr> <tr><td>1</td><td>1</td><td>max(1, -1) = 1</td><td>1</td><td>holds</td></tr> <tr><td>2</td><td>-3</td><td>max(-3, -2) = -2</td><td>1</td><td>holds</td></tr> <tr><td>3</td><td>4</td><td>max(4, 2) = 4</td><td>4</td><td>holds</td></tr> </table>
Return 4, which is the subarray [4] — correct. Step 4 is the one people skip, and it has its own checklist: does the judge want the new logical length or the mutated array? An index or a value? 0-based or 1-based (some sorted-pair variants ask for 1-indexed positions)? Sorted output or original order? A solution that computes the right answer and returns it in the wrong shape fails identically to a wrong algorithm.
Automate the inventory so it costs you nothing:
EDGE_CASES = [
[], # empty
[5], # single element
[2, 2, 2], # all identical
[1, 2, 3, 4], # sorted
[4, 3, 2, 1], # reverse sorted
[-3, -1, -2], # all negative
]
for case in EDGE_CASES:
try:
print(f"{case!r:>14} -> {max_subarray(case)}")
except Exception as e:
print(f"{case!r:>14} -> {type(e).__name__}: {e}")
Run it and the empty case reports ValueError, which is the point: it forces you to confirm from the statement whether empty input is even possible. If it is, that raise becomes a documented return value instead of a crash.
The list covers six of the seven inventory rows; the seventh (k > n, k == 0) only applies to functions that take a k, so add those cases to the driver when the signature has one — rotate(nums, 0) and rotate(nums, 9) on a length-4 array are exactly the two calls that catch a missing k %= n or a missing empty guard.
📋 Quick Reference Card: the pre-submit routine
<table> <tr><th>✅ Check</th><th>🔍 Ask</th><th>⚠️ Catches</th></tr> <tr><td>💰 Budget</td><td>n vs target complexity</td><td>hidden-copy O(n²)</td></tr> <tr><td>🎯 Technique</td><td>signal matches pattern?</td><td>subarray vs subsequence mixup</td></tr> <tr><td>📐 Intervals</td><td>[i,j] or [i,j) everywhere?</td><td>±1 length errors</td></tr> <tr><td>🚧 Bounds</td><td>index tested before access</td><td>IndexError</td></tr> <tr><td>🧪 Inventory</td><td>all 7 cases run</td><td>zero-init, k > n</td></tr> <tr><td>🔁 Mutation</td><td>copied before append?</td><td>aliasing, live buffers</td></tr> <tr><td>🔢 Numbers</td><td>64-bit sums, clamp range</td><td>overflow / wrap</td></tr> <tr><td>🧾 Contract</td><td>length or array? index or value?</td><td>right answer, wrong shape</td></tr> </table>
🧠 Mnemonic: B-E-M-N-C — Bounds, Edges, Mutation, Numbers, Contract. Five passes, roughly two minutes, before every submit.
Put this to work immediately in three ways. Keep the EDGE_CASES driver in a scratch file and paste it under every array solution you write, adapting the inputs to the problem's shape. When a submission fails a hidden test, resist rewriting the algorithm — first identify which checklist row the failing input belongs to, because the fix is usually a bound or an initializer, not a new idea. And carry the interval discipline forward: the converging and fast/slow pointer patterns in the Two Pointer lesson, and the window-shrink logic that pairs with Hash Maps & Sets, are built almost entirely out of half-open ranges whose invariants you now know how to verify by hand.