Array Complete Guide

Data Structure • easy

Arrays are contiguous memory blocks where every element has an index. That direct index access is why arrays are the baseline building block for most other structures.

They are used when you need predictable iteration speed, compact memory layout, and simple serialization across APIs, files, and databases.

Most array interview questions are really about how you traverse: one pass, two passes, two pointers, or sorting first.

Typical Complexity Baseline

Metric	Value
Read by index	`O(1)`
insert/delete in middle	`O(n)`

See It

Concept Diagram

A small animated SVG that illustrates the core idea the moving parts you need to keep in your head when you read the rest of the guide.

Array random access by index

Boxes are contiguous memory cells. The highlight slides over them in O(1) time per access.

Step 1/8Array of 8 ints in contiguous memory. Each cell is the same size.

Speed

Watch First

Video Explainer

A quick visual walkthrough before the detailed sections pick the format that helps you learn fastest.

An Overview of Arrays and Memory (Data Structures & Algorithms #2)

Channel: CS Dojo

Watch on YouTube →

Mechanics

Core Concepts

The building blocks and terminology you need before everything else clicks. Skim or deep-read.

Index

What it is Zero-based position used for O(1) access.

Why it matters Index is a required building block for understanding how Array stays correct and performant on large inputs.

Capacity

What it is Allocated slots; dynamic arrays grow capacity when full.

Why it matters Capacity is a required building block for understanding how Array stays correct and performant on large inputs.

Length

What it is Current number of valid items.

Why it matters Length is a required building block for understanding how Array stays correct and performant on large inputs.

Contiguous memory

What it is Items are stored in adjacent memory, enabling fast scans.

Why it matters Contiguous memory is a required building block for understanding how Array stays correct and performant on large inputs.

Resize strategy

What it is Most dynamic arrays grow geometrically to amortize append cost.

Why it matters Resize strategy is a required building block for understanding how Array stays correct and performant on large inputs.

Random Access

What it is Reading element i directly without scanning previous elements.

Why it matters Reading element i directly without scanning previous elements. In Array, this definition helps you reason about correctness and complexity when inputs scale.

Amortized O(1)

What it is Average append cost remains constant over many pushes despite occasional resize.

Why it matters Average append cost remains constant over many pushes despite occasional resize. In Array, this definition helps you reason about correctness and complexity when inputs scale.

In-place

What it is Algorithm updates the same array rather than allocating a second structure.

Why it matters Algorithm updates the same array rather than allocating a second structure. In Array, this definition helps you reason about correctness and complexity when inputs scale.

Stable sort

What it is Equal values keep original order after sorting.

Why it matters Equal values keep original order after sorting. In Array, this definition helps you reason about correctness and complexity when inputs scale.

Bounds check

What it is Runtime verification that index is within 0..length-1.

Why it matters Runtime verification that index is within 0..length-1. In Array, this definition helps you reason about correctness and complexity when inputs scale.

Walkthrough

Putting It All Together

Every frame of the concept diagram, laid out top-to-bottom so you can scroll through the algorithm at your own pace.

Step 1/8

Array of 8 ints in contiguous memory. Each cell is the same size.

Step 2/8

arr[0] = base + 0 × size → 3. One memory load.

Step 3/8

arr[5] = base + 5 × size → 9. Same single load random access is O(1).

Step 4/8

arr[7] = base + 7 × size → 6. Index doesn't matter every access is one hop.

Step 5/8

arr[2] = 4. Compare with sequential search of a linked list that would walk 3 nodes.

Step 6/8

arr[4] = 5.

Step 7/8

arr[1] = 1. Cache locality is excellent: neighbors are pre-fetched.

Step 8/8

arr[6] = 2. Insert/delete in the middle is O(n) (shift everything), but lookup stays O(1).

Tradeoffs

How It Compares

When this technique wins, when it loses, and what to reach for instead.

vs. Linked List

Choose this when Choose arrays when reads by position dominate.

Tradeoff Middle inserts/deletes are expensive because values shift.

vs. Hash Map

Choose this when Choose arrays when order and numeric indexing matter.

Tradeoff Lookup by arbitrary key is slower than hash map lookup.

vs. Heap / Priority Queue

Choose this when Choose arrays for full scans and vectorized operations.

Tradeoff Arrays do not maintain priority ordering automatically.

In Production

Real-World Stories

Where this shows up at real companies and what the on-call engineer learned the hard way.

Snowflake

Columnar analytics engines organize values in array-like vectors for scan-heavy SQL execution.

Takeaway Contiguous layouts reduce CPU cache misses during huge table scans.

Stripe

Event batching systems often collect records in arrays before validation and persistence.

Takeaway Simple contiguous batches are easier to serialize and replay safely.

Code

Implementation

A clean reference implementation in TypeScript, Python, and Go. Switch languages with the toggle.

Classic pattern for pair-sum style problems after sorting or when input is already sorted.

Complexity: Time O(n), Space O(1)

Two-pointer pair search in sorted array

Language

function hasPairWithSum(values: number[], target: number): boolean {
  let leftIndex = 0
  let rightIndex = values.length - 1

  while (leftIndex < rightIndex) {
    const currentSum = values[leftIndex] + values[rightIndex]
    if (currentSum === target) return true
    if (currentSum < target) leftIndex += 1
    else rightIndex -= 1
  }

  return false
}

Watch Out

Common Problems and Failure Modes

The bugs and edge cases that bite engineers most often. Skim before you ship.

Forgetting off-by-one boundaries when using left/right pointers.
Mutating input arrays when the caller expects immutability.
Sorting unnecessarily when one linear pass is enough.
Ignoring worst-case memory blowups from repeated copying.
Using nested loops when a map + one pass can reduce complexity.

Pro Tips

Tips and Tricks

Small habits that pay off every time you reach for this pattern.

When an array task looks O(n^2), check if one extra map can reduce it to O(n).
Sort once when it unlocks two-pointer logic; the one-time O(n log n) cost often simplifies everything.
Write loop invariants in plain language: what is true before and after each iteration?
For index math, test tiny cases first (length 0, 1, 2) to catch off-by-one errors quickly.

Pattern Recognition

When to Use

Concrete signals that tell you this is the right pattern both at work and on LeetCode.

Real-system usage signals

Fast random access by index for UI lists, analytics batches, and tabular payloads.
CPU cache-friendly scans, which matters for large data processing loops.
Simple shape that every language/runtime optimizes heavily.

LeetCode-specific tips (pattern-identification signals)

Identification signal: the prompt asks for direct index access, in-place updates, or contiguous range scans over ordered positions.
Identification signal: constraints push you toward O(n) or O(n log n) traversal over a linear collection, not graph-style modeling.
Look for language like "return indices", "subarray", "rotate", or "shift"; those usually indicate array-first reasoning.
For Array questions, start by naming the core invariant before writing code.
Use the constraint section to set time/space target first, then pick the data structure/algorithm.
Solve one tiny example by hand and map each transition to your variables before implementing.
Run adversarial cases: empty input, duplicates, max-size input, and sorted/reverse patterns when relevant.
During interviews, explain why your approach is the right pattern for this prompt, not just why the code works.

Practice

LeetCode Progression

A curated easy-to-hard problem ladder. Each one reinforces a specific aspect of the pattern.

#	Problem	Difficulty	Typical Complexity
1	Two Sum	Easy	`O(n)`
2	Best Time to Buy and Sell Stock	Easy	`O(n)`
3	Move Zeroes	Easy	`O(n)`
4	Product of Array Except Self	Medium	`O(n)`
5	Maximum Subarray	Medium	`O(n)`
6	Merge Intervals	Medium	`O(n log n)`
7	Set Matrix Zeroes	Medium	`O(m*n)`
8	Trapping Rain Water	Hard	`O(n)`
9	First Missing Positive	Hard	`O(n)`
10	Median of Two Sorted Arrays	Hard	`O(log(min(m,n)))`