Arrays and strings are the bread and butter of algorithms. By now you've used many techniques on them — hashing, two pointers, sliding windows, binary search. This section adds a few more staples and revisits sorting.
A prefix sum array stores the running total up to each index. With it, the sum of
any range [i, j] is a single subtraction — prefix[j+1] - prefix[i] — instead of a
loop. Combined with a hash map of prefix sums seen so far, you can answer "is there a
subarray summing to k?" or "how many subarrays sum to k?" in O(n), even with
negative numbers (where sliding windows break down).
sum = 0
seen = { 0: 1 } // prefix sum -> how many times seen
for each n in nums:
sum += n
// subarrays ending here that sum to k: seen[sum-k]
seen[sum] += 1
Many array problems become easy once sorted. Merging overlapping intervals, for instance, is trivial after sorting by start. You'll implement merge sort yourself here to see the divide-and-conquer pattern that gives O(n log n).
Strings have their own order — lexicographic (dictionary) order — which isn't the same as numeric order, and can even be redefined (alien dictionaries). Several problems here play with what "sorted" means.
The throughline: arrays and strings reward pre-processing. A prefix-sum array, a sort, or a rank table turns a quadratic scan into something linear or log-linear. Reach for that setup before brute-forcing.