Arrays

Arrays#

Think of it like this

Imagine a row of numbered mailboxes in an apartment building. Mailbox 0 is first, mailbox 1 is next, and so on. To grab mail from box 4, you go directly to box 4 — you don't check boxes 0, 1, 2, 3 first. That direct access is what makes arrays powerful.

In memory, an array is exactly this: a contiguous block where each slot sits right next to the previous one. The CPU can jump to any element in one step using the formula:

address of element[i] = base_address + i × element_size

Memory Layout

Index:   0     1     2     3     4     5
Value: [ 12 ][ 37 ][ 55 ][ 8  ][ 91 ][ 43 ]
Addr:  1000  1004  1008  1012  1016  1020
         ↑
      base address
      (each int = 4 bytes, so step = 4)

Because elements are packed together, your CPU's cache loads nearby elements automatically. This cache locality makes array traversal blazingly fast in practice — even faster than the O(n) notation suggests.

Static vs Dynamic Arrays

When a dynamic array runs out of space, it allocates a new block (typically 2× the old size) and copies everything. This copy costs O(n) but happens rarely, so the average cost per insertion is O(1) — this is called amortized analysis.

Time Complexity

Space Complexity

• Static: O(n) — exactly n elements
• Dynamic: O(n) amortized — at most 2n slots allocated at any time

Real-World Frontend Application

Arrays power almost every list-based UI you build:

• React lists: items.map(item => <Item key={item.id} />) iterates an array in O(n)
• Virtual DOM diffing: React's reconciler compares two arrays of children (old vs new) to find which nodes changed
• Redux normalized state: entities stored as arrays with separate id-lookup maps
• Canvas pixel manipulation: ImageData.data is a flat Uint8ClampedArray of RGBA values — a huge 1D array representing a 2D image

Core Patterns to Master

Pattern 1 — Two Pointers (Opposite Ends)

Start one pointer at the left, one at the right. Move them toward each other based on a condition. Eliminates the need for nested loops in many problems.

Sorted array: [-2, 1, 3, 5, 8, 11]
              ↑L                ↑R
Target sum = 9
 
Step 1: L(-2) + R(11) = 9 ✓  → Found!

// Two Sum on a sorted array — O(n) instead of O(n²)
function twoSum(arr, target) {
  let left = 0, right = arr.length - 1;
  while (left < right) {
    const sum = arr[left] + arr[right];
    if (sum === target) return [left, right];
    if (sum < target) left++;   // need bigger sum
    else right--;               // need smaller sum
  }
  return [-1, -1];
}

Pattern 2 — Sliding Window (Fixed Size)

Keep a window of size k. Slide it one step at a time by adding the new element on the right and removing the old one on the left. Processes each element exactly once → O(n).

arr = [2, 1, 5, 1, 3, 2],  k = 3
window:  [2,1,5]→sum=8    max so far = 8
         [1,5,1]→sum=7    max so far = 8
         [5,1,3]→sum=9    max so far = 9
         [1,3,2]→sum=6    max so far = 9
Answer: 9

function maxSumWindow(arr, k) {
  let windowSum = arr.slice(0, k).reduce((a, b) => a + b, 0);
  let maxSum = windowSum;
  for (let i = k; i < arr.length; i++) {
    windowSum += arr[i] - arr[i - k]; // add new, remove old
    maxSum = Math.max(maxSum, windowSum);
  }
  return maxSum;
}

Pattern 3 — Prefix Sums

Precompute cumulative sums once in O(n), then answer any range-sum query in O(1).

arr    = [ 3,  1,  4,  1,  5,  9,  2]
prefix = [ 3,  4,  8,  9, 14, 23, 25]
          index: 0   1   2   3   4   5   6
 
Sum of arr[2..5] = prefix[5] - prefix[1] = 23 - 4 = 19
                   ✓ (4 + 1 + 5 + 9 = 19)

function buildPrefix(arr) {
  const prefix = [0]; // prefix[0] = 0 (sentinel makes range queries cleaner)
  for (const x of arr) prefix.push(prefix[prefix.length - 1] + x);
  return prefix;
}
 
function rangeSum(prefix, l, r) {
  return prefix[r + 1] - prefix[l]; // sum of arr[l..r] inclusive
}

Pattern 4 — Kadane's Algorithm (Maximum Subarray)

At each index, decide: extend the current subarray, or start fresh from here?

arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
 
At each position, curMax = max(arr[i], curMax + arr[i])
curMax:  -2  1  -2   4   3   5  6   1  5
maxSoFar: -2  1   1   4   4   5  6   6  6
Answer: 6  (subarray [4, -1, 2, 1])

function maxSubarray(nums) {
  let curMax = nums[0], maxSoFar = nums[0];
  for (let i = 1; i < nums.length; i++) {
    curMax = Math.max(nums[i], curMax + nums[i]);
    maxSoFar = Math.max(maxSoFar, curMax);
  }
  return maxSoFar;
}

Common Mistakes Beginners Make

Interview Checklist

Before coding, ask yourself:

• Is the array sorted? (enables binary search and two pointers)
• Can I use a hash map to trade space for time?
• Is a prefix sum useful? (any range query)
• Can a sliding window help? (contiguous subarray constraint)
• Do I need O(1) space? (can't use extra data structures)

Key Problems to Solve