Arrays — the workhorse in disguise

Most Python developers use list every day without thinking about what it actually is. Worth thinking about.

A Python list is a dynamic array. Memory-contiguous. When you create [1, 2, 3], CPython allocates a small contiguous block, stores pointers to the three integer objects in it, and tracks length and capacity. When you append and exceed capacity, Python allocates a new block (typically 1.125x the old size — Python's growth factor is small, not 2x), copies pointers over, and frees the old block.

Why this matters for your daily work — the operations have asymmetric costs.

Append — O(1) amortised. Most appends are cheap; occasional ones trigger a resize. The 'amortised' is key — averaging over many appends, each is constant.

Index — O(1). Direct memory offset. Same speed as a C array.

Insert at position i — O(n). Every element after i shifts right by one slot. Insert at position 0 in a list of 1M items moves a million pointers.

Delete at position i — O(n). Same shift, in the other direction.

Search by value — O(n). Lists have no idea what they contain. Linear scan.

Search by sorted value — O(log n) with bisect, but ONLY if the list is sorted. Otherwise O(n).

The asymmetry guides design. Append is cheap; insert-at-front is expensive. If you find yourself inserting at the front a lot, switch to collections.deque — same iteration interface, O(1) appendleft and popleft.

If you're searching by value a lot, the list is wrong; you want a set or dict.

The 'list is dynamic array' frame answers most performance questions about lists in advance. Hold it; use it.

Two pointers solve more interview problems than any other technique. Once you can recognise the pattern, half of array problems become routine.

The basic idea — instead of nested loops over the same array, use two integer indices that walk through it together. Three flavours.

Flavour one — slow and fast pointers, both moving forward. Used for cycle detection in linked lists (Floyd's algorithm), removing duplicates from a sorted array, finding the middle of a list.

The slow pointer increments at one rate; the fast pointer increments at a different rate (often double). When they meet — or fail to meet — you've answered something about the structure.

Flavour two — pointers from opposite ends, moving toward each other. Used for palindrome check, two-sum on a sorted array, container-with-most-water type problems.

Left pointer at the start, right pointer at the end. Compare; move whichever pointer makes progress; stop when they meet.

Flavour three — sliding window. Both pointers moving forward, defining a window of interest. Used for longest-substring problems, minimum-window problems, anything 'best subrange'.

Left pointer marks the start of the window; right pointer marks the end. Expand the right; shrink the left when the window violates a constraint. Track the optimum window seen so far.

Why this is the pattern that wins. The brute force for these problems is usually two nested loops over the array — O(n²). Two pointers do it in one pass, each pointer touching each element O(1) times — O(n).

The trick to recognising a two-pointer problem — when the brute force has two indices both ranging over the array, ask if those indices have a relationship that lets them coordinate (one always greater than the other, one always halving the search space, both moving in some direction). If yes, two-pointer is probably the right answer.

Classic problem. Given a SORTED array and a target, find two indices whose values sum to the target.

Brute force — two nested loops, O(n²).

With a hash map — one pass, O(n) time, O(n) space. (We'll do that one tomorrow on the hash-map day.)

With two pointers on a sorted array — one pass, O(n) time, O(1) space. Hard to beat.

Look at the snippet. left starts at 0, right at len(nums) - 1. We compute the sum at the current pair. Three branches.

If sum equals target — found, return.

If sum is less than target — we need a bigger value. The smallest available bigger value is at left+1. Move left right.

If sum is greater than target — we need a smaller value. Smallest available smaller value is at right-1. Move right left.

We stop when left and right meet.

Why this works — because the array is sorted, the value at any index implies a range of possible sums. Moving left right increases the sum. Moving right left decreases it. Each step makes provable progress toward the target. We never need to go back.

The constraint that makes this work is sorting. If the array isn't sorted, you'd need to sort first (O(n log n)) or use a hash map (O(n)). For an unsorted array, hash map wins. For a sorted array (or one you can sort cheaply), two pointers with O(1) extra space is elegant.

This is the cleanest example of two-pointer-from-opposite-ends. Once you've coded it once, you recognise the shape. Container with most water, valid palindrome, three-sum, four-sum — all variations.

Here's a trick that turns 'sum of nums[i..j]' from an O(n) operation into an O(1) one, with O(n) preprocessing.

Given an array nums of size n, build a prefix sum array of size n+1 where prefix[i] = sum of nums[:i]. So prefix[0] = 0, prefix[1] = nums[0], prefix[2] = nums[0] + nums[1], and so on. Computed in one pass, O(n).

Now, sum of nums[i..j] = prefix[j+1] - prefix[i]. O(1) per query. No more re-summing slices.

The payoff explodes with many range queries. If you're answering 1M range-sum queries on an array of 1M items, naive is O(n*q) = 10^12 ops. With prefix sums, O(n + q) = 2*10^6 ops. Six orders of magnitude difference.

Variations on the same idea:

Prefix max — for max-in-range queries. Same shape, max instead of sum.

Prefix XOR — for XOR-in-range queries. Used in subarray-with-given-XOR problems.

2D prefix sums — sum over a rectangle in a matrix. Build prefix[i][j] = sum of submatrix [0..i-1, 0..j-1]. Rectangle sum becomes prefix[r2+1][c2+1] - prefix[r1][c2+1] - prefix[r2+1][c1] + prefix[r1][c1]. Constant per query.

NumPy's cumsum is exactly prefix sum, vectorised. np.cumsum(arr) gives you the prefix sum array as fast as the underlying SIMD allows.

In ML, you'll see prefix sums in time-series feature engineering (rolling means, cumulative metrics) and in batch sampling (cumulative weights for weighted random selection).

O(n) preprocessing for O(1) queries. Free win when you have many queries.

End of Day 16. Arrays are the most-asked structure in interviews and one of the most-used in real code.

What we covered.

Morning, list as a dynamic array. The asymmetric cost profile — append is cheap, insert-at-front is expensive, search-by-value is linear. Knowing this answers most performance questions about lists.

Midday, the two-pointer pattern in three flavours. Slow/fast for cycles. Opposite ends for sorted-array problems. Sliding window for best-subrange. The pattern alone solves a huge fraction of interview problems.

Afternoon, two-sum on a sorted array as the canonical opposite-ends two-pointer. O(n) time, O(1) space. The shape generalises to container-with-most-water, palindrome check, three-sum, four-sum. Code the shape once; reach for it forever.

Evening, prefix sums as the O(1)-range-query trick. O(n) preprocessing, O(1) per query. Saves orders of magnitude when you have many range queries. NumPy's cumsum is this, vectorised.

A pattern across the day — most array tricks are about avoiding redundant work. Don't recompute slices. Don't re-search. Don't nest loops where one pass with two pointers would do. The structure of the problem usually allows a single pass; the algorithm's job is to find it.

Tomorrow, Day 17, strings. Underestimated as a DSA topic. In real ML/data jobs, string manipulation is a daily task — tokenisers, log parsing, name normalisation. The patterns from arrays apply, plus a few that are string-specific.

See you in the morning.