DSAArrays

Arrays

An array is the most fundamental data structure in computer science. At its core, an array is a contiguous block of memory where every element lives right next to its neighbors. That single fact — contiguous memory — is the reason arrays power almost every other data structure and algorithm you will ever study.

What "Contiguous Memory" Actually Means

When you declare an array of integers, the operating system hands your program one uninterrupted chunk of memory. If each integer takes 4 bytes and the array starts at address 1000, element 0 is at 1000, element 1 is at 1004, element 2 is at 1008, and so on.

Index:    0     1     2     3     4
         ┌─────┬─────┬─────┬─────┬─────┐
Values:  │  7  │  2  │  9  │  4  │  1  │
         └─────┴─────┴─────┴─────┴─────┘
Address: 1000  1004  1008  1012  1016

To find any element the CPU performs one arithmetic operation: address = base + index * elementSize. This is why random access is O(1) — it does not matter if the array has 10 elements or 10 million, finding element i always takes the same amount of time.

Note
Modern CPUs exploit contiguous memory through **cache lines** (typically 64 bytes). When you read element 0, the hardware prefetches elements 1–15 into the L1 cache automatically. Sequential traversal of an array is dramatically faster in practice than the O(n) theoretical bound suggests, because nearly every access is a cache hit.
Zero-Based Indexing

Almost every mainstream language — JavaScript, Python, Java, C — uses zero-based indexing: the first element is at index 0, not 1. This is a direct consequence of the address formula above. If the first element were at index 1, computing its address would require a needless subtraction: base + (index - 1) * size. Zero-based indexing keeps the formula clean.

Zero-based indexing in JavaScript

JS
const fruits = ['apple', 'banana', 'cherry'];

console.log(fruits[0]);  // 'apple'   — first element
console.log(fruits[1]);  // 'banana'  — second element
console.log(fruits[2]);  // 'cherry'  — third element
console.log(fruits[3]);  // undefined — out of bounds

// Length is always one more than the last valid index
console.log(fruits.length);       // 3
console.log(fruits[fruits.length - 1]); // 'cherry' — last element
Declaring Arrays in JavaScript

JavaScript arrays are dynamic — they grow and shrink automatically. Under the hood, the JS engine allocates a larger buffer than needed and copies elements to a new, larger buffer when the capacity is exceeded (the amortized O(1) push strategy).

Array declaration patterns

JS
// 1. Array literal — most common
const nums = [1, 2, 3, 4, 5];

// 2. Array constructor with size pre-allocation
const zeros = new Array(5).fill(0);   // [0, 0, 0, 0, 0]

// 3. Array.from — great for ranges
const range = Array.from({ length: 5 }, (_, i) => i);  // [0, 1, 2, 3, 4]

// 4. Spread an iterable
const copy = [...nums];   // shallow copy

// 5. Typed arrays — fixed size, single numeric type, true contiguous memory
const typed = new Int32Array(5);  // [0, 0, 0, 0, 0] — backed by ArrayBuffer
Tip
Use typed arrays (Int32Array, Float64Array, etc.) when performance is critical and you know the element type. They map directly to raw memory with no boxing overhead, making tight numerical loops 2–10× faster than ordinary JS arrays.
Dynamic Arrays — How Growth Works

JavaScript hides array resizing, but understanding the mechanism matters for complexity analysis. A dynamic array maintains:

  • length — the number of elements currently stored

  • capacity — the total slots allocated in the underlying buffer

When length === capacity and you push one more element, the engine allocates a new buffer (typically 2× the current capacity), copies all existing elements, and then inserts the new one. That single push cost O(n), but it happens so rarely that amortized over n pushes the cost is O(1) per push.

Push 1:  capacity 1  → [1]
Push 2:  capacity 2  → [1, 2]
Push 3:  resize! capacity 4 → copy 2 elements → [1, 2, 3, _]
Push 4:  capacity 4  → [1, 2, 3, 4]
Push 5:  resize! capacity 8 → copy 4 elements → [1, 2, 3, 4, 5, _, _, _]
Time Complexity of Core Operations

Operation

Time

Why

Access by index

O(1)

Direct address arithmetic

Search (unsorted)

O(n)

Must scan every element

Search (sorted)

O(log n)

Binary search possible

Insert at end (push)

O(1) amortized

Append to existing buffer

Insert at beginning

O(n)

Must shift every element right

Insert at index i

O(n)

Must shift elements i..n−1 right

Delete at end (pop)

O(1)

Just decrement length

Delete at beginning

O(n)

Must shift every element left

Delete at index i

O(n)

Must shift elements i+1..n left

Memory Layout Intuition

The insertion and deletion costs arise from the contiguous-memory requirement. Every element must stay adjacent to maintain O(1) random access, so shifting is unavoidable.

Insert 99 at index 2 in [10, 20, 30, 40, 50]:

Step 1: Shift right from the end
  [10, 20, 30, 40, 50, _ ]  ← allocate or expand
  [10, 20, 30, 40, 50, 50]  ← copy index 4 → 5
  [10, 20, 30, 40, 40, 50]  ← copy index 3 → 4
  [10, 20, 30, 30, 40, 50]  ← copy index 2 → 3

Step 2: Place the new value
  [10, 20, 99, 30, 40, 50]  ✓
When to Use Arrays

Use arrays when…

Avoid arrays when…

You need O(1) random access by index

You need frequent insertions/deletions in the middle

Elements are accessed sequentially (cache-friendly)

The size is unknown and highly variable

You need cache-efficient numerical computation

You need O(1) insert/delete at the front

You are implementing other structures (heaps, hash tables)

You need to splice elements into arbitrary positions often

Common Interview Patterns

Most array interview problems reduce to a small set of patterns. Recognise the pattern first, then apply the template.

  • Two pointers — opposite or same-direction pointers walking toward each other or in tandem

  • Sliding window — a subarray of fixed or variable size that slides across the input

  • Prefix sums — precompute cumulative totals to answer range queries in O(1)

  • Frequency map — count elements with a hash map to find duplicates, modes, or pairs

  • In-place modification — overwrite the array itself, often using two indices

Classic: Find all duplicates in O(n) time, O(1) space

JS
// Given an array of integers in range [1, n], find all duplicates.
// Key insight: use the sign of nums[abs(nums[i])-1] as a visited flag.
function findDuplicates(nums) {
  const result = [];

  for (let i = 0; i < nums.length; i++) {
    const idx = Math.abs(nums[i]) - 1;   // map value to index

    if (nums[idx] < 0) {
      // Already negated → we visited this index before → duplicate
      result.push(idx + 1);
    } else {
      nums[idx] = -nums[idx];            // mark as visited
    }
  }

  return result;
}

console.log(findDuplicates([4, 3, 2, 7, 8, 2, 3, 1]));
// [2, 3]
Edge Cases to Always Consider

  • Empty array — does your algorithm handle [] without crashing?

  • Single element — loops that compare i to i+1 need length > 1

  • All elements equal — rotation, duplicates, and partition logic often breaks here

  • Negative numbers — index-as-sign tricks require positive values; adapt or use a Set

  • Integer overflow — midpoint calculation: use left + Math.floor((right - left) / 2) not (left + right) / 2

Warning
JavaScript arrays are objects. Sparse arrays (e.g. `const a = []; a[99] = 1`) have `length 100` but only one element. Iterating with `for...of` or `.forEach` skips holes, while `for (let i = 0; i < a.length; i++)` does not — be aware of this difference in interviews.
Practice Problems

  1. Two Sum (LeetCode 1) — hash map, O(n) time

  2. Best Time to Buy and Sell Stock (LeetCode 121) — one-pass min tracking

  3. Contains Duplicate (LeetCode 217) — Set or sort

  4. Product of Array Except Self (LeetCode 238) — prefix + suffix pass

  5. Maximum Subarray (LeetCode 53) — Kadane's algorithm

  6. Move Zeroes (LeetCode 283) — two-pointer in-place

  7. Find the Duplicate Number (LeetCode 287) — Floyd's cycle detection