204: Arrays, Dynamic Arrays, Strings, Matrices, and Memory Locality

Learning outcomes

By the end of this lesson, you can:

explain and apply indexed access in a realistic implementation;
explain and apply dynamic resizing in a realistic implementation;
explain and apply strings in a realistic implementation;
explain and apply matrices in a realistic implementation;
explain and apply in-place versus copying in a realistic implementation.

These outcomes are deliberately practical. The goal is not just to recognize the names of common data structures. You should be able to choose one, state the assumptions behind that choice, and explain what happens at the boundaries when the input is empty, malformed, unusually large, or subject to a mutation constraint.

Prerequisites and retrieval

This lesson assumes the earlier 01–06 foundation and the preceding lessons in this module. Before reading, retrieve one concrete example from a previous project where you had to choose between direct indexing and a more general lookup, grow a collection, process text, traverse a grid, or decide whether to mutate an input. The example does not need to have used these terms explicitly. Recalling the observed behavior is enough.

The reason for that retrieval step is that these structures are most useful when they support a decision. In an interview-sized problem, you may need to justify a time and space bound. In a production data-processing problem, you may also need to account for memory churn, malformed input, Unicode behavior, concurrency, or a contract that forbids mutation. Reason from those constraints instead of reaching for a memorized template.

Terminology

Indexed access: Array indexing is O(1) when the runtime provides direct indexed storage. That guarantee is about locating an element by its index; it does not make insertion or removal cheap.
Dynamic resizing: Dynamic arrays maintain capacity larger than length and occasionally allocate and copy during growth. The occasional expensive operation is spread over many appends, producing amortized O(1) append rather than strict O(1) on every append.
Strings: Strings are immutable in JavaScript. Operations that appear to modify a string produce a new string value or another result instead. Treat immutability as a precise engineering constraint, not merely vocabulary.
Matrices: A matrix is typically an array of rows. The representation may be rectangular or jagged, and that distinction affects what a valid traversal can assume.
In-place versus copying: Two algorithms with the same Big-O notation can differ substantially in memory churn, aliasing behavior, and whether callers observe a changed input.
Sentinel and boundary design: Many off-by-one bugs come from inconsistent inclusive and exclusive ranges. A boundary convention is part of the algorithm's contract, not a cosmetic detail.

Mental model

Treat Arrays, Dynamic Arrays, Strings, Matrices, and Memory Locality as a design problem with observable inputs, outputs, invariants, and failure modes. Arrays offer indexed, contiguous-like storage semantics and underpin many interview patterns. In JavaScript, however, the high-level array abstraction does not mean that every operation has the same cost, and language behavior such as immutable strings can add allocations that are easy to overlook.

A strong implementation makes assumptions visible. It says whether an index must be in range, whether rows must all have the same length, whether text is being handled as UTF-16 code units or as user-perceived characters, and whether the input may be mutated. It also narrows uncertainty at boundaries and leaves evidence, such as tests, types, constraints, metrics, or diagrams, that makes the design safe to review.

A useful interview and production sequence is:

requirement -> constraints -> model -> implementation -> failure analysis -> verification

Start with the requirement and constraints rather than jumping directly to a library call. Then state what must remain true while the algorithm runs. That statement is the invariant. Finally, choose the representation and mechanism that make the invariant easiest to maintain and verify.

Deep dive

1. Indexed access

The problem indexed access solves is simple: given a position, retrieve the corresponding element without scanning all earlier elements. Array indexing is O(1) when the runtime provides direct indexed storage. Inserting or removing near the front or middle of a dense dynamic array is different. Existing elements generally have to shift to close or create a gap, so that work is O(n).

This distinction matters when an algorithm repeatedly reads known positions but occasionally inserts at the front. The reads may remain constant-time while the updates dominate the total runtime. Also distinguish an array index from a key lookup in a map: both can retrieve a value, but they express different contracts and have different ordering and memory behavior.

Decision rule: Use indexed access deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. In a review, be able to state the valid index range and what the implementation does when the requested position is outside it.

2. Dynamic resizing

An array-backed collection needs two related quantities: its logical length and the capacity of the allocated storage. When the length reaches capacity, the collection allocates a larger region and copies the existing elements into it. That particular append is expensive, but a growth policy that increases capacity by a factor spreads the copying cost across subsequent appends. The resulting append cost is amortized O(1), not a promise that every individual append is O(1).

The distinction is important for latency-sensitive code. A single resize can still create a noticeable allocation and copy, and repeated growth can increase garbage-collection pressure. If the expected size is known, reserving capacity or choosing a representation that avoids repeated growth can reduce that churn. The exact growth policy is an implementation choice; the invariant is that the logical elements remain intact and ordered after growth.

Decision rule: Use dynamic resizing deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. State whether capacity is bounded, what happens when the bound is reached, and whether a resize can violate a caller's latency or memory budget.

3. Strings

Strings are immutable in JavaScript. A statement that appears to update text creates a new value rather than changing the original string in place. Repeated concatenation or slicing can therefore allocate, although engine optimizations and the actual workload affect the observed cost. Do not infer a precise allocation profile from Big-O alone.

There is also a representation boundary that causes real bugs. JavaScript strings are sequences of UTF-16 code units. Code points and user-perceived graphemes are not the same thing as code units, so an operation that treats each indexed position as a character may split a surrogate pair or mishandle a combining sequence. Interview assumptions often simplify text to an array of characters, but production text may not permit that simplification.

Decision rule: Use strings deliberately when it makes the contract or invariant easier to prove. If the operation is ASCII-only, say so. If it is user-visible text, define the Unicode assumption and test representative inputs. If many edits are required, consider a mutable buffer or an array-based process, but account for the final conversion and its space cost.

4. Matrices

A matrix is typically represented as an array of rows. If every row has the same length, a rectangular matrix gives you a predictable neighbor and column contract. If row lengths can differ, the structure is jagged and every access must respect the selected row's actual bounds. JavaScript does not automatically enforce either shape.

Traversal order also matters. In lower-level languages, visiting adjacent memory locations in storage order can improve locality. JavaScript implementations still pay for property access, bounds checks, and representation details, so do not promise a particular hardware-level result without measurement. The useful engineering rule is to choose an order that matches the representation, keep bounds explicit, and measure if the matrix is large enough for locality to matter.

Decision rule: Use matrices deliberately when it makes the contract or invariant easier to prove. Document the row and column dimensions before traversing neighbors. Decide whether empty matrices, missing rows, and jagged rows are valid, and reject or handle them consistently.

5. In-place versus copying

Two algorithms with the same Big-O can differ substantially in memory churn. An in-place algorithm reuses the input's storage, which can reduce auxiliary space, but it changes the observable state for every alias that refers to that input. A copying algorithm protects the caller's value at the cost of additional storage and copying work.

The choice is therefore part of the API contract. State whether the input may be mutated. If a transformation needs two buffers, use them only when the contract allows the space cost and when the simpler invariant is worth it. For an iterative matrix update, for example, a second buffer can prevent newly written cells from affecting later reads, while an in-place version may require careful traversal order or swaps.

Decision rule: Use in-place versus copying deliberately when it makes the contract or invariant easier to prove. Document mutation in the function contract and tests. If callers may retain references to the input, treat mutation as a behavior change rather than an internal optimization.

6. Sentinel and boundary design

Many off-by-one bugs come from mixing inclusive and exclusive ranges. Prefer half-open intervals [lo, hi): lo is included, hi is excluded, and the size is hi - lo. This convention composes cleanly when a range is split and makes an empty range possible without inventing a special endpoint.

For matrices, define the valid row and column ranges before traversing neighbors. A neighbor such as (row - 1, column) is valid only after checking both dimensions. A sentinel can simplify a loop or represent “not found,” but it must be distinguishable from a legitimate data value. If zero is a valid result, returning zero as an absence marker silently corrupts the contract.

Decision rule: Use sentinel and boundary design deliberately when it makes the contract or invariant easier to prove. Pick one endpoint convention, write it down, and test the smallest valid range, the empty range, and the first and last valid positions.

Worked example

Consider an interview-sized problem and a production data-processing problem, so the learner must reason from constraints rather than memorize a template. Start by writing the requirement in one sentence. Then list the input and output contracts and identify which of the concepts above owns each failure mode. For example, an array maximum needs a defined behavior for an empty input; a matrix traversal needs a shape contract; and a string encoder needs a Unicode contract.

The important move is separation of concerns. Parsing or validation belongs at the boundary; domain rules belong in the domain or service layer; persistence rules belong in the database or repository; and presentation rules belong in the client. Mixing those concerns can make a happy-path demo look shorter, but it makes edge cases much harder to reason about and makes failures harder to assign to the right owner.

function solve(values: readonly number[]): number {
  let answer = 0;
  // State the invariant before choosing the data structure.
  for (const value of values) {
    answer = Math.max(answer, value);
  }
  return answer;
}

The code is intentionally small, but it still has a contract that must be stated. It scans the input once, uses constant auxiliary space, and returns the largest value encountered or 0 when no value changes the initial answer. That last behavior is not a universal definition of “maximum”; it is only safe if the domain guarantees that 0 is an acceptable empty result and that the relevant values are not all negative. If those assumptions are false, the contract or implementation must change. The readonly annotation also communicates that this function is not expected to mutate the input, although it does not validate runtime callers by itself.

Walk the example with at least four cases: the normal path, an empty or missing value, a duplicate, retry, or concurrent path where relevant, and a dependency failure. For this pure function, concurrency and dependency failure may be non-applicable; say that explicitly rather than forcing irrelevant behavior into the example. For each applicable case, state which layer detects the problem and what the caller observes. This is the level of explanation expected in a senior code review or technical interview.

Production perspective

Production correctness is broader than “the code works on my machine.” Ask how the design behaves during deploys, retries, partial failure, stale clients, concurrent requests, malformed data, schema changes, and high cardinality. An array algorithm may be correct for ten values and still exhaust memory when handed an unbounded stream. A string algorithm may pass ASCII tests and corrupt user-visible text when it assumes one UTF-16 code unit equals one character.

Prefer explicit contracts, bounded resource usage, structured errors, and measurable behavior. Optimize only after you can identify the bottleneck or risk with evidence. When locality or allocation behavior is important, measure representative workloads rather than treating a theoretical constant factor as a guaranteed result.

When the topic involves an external dependency, define a timeout and cancellation strategy. When it involves persistence, define transaction and consistency expectations. When it involves user-visible state, define loading, empty, error, stale, and success states. When it involves security, assume the client can be modified and the network input is untrusted. These concerns do not replace the data-structure analysis; they define the environment in which that analysis has to hold.

Guided lab

Implement matrix rotation or spiral traversal, plus a string run-length encoder. Before coding, state the mutation policy, the Unicode assumption, and the exact auxiliary-space usage. For matrix rotation, say whether the input must be square for an in-place implementation or whether a rectangular input produces a new matrix. For spiral traversal, state the behavior for an empty matrix and jagged rows. For run-length encoding, define whether counts are based on code units, code points, or grapheme clusters.

Add empty, 1x1, rectangular, and large cases. Include inputs that make the chosen boundary convention visible, such as a single row, a single column, repeated characters, and text containing a non-ASCII character when your Unicode contract supports it.

Complete the lab with this discipline:

Write the requirement and two non-requirements.
List input, output, and error contracts before implementation.
Implement the smallest correct vertical slice.
Add at least one invalid-input test and one edge-case test.
Instrument or inspect the behavior instead of guessing.
Refactor one hidden assumption into an explicit type, constraint, function, or configuration.
Explain one alternative design and why you did not choose it.
Record a short “what would break at 10× scale?” note.

Edge cases and failure modes

Indexed access: test absence, malformed input, duplicates, ordering or concurrency where applicable, and behavior at the smallest and largest credible sizes. Include the first index, the last valid index, and an out-of-range index.
Dynamic resizing: test absence, malformed input, duplicates, ordering or concurrency where applicable, and behavior at the smallest and largest credible sizes. Exercise the transition from one capacity to the next and verify that no element is lost or reordered.
Strings: test absence, malformed input, duplicates, ordering or concurrency where applicable, and behavior at the smallest and largest credible sizes. Include empty text, repeated concatenation, and Unicode input according to the declared contract.
Matrices: test absence, malformed input, duplicates, ordering or concurrency where applicable, and behavior at the smallest and largest credible sizes. Include empty, 1x1, rectangular, and jagged inputs if jagged rows are possible, and verify every neighbor boundary.
In-place versus copying: test absence, malformed input, duplicates, ordering or concurrency where applicable, and behavior at the smallest and largest credible sizes. Verify both the returned result and whether the original input, including aliases to it, changed.

Common mistakes and debugging

Solving the example instead of the requirement: a copied pattern can be syntactically correct but architecturally wrong. Start by writing the input, output, mutation, and error contracts.
Hiding uncertainty with assertions, broad exception handlers, permissive schemas, or “temporary” any values. These can move the failure away from the boundary without making the input valid.
Testing only the happy path and therefore discovering contracts only after integration. Add empty, boundary, malformed, and scale-relevant cases while the representation is still easy to change.
Optimizing before measuring, or selecting a scalable mechanism without a scale requirement. Establish the workload and observe allocation, latency, and memory behavior before changing the algorithm.
Letting client-side behavior stand in for server-side authorization, validation, or persistence guarantees. A client can be modified and must not be treated as a security boundary.

For debugging, reproduce the smallest failing case first. Inspect the actual value, shape, aliasing relationship, or execution plan rather than the value you expected to have. Trace the boundary where the invariant first becomes false: an invalid index, a resize that failed to preserve an element, a string operation that split a code point, a jagged row, or an unexpected mutation. Then fix the owning layer instead of adding a downstream patch that hides the original contract violation.

Interview questions

What problem does Indexed access solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Dynamic resizing solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Strings solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Matrices solve, and what trade-off or failure mode would make you choose a different approach?
What problem does In-place versus copying solve, and what trade-off or failure mode would make you choose a different approach?

When answering, do more than give a definition. Name the input and mutation contract, give the expected time and auxiliary-space costs, and identify one boundary case that could invalidate the simple answer.

Checkpoint

Without notes, explain Arrays, Dynamic Arrays, Strings, Matrices, and Memory Locality to another developer in five minutes. Your explanation must include one invariant, one edge case, one production failure mode, and one alternative design. Include the distinction between logical length and capacity, the Unicode assumption for string processing, and the shape assumption for matrix processing where relevant. Then implement a small example without copying the lesson code and explain why its boundary behavior is correct.

Mastery checklist

I can define the core terms precisely.
I can choose a design from requirements instead of from habit.
I can implement and test the normal path and edge cases.
I can explain the runtime, storage, or complexity cost.
I can identify which layer owns validation, errors, and recovery.
I can compare at least two reasonable alternatives.
I can explain how the design changes at larger scale or stricter reliability.