# Arrays

> Contiguous memory, O(1) index access. The fastest structure when you know where to look.

- **Category**: Data Structures
- **Subcategory**: linear
- **Canonical URL**: https://designpattern.fyi/data_structures/arrays/

---

## Description
Clean, reusable architecture pattern.


## Use Cases
Storing a leaderboard of top 100 scores, holding pixel data for image processing, buffering bytes from a network stream, implementing a lookup table. Anywhere you iterate or index — arrays win.



## Implementation Example

```javascript
// ─── Array fundamentals ───────────────────────────────────────

const arr = [10, 20, 30, 40, 50];

// O(1) — Direct index access (base_addr + i * size)

// O(n) — Linear search (unsorted array)
const idx = arr.indexOf(30);  // 2  — scans left-to-right
const has = arr.includes(30); // true

// O(1) amortized — Push to end (dynamic resize doubles capacity)
arr.push(60);                 // [10, 20, 30, 40, 50, 60]

// O(n) — Insert at beginning (shifts all elements right)
arr.unshift(5);               // [5, 10, 20, 30, 40, 50, 60]

// O(1) — Remove from end
arr.pop();                    // [5, 10, 20, 30, 40, 50]

// O(n) — Remove from beginning (shifts all elements left)
arr.shift();                  // [10, 20, 30, 40, 50]

// O(n) — Insert/delete in middle via splice
arr.splice(2, 0, 99);         // [10, 20, 99, 30, 40, 50] — insert at index 2
arr.splice(2, 1);             // [10, 20, 30, 40, 50]      — delete at index 2

// ─── Two-pointer technique (avoid O(n²) with O(n) + array) ───

// O(n) — Reverse in-place using two pointers
function reverseInPlace(arr) {
  let lo = 0, hi = arr.length - 1;
  while (lo < hi) {
    [arr[lo], arr[hi]] = [arr[hi], arr[lo]]; // Swap
    lo++; hi--;
  }
  return arr;
}

// O(n) — Remove duplicates from sorted array in-place (O(1) extra space)
function deduplicateSorted(arr) {
  let write = 1;
  for (let read = 1; read < arr.length; read++) {
    if (arr[read] !== arr[read - 1]) arr[write++] = arr[read];
  }
  return arr.slice(0, write);
}

// ─── Sliding window (O(n) over O(n²) nested loops) ─────────────

// O(n) — Max sum subarray of length k
function maxSumSubarray(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]; // Slide: add new, remove old — O(1) per step
    maxSum = Math.max(maxSum, windowSum);
  }
  return maxSum;
}

```



## Trade-offs


### Advantages

- O(1) random access by index — unbeatable for positional reads

- Best cache performance of any data structure — sequential memory = CPU prefetch heaven

- Minimal memory overhead — just the elements, no per-node pointers

- Foundation of all other structures (stacks, queues, heaps, hash tables all use arrays internally)




### Considerations & Drawbacks

- Insert/delete at arbitrary position is O(n) — all elements after the target must shift

- Static arrays are fixed-size — overflow means manual reallocation

- Dynamic arrays (ArrayList, JS Array) double capacity on resize — O(n) occasional spikes

- Wasted capacity after deletion unless you compact — memory fragmentation over time







---
**Reference**: [Original Source](https://www.bigocheatsheet.com)