Arrays

An array is the most fundamental data structure: a block of contiguous memory holding elements of the same type, each reachable by an integer index. That contiguity is the whole story — it is why some operations are blazing fast and others are surprisingly slow.

Because element i lives at base_address + i × element_size, the computer can jump straight to any index with a single arithmetic step. No scanning, no pointers to follow.

The cost model

The trade-off is symmetrical: instant reads, expensive middle edits. Inserting or deleting anywhere but the end forces every later element to shift by one slot to stay contiguous.

Dynamic arrays (how push stays cheap)

Languages give you growable arrays — list in Python, ArrayList in Java, vector in C++. When the backing buffer fills, it allocates a bigger one (usually 2×) and copies over. That copy is O(n), but it happens rarely enough that appends are amortised O(1).

Pattern 1 — Two pointers

Two indices moving toward each other turn many O(n²) brute-force scans into a single O(n) pass with O(1) extra space.

function isPalindrome(s) {
  let l = 0, r = s.length - 1
  while (l < r) {
    if (s[l] !== s[r]) return false
    l++; r--
  }
  return true
}

Pattern 2 — Prefix sums

Precompute running totals once, then answer any range-sum query in O(1). The sum from index l to r is just prefix[r+1] − prefix[l].

function buildPrefix(arr) {
  const prefix = [0]
  for (const n of arr) prefix.push(prefix.at(-1) + n)
  return prefix
}
// sum of arr[l..r] inclusive:
//   prefix[r + 1] - prefix[l]

When to reach for an array

• You need random access by index — arrays are unbeatable.
• The data is append-mostly — amortised O(1) pushes.
• You want cache-friendly iteration — contiguous memory is prefetched efficiently.
• Avoid them for frequent inserts/deletes in the middle — reach for a linked list instead.