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