Arrays and Strings

1Contiguous storage and random access

An array stores its elements in one contiguous block of memory. The address of index i is base plus i times the element width, so a read or write at a known index is O(1) — constant work, independent of how long the array is. That is random access: you do not walk from the front.

The same layout is why an unsorted scan still costs O(n): knowing the address of every cell does not tell you which cell holds the value you want, so you may have to look at all of them. Contiguity buys index arithmetic, not free search.

Figure. Five equal cells in one row. Index i lands on the i-th cell by arithmetic; nothing walks the cells in between.

How an index becomes an address

1. Base addressThe array occupies one unbroken block; the runtime knows where index 0 begins.
2. Scale the indexMultiply i by the fixed byte width of one element — every cell is the same size.
3. Add oncebase + i \times width is the cell. One multiply and one add is O(1), whether i is 3 or 3 million.

2Insert and delete force a shift

Contiguous layout makes middle inserts and deletes expensive. To insert at index i in an n-element array you must move every element from i through n-1 one slot to the right first — otherwise you overwrite a live value. That shift touches n-i cells, so the cost is O(n). Deletion is the same walk in reverse: close the gap by sliding the tail left.

Appending at the end of a dynamic array that still has spare capacity is different — no live cell has to move, so that write is O(1) amortized once growth is accounted for. The O(n) bill is for an arbitrary index, not for every mutation.

Figure. Six live values A–F with a hole opened at index 2. The four-cell tail C, D, E, F must each move one slot right before the new value can land — that slide is the O(n) cost (n-i = 4 writes).

Insert at index i

1. Need a holeCell i is already occupied. Nothing can land there until the tail moves.
2. Shift the tailCopy a[n−1] → a[n], then a[n−2] → a[n−1], …, down to a[i] → a[i+1] — n-i writes.
3. Write the new valuea[i] is free; store the insert. One write after the shift.

3Dynamic arrays and amortized append

A dynamic array (Python list, Java ArrayList, C++ vector) keeps a capacity larger than its size. Appends into spare capacity are a single write. When size hits capacity the structure allocates a new block — typically twice as large — copies every live element across, and only then appends. That resize is O(n) when it happens.

Across n appends starting from empty, the doubling copies total 1+2+4+\cdots+n = O(n) element moves. Spread over n appends that is O(1) amortized per append: a few appends pay a large copy, most pay almost nothing, and the average stays constant.

Figure. Resize copy counts for eight appends with doubling. The three growth steps sum to 7 — less than one full extra pass over the final array.

What doubling buys

1. Spare slotIf size < capacity, write at a[size] and bump size — one O(1) step.
2. GrowIf full, allocate ~2× capacity and copy the old block over — O(\text{capacity}) once.
3. AmortizeGeometric copies sum to O(n) over n appends, so the average per append is O(1).

4Prefix sums for range queries

When you will answer many queries of the form "sum of a[i..j]" on a static array, precompute a prefix array P with P[0]=0 and P[k]=P[k-1]+a[k-1]. Building P is one O(n) pass. Each range then collapses to a subtraction: \text{sum}(i,j)=P[j+1]-P[i], which is O(1).

That beats rescanning the slice in O(j-i+1) per query whenever queries outnumber updates. If the array keeps changing, a plain prefix array goes stale — then you need a different structure. For the interview pattern "many range sums, array frozen," prefixes are the default move.

Figure. Each prefix node adds one array value. The bracketed query is the difference of two prefix nodes — no rescan of the slice.

Build, then query

1. SeedSet P[0]=0 so every range formula stays uniform, including ranges that start at 0.
2. AccumulateFor k=1..n, set P[k]=P[k-1]+a[k-1]. Each cell is the sum of a strict prefix.
3. Subtractsum(i,j) = P[j+1] − P[i] drops the head before i and keeps through j.

5Kadane's maximum subarray

The maximum-sum contiguous subarray can be found in one O(n) pass. At each index track current: the best sum of a subarray that ends here. The recurrence is current = max(a[i], current + a[i]) — either start fresh at i, or extend the streak that ended at i−1. A parallel best remembers the largest current seen. Space is O(1) beyond the input.

The trap is restarting: when current + a[i] loses to a[i] alone, the old prefix is abandoned. That is not "skipping" an element inside a kept subarray — the subarray must stay contiguous. Checking all O(n^2) endpoint pairs works but is the wrong first move in an interview.

Figure. Winning window [4, −1, 2, 1]. Cells outside the bracket are contiguous neighbours that Kadane considered and rejected by reset or by a lower best.

One pass

1. SeedSet current = best = a[0]. The answer is at least the first element when the array is non-empty.
2. Extend or resetAt each next value, current = max(value, current + value).
3. Recordbest = max(best, current) after every update. Return best at the end.

Kadane, one pass

def max_subarray(nums):
    current = best = nums[0]
    for value in nums[1:]:
        current = max(value, current + value)
        best = max(best, current)
    return best

Coding lab. Kadane on the nine-number row runs in the app, with checks on your output.

6Immutable strings and concatenation cost

In languages like Java and Python, strings are immutable: any concatenation builds a new string rather than editing the old one in place. A loop that does result = result + next_chunk therefore copies the whole result on every iteration. If the final length is n and you grow by one character at a time, the copies cost 1+2+\cdots+n = O(n^2).

The fix is to accumulate chunks in a mutable buffer — a list in Python, a StringBuilder in Java — and join once at the end. That keeps total character movement O(n). Immutability is a safety property; the quadratic bill is what you pay for ignoring it in a hot loop.

Figure. Immutable strings copy on each append — 1+2+\cdots+n becomes quadratic; use a builder or join.

Why the loop is quadratic

1. Step kresult already holds k−1 characters; appending one more allocates a fresh string of length k and copies all k characters into it.
2. Sum the copiesLengths 1 through n sum to n(n+1)/2 character writes — O(n^2).
3. Buffer oncePush chunks into a list/builder, then join: each character is written a constant number of times, O(n) total.

7In-place two-pointer reverse

Two indices walking toward each other let you reverse or partition an array using O(1) extra memory instead of allocating a second array. For reverse: left starts at 0, right at n−1; swap a[left] with a[right], then step inward until they meet. Each element moves at most once, so time is O(n) and the auxiliary space is two integers.

The same left/right skeleton partitions around a pivot (swap misfits inward) and rotates via reversals. Prefer it when the prompt constrains extra memory — copying into a new array is correct but spends O(n) space the in-place walk does not need.

Figure. First swap exchanges the ends. The next swap will meet at the middle pair; no second array appears.

Reverse in place

1. Place the fingersleft = 0, right = n−1.
2. SwapExchange a[left] and a[right].
3. Step inleft += 1, right −= 1; repeat while left < right.

8Which array technique fits

Interview prompts on arrays and strings usually collapse to one of four moves. Many static range-sum queries → prefix sums. Maximum contiguous sum → Kadane. Reverse, rotate, or partition under a memory cap → two pointers in place. Building a string in a loop → buffer then join, never repeated concatenation.

These are not interchangeable. Prefix sums do not find a maximum subarray; Kadane does not answer arbitrary later range queries without rescanning; two pointers reverse does not make range sums O(1). Pick by the question asked, not by the structure you saw last.

Read the prompt shape in the Prompt → first move table — many frozen range sums → Prefix sums; max contiguous sum → Kadane; in-place reverse/partition → two pointers; string building → buffer then join.