Arrays & Strings

One row of same-size boxes, then two ways of walking it that turn a nested loop into a single pass. Builds on Complexity & Big-O and The Memory Hierarchy (cache, locality, the memory wall).

Before you start. You need Complexity & Big-O‘s two words: O(1) means the cost never changes as the pile grows, O(n) means it climbs in step with it. Every trick below is about touching as few boxes as possible.

A street where every house has a number

Say you’re handed a thousand sealed boxes and told box number 3,000 has what you need. If the boxes sit in one line, same size, numbered in order, you reach box 3,000 by arithmetic: skip that many box-widths from the start, done. But if the boxes are scattered, each tied by a string to wherever the next one landed, you have no choice but to follow the string, one box at a time. The two feel about the same at ten boxes. At ten million they are nothing alike.

1945: von Neumann’s row of numbered boxes

In June 1945 the mathematician John von Neumann circulated First Draft of a Report on the EDVAC, describing a computer whose memory was one long row of numbered storage cells, each holding the same number of bits, reached by its position alone - the design every computer since has copied. Box number i sits at start + i × size: one multiply, one add, no walking the row. That row is what engineers call an array, and it’s why fetching box 3,000 costs exactly what fetching box 3 costs: O(1), whatever the pile’s size.

flowchart LR
  A["row starts at address 1000, each box 8 bytes wide"] --> B["want box i=3: address = 1000 + 3 x 8 = 1024"]
  B --> C["one multiply, one add - no walking"]

Adding to the end is free. Adding in front costs everyone.

A row has a fixed number of boxes, so it’s handed spare ones at the far end before it needs them. Drop a new item into that spare room and nothing else moves. Drop one at the front, though, and every box after it must shift one slot right - like renumbering every house on the street because one new house went in first. That shift touches all n boxes, O(n), which is why a structure that links boxes with string instead of position - Linked Lists, Stacks & Queues - exists at all.

1972: Ritchie’s one-byte decision

Words are a row of boxes too, one per letter. In 1972, at Bell Labs, Dennis Ritchie was designing the C language and had to decide how a program would know where a word of text ends: store the length in a hidden box up front, or mark the last letter’s box with a value no real letter uses, zero. Ritchie chose the zero - one byte cheaper, one edge case uglier, and it’s still how C decides where a file name stops. That only works because the boxes are addressed one at a time in a row: the same array idea, applied to letters.

Most languages you’ll actually write in made a different, later choice: once a piece of text exists, none of its boxes may be overwritten. Change one letter and the language builds a brand-new row, copies every letter across, and drops the old one. That’s called immutable, and it hides a trap: glue a hundred short pieces of text together one at a time, and each glue-step recopies everything glued so far. Ten pieces cost about 1+2+…+10 = 55 copied letters; a hundred cost 1+2+…+100 = 5,050 - nearly a hundred times the copying, not ten.

Two fingers, walking toward the middle

Take six numbers in order, [1,3,4,6,8,10], and ask which two add up to 14. Checking every pair looks at fifteen of them. The fast way puts one finger at the left end, one at the right, and reads their sum: 1+10=11, too small, so slide the left finger inward. 3+10=13, still small, slide again. 4+10=14, found - three looks instead of fifteen. The sorted order always tells you which finger is wrong, so nothing is ever rechecked. Two fingers walking toward each other and never turning back is what engineers call two pointers; between them they take at most n steps, not n².

flowchart LR
  L1["left=1 right=10: sum 11, too small"] --> L2["left=3 right=10: sum 13, too small"]
  L2 --> L3["left=4 right=10: sum 14, found"]

A window that grows and shrinks

The same trick answers a different question: what’s the longest stretch of text with no repeated letter? Checking every stretch is a loop inside a loop. The fast way keeps a sliding window, a left edge and a right edge, moving only forward: push the right edge on one letter at a time, and the moment a repeat lands inside the window, pull the left edge forward until it’s gone. Each edge moves at most n times over the whole pass, so the search costs O(n) for the same reason two pointers did - nothing gets looked at twice.

Asking about a range, over and over

One more shortcut: what’s the total of everything between box 12 and box 900, asked a thousand times over the same row? Re-adding the range each time costs O(n) per question. Instead, walk the row once, writing down the running total up to each box - after that, any range’s total is one subtraction of two running totals, O(1) per question. Engineers call that running-total row a prefix sum.

You now know

• An array is one row of same-size boxes; box i’s address is one multiply and one add, so lookup costs the same at any size.
• Text is a row of characters too. Many languages rebuild the whole row on every edit, so gluing pieces together in a loop quietly costs far more than it looks.
• Two fingers walking toward each other from opposite ends replace checking every pair with one pass.
• Running totals turn “add up this range” into one subtraction, after a single walk down the row.

Stop here if you want. What follows is the same row of boxes, in numbers, timed from 1,000 to 1,000,000 items.

Second read: the row of boxes, measured

The array and the dynamic array

Element i lives at base + i × size - the multiply-and-add from the story, hence O(1) random access. Neighbours being physically adjacent also makes iteration cache-friendly (the The Memory Hierarchy (cache, locality, the memory wall) payoff).

A dynamic array (Python list, Go slice, C++ vector, Java ArrayList) is a static array with a capacity that doubles when full, copying everything over - so append is amortized O(1) (per Complexity & Big-O). The operation-cost table:

index / update        O(1)      pure arithmetic
append (end)          O(1)*     amortized; * = occasional O(n) doubling
insert / delete mid   O(n)      must SHIFT everything after it
insert / delete front O(n)      shift ALL of it
search (unsorted)     O(n)      linear scan
search (sorted)       O(log n)  binary search

Arrays are superb for indexing, iteration, and end-append; poor for insertion/deletion anywhere but the end - that O(n) shift is why linked lists and deques exist (Linked Lists, Stacks & Queues).

Measured: ten thousand inserts into an array already holding n items, once at the end (push) and once at the front (unshift), node v22:

Push doesn’t care how big the array is: each write lands in spare capacity. Unshift moves all n items one slot right every time: at a million items, ten thousand calls move 10^10 items, 1.6 s - memmove running flat out. That’s the O(n) behind “use a deque for a queue.”

Strings are arrays of characters

A string is an array of characters - bytes or code points (Complexity & Big-O: ASCII = 1 byte, UTF-8 = 1–4). The trap, as the story said, is immutability: in Python, Java, and JS every edit makes a new string, so building one with += in a loop is a classic O(n²) bug - each += copies the entire string so far:

s = ''
for p in parts: s += p        # each += copies all of s → O(n²)

s = ''.join(parts)            # collect then join once → O(n)

Fix: accumulate in a list and join once. Other staples: substring search (naive O(n·m) vs KMP O(n+m)), anagrams, palindromes, frequency maps (hashing, Hashing).

Measured in Python 3.12, building a string of n one-character pieces with s = s + p against one join:

Ten times the pieces, a hundred times the time: 1.1 ms to 109 ms. The k-th concatenation copies k characters, so n of them copy 1 + 2 + ... + n = n(n+1)/2 characters - five billion at n = 100,000, where the 109 ms went. The proof: write the series forwards and backwards and add them, n pairs each summing to n+1, so the total is n(n+1)/2 - the same formula behind the nested loop’s pair count below. join copies each character once, 500× faster at that size. One caveat: JavaScript flattens concatenations lazily (a rope of pieces), so the same loop in node was only 3× slower than join, not a hundred - the model is what matters, not the runtime.

Two-pointer, measured

Reach for it when you see a sorted array, a palindrome, pairs/triplets summing to a target, or in-place compaction. The other shape is same-direction (fast/slow): one pointer scouts ahead, the other marks a write position - removing duplicates, or Floyd’s tortoise & hare cycle detection.

Two-sum on a sorted array, both ways, in the worst case (a target no pair reaches, so neither method can stop early):

The nested loop examines n(n-1)/2 pairs, fifty million at 10,000. Two pointers move L and R at most n times total; at a million it’s 1.7 ms, about the cost of one scan. (The 245 us at 10,000 briefly beating 100,000’s 218 us is JIT warm-up noise, not a reversal.)

The board’s own six numbers:

flowchart LR
    S1["L=1 R=10 sum 11 too small: L right"] --> S2["L=3 R=10 sum 13 too small: L right"]
    S2 --> S3["L=4 R=10 sum 14 found"]
    S3 -.->|if 15 instead| S4["L=6 R=10 sum 16 too big: R left"]
    S4 --> S5["L=6 R=8 sum 14 too small: L right"]
    S5 --> S6["L=8 R=8 crossed: no pair"]

Every arrow discards one element for good: too small means nothing pairs with L; too big means nothing pairs with R. Worked in full: Clinic #05 - Two Sum (unsorted, a hash map replaces the second finger), Clinic #17 - Container With Most Water and Clinic #18 - 3Sum (converging pointers), Clinic #04 - Meeting Rooms II (two sorted lists at once).

Sliding window & prefix sums, measured

Two shapes: a fixed window (size k) slides by one, add-then-drop, O(1) per step; a variable window grows R while valid and shrinks L when it breaks - longest substring without repeats, from the story, is the classic case.

Prefix sums trade space for time - the running-total row from the story, written as a formula:

prefix[k] = a[0] + … + a[k-1]
sum(i..j) = prefix[j+1] - prefix[i]     // O(1) per query after O(n) precompute

Read it as: prefix[k] is the running total of the first k items, so any range sum is one running total minus another.

Two-pointer, sliding window, and prefix sums are the three patterns that solve most array/string problems.

The variable window has exactly three states, and every window problem is the same machine with a different “valid” test:

stateDiagram-v2
    [*] --> Expand
    Expand --> Check: R moves right, add s[R]
    Check --> Record: window valid
    Record --> Expand: best = max(best, R-L+1)
    Check --> Shrink: window broken
    Shrink --> Check: L moves right, drop s[L]
    Expand --> [*]: R reached the end

R and L each only ever move right, so between them they take at most 2n steps however many times the window shrinks - the whole proof it’s O(n), and why the pattern never needs the “for every start, for every end” pair of loops. Timed, on random lowercase strings, for “longest substring without a repeated character”:

The naive column looks tame at first because each inner scan stops at the first repeat - with 26 letters that’s after ~20 characters, so it’s really O(26n) here; a million distinct code points would show the full O(n²). The window column scales ten per row, agreeing with naive at every size checked. Clinic: Clinic #06 - Longest Substring Without Repeating Characters.

Prefix sums, timed as they’re actually used: ten thousand random range-sum queries, rescanned vs. precomputed:

Rescanning costs O(n) per query: random ranges average a third of the array, so about three billion additions over a million items, 4.3 s. Prefix is dominated by the one O(n) precompute (3.6 ms at a million) and doesn’t care how long the ranges are: build it once you’ll ask more than one range query.

Which pattern a problem wants:

flowchart TD
    A[an array or string problem] --> B{asked about pairs or triplets, or sorted, or a palindrome?}
    B -->|yes| TP[two pointers, converging or fast and slow]
    B -->|no| C{asked for the best contiguous run that satisfies a condition?}
    C -->|yes| W[sliding window, fixed size or grow and shrink]
    C -->|no| D{asked many times about sums over ranges?}
    D -->|yes| P[prefix sums, one precompute]
    D -->|no| H[probably a hash map: [[0058-hashing]]]

The three diamonds fire in order of how often they’re needed. Most array problems that aren’t one of these are a hash map wearing an array costume - the next lesson.

Try it

# the string trap, measured
import time
parts = ["x"] * 200_000
t=time.perf_counter(); s=""
for p in parts: s += p
print("+= loop", time.perf_counter()-t)                # noticeably slow (O(n^2))
t=time.perf_counter(); s="".join(parts)
print("join   ", time.perf_counter()-t)                # fast (O(n))

# two-pointer two-sum on a sorted array
def two_sum(a, target):
    L, R = 0, len(a)-1
    while L < R:
        s = a[L] + a[R]
        if s == target: return (a[L], a[R])
        if s < target: L += 1
        else: R -= 1
print(two_sum([1,3,4,6,8,10], 14))                     # (4, 10)

Run here on Python 3.12: the += loop over 200,000 pieces took 358 ms and s = s + p took 341 ms, the same O(n^2) path either way, against a join in well under a millisecond.

The four tables above came from one node script, arrays.mjs; worth typing yourself:

# front insert vs end append, 10^4 operations on an array of n
node -e 'for (const n of [1e3,1e4,1e5,1e6]) { const base=Array.from({length:n},(_,i)=>i);
  let b=base.slice(), t=performance.now(); for(let k=0;k<1e4;k++) b.push(k); const tp=performance.now()-t;
  b=base.slice(); t=performance.now(); for(let k=0;k<1e4;k++) b.unshift(k); const tu=performance.now()-t;
  console.log(n, "push", tp.toFixed(1), "ms", "unshift", tu.toFixed(1), "ms"); }'

# the window, and its proof: count how many times L and R move
node -e 'const s=Array.from({length:1e6},()=>"abcdefghijklmnopqrstuvwxyz"[Math.floor(Math.random()*26)]).join("");
  const last=new Map(); let L=0,best=0,moves=0; for(let R=0;R<s.length;R++){ moves++;
  if(last.has(s[R])&&last.get(s[R])>=L){ moves+=last.get(s[R])+1-L; L=last.get(s[R])+1; } last.set(s[R],R); best=Math.max(best,R-L+1); }
  console.log("longest", best, "pointer moves", moves, "<= 2n =", 2*s.length)'

# prefix sums: 10^4 range queries over 10^6 numbers, rescanning vs one precompute
node -e 'const n=1e6, a=Array.from({length:n},()=>Math.floor(Math.random()*100));
  const qs=Array.from({length:1e4},()=>{const i=Math.floor(Math.random()*n),j=Math.floor(Math.random()*n);return [Math.min(i,j),Math.max(i,j)];});
  let t=performance.now(), x=0; for(const [i,j] of qs){let s=0; for(let k=i;k<=j;k++) s+=a[k]; x+=s;} console.log("rescan", (performance.now()-t).toFixed(0), "ms");
  t=performance.now(); const p=new Float64Array(n+1); for(let k=0;k<n;k++) p[k+1]=p[k]+a[k]; let y=0; for(const [i,j] of qs) y+=p[j+1]-p[i]; console.log("prefix", (performance.now()-t).toFixed(1), "ms", "same:", x===y)'

The middle one prints the proof as a number: for a million random letters it reported longest 21 pointer moves 1999991 <= 2n = 2000000. With only 26 letters, the window shrinks almost every step, so the pointers use nearly the whole 2n budget; fewer repeats keeps moves closer to n. Either way, L never moves left.

Go deeper

• Python list internals (over-allocation)
• Go slices: usage and internals
• neetcode.io - arrays & two-pointer/sliding-window patterns
• CLRS ch. 10 (elementary structures)
• KMP substring search explained.

Related

• Foundations #03 - Arrays, Do-Pointer & Sliding Window - the Hinglish twin: one array, four walks
• Clinic #05 - Two Sum - two-sum unsorted, where a hash map plays the second finger
• Clinic #17 - Container With Most Water and Clinic #18 - 3Sum - converging pointers, worked in full
• Clinic #04 - Meeting Rooms II - two pointers over two sorted lists at once
• Clinic #06 - Longest Substring Without Repeating Characters - the window, line by line
• Complexity & Big-O - why the tables above go up by ten per row or a hundred
• Foundations #01 - Complexity (Big-O ka poora naksha) - the “touched once” way of seeing every O(n) pattern here
• The Memory Hierarchy (cache, locality, the memory wall) - why contiguous slots are the fast kind of memory
• Linked Lists, Stacks & Queues - what replaces the array when front-insertion is the common case
• The full DSA list is in CURRICULUM.

Retrieval practice

9 questions. Answer each one before you open it.