Algorithms from zero
Arrays and strings: free-recall review
Retrieval beats re-reading. For each prompt, say or write a full answer from memory before you open the model answer — the effort of recall is what makes the pattern and its precondition stick.
Reconstruct the unit’s spine — why contiguity sets every cost, why two pointers and sliding window are O(n), what prefix sums trade, what in-place costs, and the string concatenation trap — without looking back at the lessons.
- 01Why does the array's contiguity produce both its strength (O(1) indexing) and its weakness (O(n) middle insertion)?
- 02Two pointers comes in two shapes. Name them, what each is for, and the precondition opposite-ends two-sum depends on.
- 03Why is the sliding window O(n) and not O(n²), even when the variable-size version contains a nested while loop?
- 04What does a prefix-sum array buy you, what does it cost, and when is it the wrong tool?
- 05What does in-place mean precisely, what does it cost, and name the two core in-place techniques from the unit.
- 06A string is algorithmically an array, yet building one by repeated += in a loop is O(n²). Explain why, and give the fix.
If you could reconstruct each answer from memory, you hold the unit’s spine: contiguity sets the whole cost table (O(1) index, O(n) shift, O(1) amortized append); two pointers and sliding window both hit O(n) through forward-only, single-pass movement; opposite-ends two-sum needs sorted input; prefix sums trade O(n) space for O(1) static range queries; in-place buys O(1) space by destroying the input; and strings are arrays that punish loop concatenation with O(n²) — collect and join instead.