Chapter 2 — Arrays

You have used arrays every day since you started programming. You have mapped over them, filtered them, pushed into them, and spread them. But you have almost certainly never asked what one actually is — not the JavaScript [], but the thing underneath it that makes it work. That gap is about to close. By the end of this chapter you will understand why reading from an array is instant, why inserting into the middle is slow, why JavaScript's array is a lie in the best possible sense, and how every array problem in every interview collapses into a small set of physical realities that you can reason about from scratch. Arrays are the foundation every other data structure is either built on or built against. You need to know this cold.

Part 1: What an Array Actually Is

Your computer has RAM — Random Access Memory. Think of it as an enormously long row of numbered storage boxes, each box holding exactly one byte (8 bits). Every box has an address: 0, 1, 2, 3, ... all the way up to however much RAM you have.

When you create a variable in any programming language, the language runtime asks the operating system: "Give me some boxes." The OS hands back an address — the number of the first box — and the runtime stores your data starting there.

An array is the simplest possible use of this system: you ask for n boxes in a row, all adjacent, all yours.

If you create an array of 4 integers and the OS gives you starting address 1000, your memory looks like this (assuming each integer takes 4 bytes):

Address:  1000  1001  1002  1003  1004  1005  1006  1007  1008  1009  1010  1011  1012  ...
Content:  [  element 0  ] [  element 1  ] [  element 2  ] [  element 3  ] [  unused ...
           arr[0]          arr[1]          arr[2]          arr[3]

The critical word is adjacent. All four elements are sitting next to each other in memory, with no gaps between them. This contiguity is not an accident — it is the defining property of an array, and everything interesting about arrays flows from it.

Part 2: Why Reading From an Array is O(1)

You write arr[2] and expect to get the third element. How does the computer find it?

It does not search. It calculates.

The computer knows three things:

1. The starting address of the array (call it base — stored when the array was allocated)
2. The index you asked for (call it i — in this case, 2)
3. The size of each element in bytes (call it elementSize — for a 32-bit integer, this is 4 bytes)

From these three numbers, it computes the exact address of element i:

address of arr[i] = base + (i × elementSize)

For our example: address of arr[2] = 1000 + (2 × 4) = 1008.

The CPU jumps directly to address 1008 and reads the value there. One arithmetic calculation. One memory read. Done.

This works for arr[0], arr[99], or arr[999999] — the calculation is the same. Three numbers multiplied and added. That is why array access is O(1): it is not a search. It is arithmetic.

This is the feature that makes arrays foundational. O(1) access means you can jump to any position instantly, regardless of the size of the array. No other data structure in this book gives you this for free without strings attached.

One assumption hiding here: This calculation works only because all elements are the same size. If element 0 took 4 bytes and element 1 took 7 bytes, the formula base + (i × elementSize) would not work — there is no single elementSize to use.

In lower-level languages (C, C++), arrays enforce this: every element must be the same type, and therefore the same size. In JavaScript, arr[0] could be a number and arr[1] could be a string — they are different sizes. So how does JavaScript maintain O(1) access?

It cheats slightly, in a clever way. Instead of storing the values directly in the contiguous block, JavaScript stores pointers (memory addresses) in the contiguous block, one pointer per element, and each pointer points to the actual value somewhere else in memory. Every pointer is the same size (8 bytes on a 64-bit system), so the formula works. This is called boxing: the value is "boxed" into a heap-allocated object, and the array stores a reference to the box.

The consequence: on mixed-type JavaScript arrays, you technically do two memory accesses per element read — one to find the pointer, one to read the value the pointer points to. V8 is smart enough to optimize this away when it detects that all elements in the array are the same type (all numbers, all objects), reverting to direct storage. This optimization is one reason "typed arrays" (like Int32Array) are faster than regular arrays for numeric computation — they force the same-type constraint and allow direct storage.

For your purposes in interviews: JavaScript array access is O(1). The underlying mechanics described above explain why, and they explain why the optimization is possible.

Part 3: Why Searching an Unsorted Array is O(n)

You have the array and you want to find whether the number 42 is in it. You cannot use the address formula because that requires knowing where 42 is, which is exactly what you are trying to find.

You have no choice but to start at index 0 and check each element in turn until you either find 42 or exhaust the array.

function find(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i;
  }
  return -1;
}

In the worst case (the target is not there, or is the last element), you check all n elements. O(n).

This is not a failure of cleverness. It is a physical constraint. The elements could be in any order. There is no structural information you can exploit to narrow the search without looking. You are blind until you look.

The important question: Is there anything you can add to an array — or any additional structure you can build around it — that would let you find elements faster than O(n)?

Yes. Two things:

1. Sort the array. A sorted array has structural information: if arr[5] > target, you know the target cannot be anywhere to the right of index 5. This lets you use binary search — O(log n). We will build this precisely in Chapter 9.

2. Build an index alongside it. A HashMap (Chapter 3) maps values to their positions, giving O(1) lookup. You trade O(n) space for O(1) time.

Both of these are answers to Question 4: "Where is the waste?" The waste in linear search is looking at elements you do not need to look at. Sorting or indexing eliminates that waste.

Part 4: Why Inserting Into the Middle is O(n)

This is the operation that surprises most developers who have not thought about memory.

You have an array of 5 elements at addresses 1000–1019 (4 bytes each):

[10, 20, 30, 40, 50]
 ↑                ↑
addr 1000       addr 1016

You want to insert the value 25 between index 1 (value 20) and index 2 (value 30).

You might think: just write 25 into the address after 20. But what is at that address? The value 30. If you write 25 there, you overwrite 30. It is gone.

You need to make room. The only way to make room in a contiguous block of memory is to shift every element after the insertion point one position to the right.

Here is the sequence:

1. 50 moves from index 4 to index 5 (but wait — index 5 does not exist yet, the array only has 5 slots. So either you had extra capacity, or you need to resize first. Let's assume extra capacity for now.)
2. 40 moves from index 3 to index 4.
3. 30 moves from index 2 to index 3.
4. Now index 2 is free. Write 25 there.

Before: [10, 20, 30, 40, 50, __ ]
                 ↑ insert here
Step 1: [10, 20, 30, 40, 50, 50]  ← copy 50 rightward
Step 2: [10, 20, 30, 40, 40, 50]  ← copy 40 rightward
Step 3: [10, 20, 30, 30, 40, 50]  ← copy 30 rightward
Step 4: [10, 20, 25, 30, 40, 50]  ← write 25 into freed slot

Three elements were shifted. If we were inserting at index 0 — the very front — we would have to shift all n elements. That is O(n).

Insertion at the end (push) requires no shifting at all — just write to the next available slot. O(1) amortized (the resize cost is amortized, as we derived in Chapter 1).

Insertion at position i requires shifting n - i elements. In the worst case (i = 0), that is n shifts. O(n).

Deletion follows the same logic. Removing an element from the middle leaves a gap. To maintain contiguity (which is required for the O(1) access formula to work), you must shift every element after the deletion point one position left. Also O(n) in the worst case.

Before: [10, 20, 25, 30, 40, 50]
                 ↑ delete index 2 (value 25)
Step 1: [10, 20, 30, 30, 40, 50]  ← copy 30 leftward
Step 2: [10, 20, 30, 40, 40, 50]  ← copy 40 leftward
Step 3: [10, 20, 30, 40, 50, 50]  ← copy 50 leftward
Result: [10, 20, 30, 40, 50]      ← length decremented, last slot ignored

This is the fundamental tension of arrays: O(1) access, O(n) insertion/deletion in the middle. Every other data structure in this book is either an attempt to get better insertion/deletion (at the cost of O(1) access), or a structure that adds a layer on top of arrays to give you better search.

Here is the full complexity picture for array operations:

Part 5: JavaScript's Array is a Lie (The Best Kind)

When you write const arr = [] in JavaScript, you are not creating a fixed-size contiguous block of memory. You are creating a dynamic, resizable, type-flexible object that behaves like an array but is managed by V8 in a more sophisticated way.

Here is the truth about JavaScript arrays:

V8 uses different internal representations depending on how you use the array. It switches between them automatically, usually invisibly.

Representation 1: FAST_SMI_ELEMENTS

If you create an array of small integers (arr = [1, 2, 3, 4]), V8 stores them as a genuine contiguous C++ array of 32-bit integers. This is as close to a "real" array as you get in JavaScript. Access is O(1) with no indirection. Push amortizes as we described.

Representation 2: FAST_DOUBLE_ELEMENTS

If your array contains floating-point numbers, V8 stores them as a contiguous array of 64-bit doubles. Still a true contiguous block, still O(1) access.

Representation 3: FAST_ELEMENTS

If your array mixes types, or contains objects/strings, V8 stores an array of pointers, where each pointer points to a heap-allocated value. Still contiguous in terms of the pointer array, still O(1) access per pointer lookup, but now each access is two memory operations: read the pointer from the array, then read the value the pointer references.

Representation 4: DICTIONARY_ELEMENTS

If your array becomes sparse — meaning you do something like arr[10000] = 5 on an otherwise empty array — V8 refuses to allocate 10,001 slots of memory for a 1-element array. Instead it switches to a hash map representation. Access is now O(1) average (hash map lookup) but with higher constant cost. Iteration is also different because the hash map does not preserve order the same way.

Why does this matter to you?

Because V8's array representation affects performance in ways that Big O notation alone does not capture. Consider:

// Creates a FAST_SMI_ELEMENTS array — fastest possible
const arr1 = [1, 2, 3, 4, 5];

// Adding a string causes demotion to FAST_ELEMENTS — two memory accesses per read
arr1.push("hello");

// Creates a DICTIONARY_ELEMENTS array despite only having 1 element
const arr2 = [];
arr2[10000] = 5;

Both arr1 and arr2 report arr[i] as O(1) — and they both are — but their constant factors differ significantly. In a tight performance loop, this matters. In interviews, you just need to know that JavaScript arrays are dynamic and V8 manages the representation for you.

The length property is not a count of elements. It is one more than the highest index ever assigned. arr2 above has arr2.length === 10001 even though it has one element. This trips up many developers when they iterate expecting length to mean "number of items."

Part 6: The Most Important Array Patterns

Certain techniques show up again and again in array problems. Not as patterns to memorize, but as logical responses to physical constraints. Understand the constraint and the technique follows naturally.

The Running Total (Prefix Sum)

Problem: you have an array of numbers and you need to answer many queries of the form "what is the sum of elements from index i to index j?"

Brute force: for each query, loop from i to j and sum. O(n) per query.

If you have 1,000 queries and n = 100,000, that is 100,000,000 operations. Too slow.

The waste: for each query, you are recomputing sums that overlap with previous queries. The sum from index 3 to 7 and the sum from index 3 to 9 share the elements at indices 3-7. You are computing those elements twice.

The fix: compute a prefix sum array once, upfront.

prefix[i] stores the sum of all elements from index 0 to index i-1.

function buildPrefix(arr) {
  const prefix = new Array(arr.length + 1).fill(0);
  for (let i = 0; i < arr.length; i++) {
    prefix[i + 1] = prefix[i] + arr[i];
  }
  return prefix;
}

function rangeSum(prefix, i, j) {
  return prefix[j + 1] - prefix[i];
}

Now each query is O(1): just subtract two numbers. Building the prefix array costs O(n) once.

Let's dry run this on arr = [3, 1, 4, 1, 5, 9]:

i=0: prefix[1] = prefix[0] + arr[0] = 0 + 3 = 3
i=1: prefix[2] = prefix[1] + arr[1] = 3 + 1 = 4
i=2: prefix[3] = prefix[2] + arr[2] = 4 + 4 = 8
i=3: prefix[4] = prefix[3] + arr[3] = 8 + 1 = 9
i=4: prefix[5] = prefix[4] + arr[4] = 9 + 5 = 14
i=5: prefix[6] = prefix[5] + arr[5] = 14 + 9 = 23

prefix = [0, 3, 4, 8, 9, 14, 23]

Query: sum from index 2 to index 4 (elements 4, 1, 5)?

prefix[5] - prefix[2] = 14 - 4 = 10. Correct: 4 + 1 + 5 = 10.

Why does the subtraction work? prefix[j+1] is the sum of all elements from index 0 to j. prefix[i] is the sum of all elements from index 0 to i-1. Their difference is exactly the sum from i to j. The elements before index i cancel out.

Where does this live in your own work? AttemptIQ computes per-subject accuracy across a user's attempt history. If you need to compute "accuracy over the last 30 attempts" vs "accuracy over the last 100 attempts", prefix sums on attempt results (1 for correct, 0 for incorrect) let you answer any range query in O(1) after a one-time O(n) build. Without this, each dashboard load recomputes from scratch.

In-Place Modification

Some problems ask you to modify an array without allocating additional space. The words "in-place" or "O(1) extra space" are the signal.

The technique usually involves maintaining two pointers — one that reads and one that writes — which we will build out fully in Chapter 5 (Two Pointers). Here is the core idea:

// Remove all zeros from arr in-place, keep relative order of non-zeros
function removeZeros(arr) {
  let writeIndex = 0;
  for (let readIndex = 0; readIndex < arr.length; readIndex++) {
    if (arr[readIndex] !== 0) {
      arr[writeIndex] = arr[readIndex];
      writeIndex++;
    }
  }
  // everything from writeIndex onward is leftover garbage
  arr.length = writeIndex;
  return arr;
}

Dry run on arr = [0, 1, 0, 3, 12]:

readIndex=0: arr[0]=0, skip. writeIndex stays 0.
readIndex=1: arr[1]=1, not zero. arr[0] = 1. writeIndex → 1.
readIndex=2: arr[2]=0, skip. writeIndex stays 1.
readIndex=3: arr[3]=3, not zero. arr[1] = 3. writeIndex → 2.
readIndex=4: arr[4]=12, not zero. arr[2] = 12. writeIndex → 3.

arr after loop: [1, 3, 12, 3, 12]  ← first 3 slots are correct
arr.length = 3 → [1, 3, 12]

The read pointer visits every element once (O(n)). The write pointer only advances when it writes. No extra array allocated. O(n) time, O(1) space.

Why this works: contiguity means we can use two indices to walk the array at different speeds. One reads all n elements; one writes only the elements that survive the filter. This "two-speed walk" eliminates the need to build a new array.

Part 7: The Four-Question Framework Applied

Let's apply the full framework to a real array problem.

Problem: Given an array of integers, move all zeros to the end while maintaining the relative order of all non-zero elements. Do this in-place.

Input:  [0, 1, 0, 3, 12]
Output: [1, 3, 12, 0, 0]

Q1: What do I have? An array of n integers, some of which are zero. The array can be modified in-place (we own it). n could be large — assume up to 10⁵.

Q2: What do I want? The same array, modified so all zeros are at the end and all non-zeros are at the front in their original relative order. No return value needed — modification is in-place.

Q3: What is the brute force? Build a new array: first collect all non-zeros in order, then append the right number of zeros.

function moveZeroesBrute(arr) {
  const nonZeros = arr.filter(x => x !== 0);
  const zeroCount = arr.length - nonZeros.length;
  return [...nonZeros, ...new Array(zeroCount).fill(0)];
}

This works. Time: O(n) for filter, O(n) for spread. Total O(n). Space: O(n) for nonZeros array.

Q4: Where is the waste? The brute force allocates a new array of size n. The problem says in-place — we are not allowed extra space. But also: even if we were allowed extra space, there is waste in building a copy when the work could be done directly on the original array.

The waste is the extra allocation. We can eliminate it with the two-pointer technique:

function moveZeroes(arr) {
  let writeIndex = 0;

  // Pass 1: write all non-zeros to front
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] !== 0) {
      arr[writeIndex] = arr[i];
      writeIndex++;
    }
  }

  // Pass 2: fill rest with zeros
  for (let i = writeIndex; i < arr.length; i++) {
    arr[i] = 0;
  }
}

Dry run on [0, 1, 0, 3, 12]:

Pass 1:
i=0: arr[0]=0. Skip. writeIndex=0.
i=1: arr[1]=1. arr[0]=1. writeIndex=1.
i=2: arr[2]=0. Skip. writeIndex=1.
i=3: arr[3]=3. arr[1]=3. writeIndex=2.
i=4: arr[4]=12. arr[2]=12. writeIndex=3.
Array after pass 1: [1, 3, 12, 3, 12]
              (first 3 correct, last 2 are stale values — don't matter)

Pass 2:
i=3: arr[3]=0.
i=4: arr[4]=0.
Array after pass 2: [1, 3, 12, 0, 0] ✓

Time: O(n) for pass 1 + O(n) for pass 2 = O(2n) = O(n). Space: O(1) — no new arrays, only two integer variables (writeIndex, i).

The brute force was O(n) time but O(n) space. The optimized version is O(n) time and O(1) space. Same time complexity, dramatically better space. This is the time-space trade-off in action: not always trading time for space — sometimes you can keep both, if you think carefully about what the algorithm actually needs.

Part 8: How to Think About This, Not Just Use It

When you see an array problem, here are the signals to read from the problem statement:

Signal: "in-place" or "O(1) extra space" This means you cannot build a new array. You must work within the existing memory. Reach for two pointers (read index and write index) running at different speeds through the array.

Signal: "sorted array" A sorted array has structure you can exploit. The elements are ordered, which means you can cut the search space in half at each step (binary search, Chapter 9) or use two pointers from both ends moving toward the center (Chapter 5). Never treat a sorted array like an unsorted one — you are throwing away free information.

Signal: "subarray" or "contiguous" When the problem talks about sums or properties of contiguous subarrays, think prefix sums or sliding window (Chapter 6). The word "contiguous" is the trigger.

Signal: "find all pairs" or "find two elements that..." Brute force is O(n²) — nested loops. This is almost always the wrong answer. The question is whether you can find the "complement" of each element in O(1) (HashMap, Chapter 3) or whether sorting creates structure you can exploit (Two Pointers, Chapter 5).

Signal: "rotate" or "reverse" These are in-place pointer manipulation problems. Think about what happens to indices when you rotate or reverse — work it out physically for a small example, then generalize.

The underlying physical reality to hold in mind: an array is fast to access by index and slow to restructure. Every technique is either exploiting the fast access or working around the slow restructuring.

Part 9: Where Arrays Live in Real Systems

PostgreSQL Table Pages

When PostgreSQL stores a table on disk, it stores it in 8KB pages. Each page is essentially an array: a contiguous block of memory containing row data, stored sequentially. When you run a sequential scan (SELECT * FROM attempts WHERE user_id = 42 with no index), PostgreSQL reads every page of the table into memory and scans the rows linearly — this is O(n) in the number of rows, for exactly the same reason that searching an unsorted array is O(n). There is no structural shortcut.

When PostgreSQL adds a B-tree index on user_id, it is adding an external structure (not changing the table array itself) that allows O(log n) lookup — finding which pages contain the target rows — before reading those specific pages. The table pages are still an array. The index is the additional structure built alongside the array to enable faster search.

The explicit parallel: table pages are the array. A sequential scan is a linear search. An index is the external structure that makes lookup faster — exactly analogous to a HashMap or sorted index on an in-memory array.

V8's Typed Arrays and Node.js Buffers

When you read a file in Node.js with fs.readFile, you get a Buffer. A Buffer is a Uint8Array under the hood — a true C-level contiguous array of bytes, allocated outside of V8's garbage-collected heap. Every byte is exactly 8 bits. Access is O(1), identical to C array access, because there is no boxing, no pointer indirection, no type flexibility.

When Node.js receives a network packet, the bytes arrive in a Buffer. When Stripe processes your payment webhook, the raw JSON arrives as a Buffer. When your ScoreResume backend reads an uploaded PDF, it comes in as a Buffer. These are all arrays at the most literal, machine-level sense of the word. Understanding what a "real" array is makes working with Buffers intuitive instead of mysterious.

Redis Lists

Redis's LIST data type is implemented as a doubly linked list for large lists, but as a ziplist (a compact, contiguous memory block — essentially an array) for small lists (fewer than 128 elements by default). Redis makes this switch automatically.

Why? Because for small lists, the O(1) access and cache friendliness of a contiguous memory block outweighs the O(n) insertion cost — small lists are rarely large enough for O(n) insertions to matter. As the list grows, Redis switches to a linked list to get O(1) insertion at either end (LPUSH/RPUSH), sacrificing O(1) access by index (LINDEX becomes O(n) on a large list).

This is a direct, production illustration of the array trade-off: Redis literally switches data structures at a threshold because the trade-off tips at that point. When you call LINDEX mylist 50 on a large Redis list and wonder why it is slow, the answer is: it is no longer backed by a contiguous block. It is now a linked list, and O(n) traversal to find index 50 is unavoidable.

JavaScript Engine JIT Compilation

When V8's JIT (Just-In-Time) compiler encounters a loop that accesses an array, it checks the array's internal representation. If the array is FAST_SMI_ELEMENTS (all small integers), the JIT can compile the loop to machine code that directly addresses memory using the formula base + (i × 4) — identical to how C arrays work. No JavaScript overhead at all.

If you then push a string into that array mid-loop, V8 "deoptimizes" — it throws away the compiled machine code and falls back to interpreted JavaScript, because the assumption it compiled against (all integers) is now violated. This is called a deoptimization bailout, and it is why mixing types in a hot array (one inside a performance-critical loop) causes measurable slowdowns.

You will never see this in an interview. You will see it when profiling a Node.js service that is underperforming. Knowing the cause makes the fix obvious: keep your arrays type-consistent in performance-critical code.

Vocabulary Map

Practice Problems

Work all five on paper. Simulate the machine. Do not run code.

Problem 1 — Trace and Predict

Here is a function that rotates an array to the right by k positions. "Rotate right by 1" means the last element moves to the front.

function rotate(arr, k) {
  k = k % arr.length;
  reverse(arr, 0, arr.length - 1);
  reverse(arr, 0, k - 1);
  reverse(arr, k, arr.length - 1);
}

function reverse(arr, left, right) {
  while (left < right) {
    let temp = arr[left];
    arr[left] = arr[right];
    arr[right] = temp;
    left++;
    right--;
  }
}

Your task:

Trace through rotate([1, 2, 3, 4, 5, 6, 7], 3) step by step. Write the state of the array after each call to reverse. Then write the final array.

After tracing: explain in plain English why this three-reversal trick works. Do not just describe the steps — explain the logical reason why reversing the whole array and then reversing two halves produces a rotation. The goal is to understand it deeply enough to reconstruct the algorithm from scratch if you forget it.

Also: why is k = k % arr.length the first line? What breaks without it? Give a concrete example.

Problem 2 — Find the Waste

Here is a function that finds the first duplicate in an array of integers (integers are in the range 1 to n, array has n+1 elements, so by the pigeonhole principle a duplicate must exist):

function findDuplicate(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] === arr[j]) return arr[i];
    }
  }
}

Part A: Derive the time and space complexity of this brute force.

Part B: Where is the waste? For each element arr[i], what is the brute force doing that is redundant?

Part C: The problem says integers are in range 1 to n and the array has n+1 elements. This is extra information that the brute force ignores entirely. How could you exploit the fact that values are in a constrained range to improve performance? Describe your improved approach, derive its complexity, and write the code in JavaScript.

Note: There is more than one way to exploit this constraint. Find at least one O(n) time solution. If you find two with different space complexities, describe both and compare the trade-off.

Problem 3 — Failure Analysis

A developer on your AttemptIQ backend writes this function to compute a user's "streak" — the number of consecutive days they have practiced, ending on today:

function computeStreak(attempts) {
  // attempts: array of Date objects, sorted oldest-first, one per day practiced
  // Returns: number of consecutive days ending today

  const today = new Date();
  today.setHours(0, 0, 0, 0);

  let streak = 0;
  for (let i = attempts.length - 1; i >= 0; i--) {
    const day = new Date(attempts[i]);
    day.setHours(0, 0, 0, 0);

    const expectedDay = new Date(today);
    expectedDay.setDate(today.getDate() - streak);

    if (day.getTime() === expectedDay.getTime()) {
      streak++;
    } else {
      break;
    }
  }

  return streak;
}

Part A: Under what inputs does this function produce a correct result?

Part B: Find at least three distinct inputs or conditions under which this function produces wrong output or behaves unexpectedly. For each, explain exactly why it fails — trace the logic and show the specific line where the wrong answer emerges.

Part C: The complexity of this function is O(n) in the worst case. Can you think of a way to make it O(1) after O(n) preprocessing? What would you precompute, and where in your system would you compute it?

Problem 4 — Design Under Constraints

You are building the "recent attempts" feed for AttemptIQ's dashboard. The dashboard shows the user's last 20 attempts in reverse chronological order (most recent first). Requirements:

• New attempts must be recorded in O(1) time
• Fetching the last 20 attempts must be O(1) time
• Memory usage must be bounded — you must not store more than 20 attempts per user in this structure (older attempts are stored in the database separately)
• You cannot use JavaScript's built-in array methods that resize (no push/pop/shift/unshift). Assume you have a fixed-size array of length 20.

Your task: Design a data structure (using only a fixed-size array of length 20 and a few integer variables) that satisfies all four constraints. This structure has a name — but do not look it up. Derive it from the constraints.

For your design:

1. Describe what variables you maintain and what they track.
2. Describe the algorithm for recording a new attempt.
3. Describe the algorithm for fetching the last 20 attempts in order.
4. Prove that both operations are O(1).
5. Trace through recording 25 attempts one by one, showing the state of your array and variables after attempt 18, 19, 20, 21, 22, and 25.

Hint: The constraint "cannot resize" combined with "must overwrite oldest" should suggest that old data and new data can coexist in the same array if you are clever about which index you write to next.

Problem 5 — Reach Beyond

This problem connects Chapter 2 to Chapter 1's amortized analysis.

You are implementing a stack (a data structure that supports push and pop, where pop always removes the most recently pushed element — last in, first out). You decide to implement it using a JavaScript array with a fixed maximum size, resizing when needed.

class Stack {
  constructor() {
    this.data = new Array(4);  // start with capacity 4
    this.size = 0;
  }

  push(val) {
    if (this.size === this.data.length) {
      // resize: double the capacity
      const newData = new Array(this.data.length * 2);
      for (let i = 0; i < this.size; i++) {
        newData[i] = this.data[i];
      }
      this.data = newData;
    }
    this.data[this.size] = val;
    this.size++;
  }

  pop() {
    if (this.size === 0) return undefined;
    const val = this.data[this.size - 1];
    this.size--;
    return val;
  }
}

Part A: What is the worst-case time complexity of a single push call? What triggers this worst case?

Part B: Using the amortized analysis technique from Chapter 1, prove that the amortized cost per push is O(1). Show the arithmetic — do not just claim it.

Part C: This stack shrinks when you pop elements, but the backing array never shrinks. If someone pushes 1,000,000 elements and then pops 999,999 of them, the backing array still holds 1,000,000+ slots. What is the space complexity of the stack after these operations? Is this a problem in practice?

Part D (reach): Modify the design so that the backing array shrinks when it is less than 25% full. Specifically, when this.size < this.data.length / 4, halve the capacity. Prove that this shrinking strategy still gives O(1) amortized push and pop. Then explain why shrinking at 50% full (rather than 25%) would be dangerous — what sequence of operations would cause O(n) work on every operation?

(Part D requires you to reason about something not explicitly taught. Think carefully about what happens when size hovers at exactly the resize threshold.)

What's Coming Next

Arrays give you O(1) access by index but O(n) search by value. Every search you do — checking whether a username exists, whether a session token is valid, whether a question has been answered — requires scanning the entire array if the data is unsorted. Chapter 3 introduces the data structure that fixes this: the HashMap. A HashMap is, at its core, a clever use of an array combined with a mathematical function that turns any key into an index. It gives you O(1) search by value instead of O(1) access by index. Understanding arrays first means you will understand exactly what the HashMap is doing underneath — and why it is not magic, just arithmetic applied cleverly.