Algorithms from zero
Arrays and strings: multiple-choice review
Crux Multiple-choice synthesis across the arrays-and-strings unit: contiguity costs, two pointers, sliding window, prefix sums, in-place writes, and the string concatenation trap.
Your altitude — climbing toward senior
ZeroJuniorMiddleSenior
You are at middle altitude — in the skySix questions that cut across the whole unit. Each one is a choice you make at a whiteboard or in a code review — not a definition to recite, but the right pattern to reach for and the precondition it quietly depends on.
Goal
Confirm you can connect the array’s contiguity cost model to the patterns built on it — two pointers, sliding window, prefix sums, in-place writes, and strings-as-arrays — and recognise the precondition each one silently assumes.
Quiz
Completed
A profiler shows a hot loop that inserts at index 0 of a 1M-element array on every request. Why is this the bottleneck, and what is the right fix?
Heads-up Indexing is O(1) regardless of size: address = base + i × element_size needs no scan. The cost here is the shifting that front insertion forces, not the lookup.
Heads-up Sorting does not change insertion cost — inserting into the middle or front of a sorted array still shifts O(n) elements. Sorting helps search, not insertion.
Heads-up Only append is O(1) amortized. Insertion at the front or middle is O(n) because of the shift, no matter how the array grows.
Quiz
Completed
You apply the opposite-ends two pointers two-sum to find a pair summing to a target, but it misses pairs you can spot by hand. What is the most likely cause?
Heads-up The converging scan considers every viable pair in one pass; it does not stop after one. The defect is running it on unsorted input, where the move rule no longer tracks the sum direction.
Heads-up Both at index 0 is the same-direction (fast/slow) shape, used for in-place compaction. Two-sum needs opposite ends converging — the bug is the missing sorted precondition, not the start positions.
Heads-up Two pointers is O(n): each pointer moves at most n times. It does not time out here — it returns wrong answers because the sorted precondition is violated.
Quiz
Completed
For 'smallest subarray with sum ≥ target' on positive integers, the variable-size sliding window runs in O(n) even though it has a nested while loop. Why is it not O(n²)?
Heads-up The inner loop can run many times in one outer step and zero in another. The O(n) bound comes from left's total forward-only movement being ≤ n across the whole run, not from a per-iteration cap.
Heads-up This is the variable-size window — its length changes. The fixed-size window is a different shape; here the O(n) bound rests on left and right each moving forward at most n times total.
Heads-up Sliding window works on unsorted arrays and still has the inner shrink loop. The bound is amortized over monotonic, forward-only pointer movement, not from sorting.
Quiz
Completed
A service answers thousands of range-sum queries over a fixed-length log. Each query currently traverses the range. When is precomputing a prefix sum the right call, and what does it cost?
Heads-up Prefix sums only accelerate range-sum-style queries on a static array. They do nothing for insertion, search, or per-element updates, and any element change forces an O(n) rebuild.
Heads-up Building is O(n) once, but it is amortised over thousands of O(1) queries. For large q the precompute pays for itself many times over.
Heads-up Prefix sums need no sorting — they work on any values, including negatives. The only real requirement is that the array stays static between queries.
Quiz
Completed
A reviewer flags that your in-place 'remove all zeros' using a write pointer mutates the caller's array, breaking a later read of the original. What is the correct framing of the tradeoff?
Heads-up Building a new array is the O(n)-space alternative, not a bug fix. The write-pointer approach is correct; the issue is a contract about whether the caller may keep the original.
Heads-up The advantage is memory (O(1) auxiliary), not guaranteed speed. The real tradeoff is space saved versus the original input being overwritten.
Heads-up Direction does not undo mutation — any in-place compaction overwrites cells. To preserve the original you copy it first; you do not change scan direction.
Quiz
Completed
A function builds a large CSV by doing result += line inside a loop over n rows and is unexpectedly slow at scale. What is happening and what is the fix?
Heads-up The concatenation itself is O(n²): each += copies the whole string so far. Even with no I/O, the quadratic copying dominates at scale.
Heads-up Indexing and length are O(1). The cost is the repeated full copies that immutability forces on each +=, not index or length access.
Heads-up + and += do the same allocate-and-copy on immutable strings — both are O(n²) in a loop. The fix is array push plus a single join, not a different operator.
Recap
The through-line of the unit is one cost model and the patterns that exploit it. Contiguity gives O(1) indexing but O(n) shifts, so front/middle insertion is the trap and append is cheap. Two pointers turn nested pair-scans into one pass — but opposite-ends two-sum needs sorted input. Sliding window is O(n) because the pointers only move forward. Prefix sums trade O(n) space for O(1) static range queries. In-place writes buy O(1) space at the cost of the original. And strings are arrays with one sting: immutability makes loop concatenation O(n²) — collect and join instead.