FundamentalsData structureaka static array, fixed-size array, contiguous array

Array

A fixed-size block of contiguous memory holding elements of one type, addressable by index in O(1).

▶ VisualizePattern: Binary SearchPractice (8)
Progress

Definition

An array stores n elements of the same type in one contiguous block of memory. Element i lives at address base + i * elementSize, so reading or writing any index is a single multiply-add and a memory load — O(1) regardless of n.

A static array has a fixed capacity chosen at creation. Growing it means allocating a new block and copying, which is exactly what a Dynamic Array automates. Nearly every other structure — String, Matrix (2D Array), Hash Table, Binary Heap, Adjacency Matrix — is ultimately built on arrays.

Arrays are the default container in interviews. Most "array problems" are not about the structure itself but about the algorithms that exploit index arithmetic: Binary Search, Two Pointers (Opposite Ends), Sliding Window (Variable Size), Prefix Sum, and in-place partitioning.

contiguousO(1) accessfixed sizecache friendlyindex

Intuition

A mental model before the formal terms.

Picture a row of numbered mailboxes bolted to a wall. Because every box is the same size and they sit side by side, the postal worker does not search for box 37 — they walk exactly 37 box-widths from the start. That is why indexed access is constant time.

The same physical layout is the weakness: inserting a new mailbox in the middle means unbolting and shifting every box after it one slot to the right. Deleting from the middle shifts them back. Only the end of the row is cheap to change.

How it works

  1. Allocation reserves capacity * elementSize bytes and remembers the base address.
  2. get(i) and set(i, v) compute base + i * elementSize and read/write that word. Bounds are checked in most languages (0 <= i < n).
  3. insertAt(i, v) shifts elements i..n-1 one position right (n - i moves), then writes v at i. Requires n < capacity.
  4. deleteAt(i) shifts elements i+1..n-1 one position left and decrements n.
  5. search(v) with no ordering information scans every element (Linear Search); if the array is sorted, Binary Search finds it in O(log n).

Why it works

Constant-time access follows directly from the address formula: the position of element i is a pure function of i, with no pointers to follow.

Contiguity also makes arrays cache-friendly: a sequential scan pulls 8–16 neighbouring elements into cache per line, so iterating an array of one million ints is often 10× faster than walking a Linked List of the same size even though both are "O(n)".

Shifting on insert/delete is unavoidable because the address formula assumes no gaps: element i+1 must sit exactly one slot after element i.

Operations

OperationDescriptionCost
get(i)Read the element at index i via base + i * size.O(1)
set(i, v)Overwrite the element at index i.O(1)
search(v)Scan for value v; O(log n) with binary search if sorted.O(n)
insertAt(i, v)Shift a[i..n-1] right by one and write v; needs spare capacity.O(n)
deleteAt(i)Shift a[i+1..n-1] left by one.O(n)
append(v)Write at index n if n < capacity; otherwise the array is full.O(1)
traverseVisit every element in index order; sequential memory access is cache-friendly.O(n)

Recognition

How to tell a problem wants this.

  • The input is given as a list/sequence of numbers or characters and you need indexed access (a[i], a[i-1], a[mid]).
  • The problem asks for subarrays, contiguous ranges, "in-place" modification, or O(1) extra space — all rely on index arithmetic.
  • Sorted input, or "you may sort first", signals Binary Search or Two Pointers (Opposite Ends) over an array.
“sorted array” → Binary Search“sorted array” → Two Pointers“contiguous subarray” → Sliding Window“sum of subarray” → Prefix Sum

Interactive demo

Play, step, change the input. ← → and space work too.

Showing the closely related Linear Search visualization.

2
0
5
1
8
2
12
3
16
4
23
5
38
6
56
7
72
8
91
9
1/7Search for 23 by checking every element from left to right. No ordering is assumed, so nothing can be skipped.
Being compared with targetTarget foundEliminated
PseudocodeLearn Linear Search →
1for i in 0 .. n-1:
2  if a[i] == target: return i
3return -1
Variables
target23
Complexity
best O(1)
avg O(n)
worst O(n)
space O(1)
Speed

Pseudocode

1class Array(capacity):
2  data = allocate(capacity); n = 0
3  get(i): assert 0 <= i < n; return data[i]
4  set(i, v): assert 0 <= i < n; data[i] = v
5  insertAt(i, v):
6    assert n < capacity and 0 <= i <= n
7    for j = n down to i+1: data[j] = data[j-1]
8    data[i] = v; n += 1
9  deleteAt(i):
10    for j = i to n-2: data[j] = data[j+1]
11    n -= 1
12  search(v): for i in 0..n-1: if data[i] == v return i; return -1

Implementation

1from typing import Generic, TypeVar
2 
3T = TypeVar("T")
4 
5 
6class StaticArray(Generic[T]):
7    """Fixed-capacity array with explicit shifting on insert/delete."""
8 
91 · Storage and size
10    def __init__(self, capacity: int) -> None:
11        self._data: list[T | None] = [None] * capacity  # allocated once
12        self._n = 0                                      # live elements
13        self._capacity = capacity
14 
15    def __len__(self) -> int:
16        return self._n
17 
182 · Bounds-checked access
19    def get(self, i: int) -> T:
20        if not 0 <= i < self._n:
21            raise IndexError(i)
22        return self._data[i]  # type: ignore[return-value]
23 
24    def set(self, i: int, value: T) -> None:
25        if not 0 <= i < self._n:
26            raise IndexError(i)
27        self._data[i] = value
28 
293 · Insert with right shift
30    def insert_at(self, i: int, value: T) -> None:
31        if self._n == self._capacity:
32            raise OverflowError("array is full")
33        if not 0 <= i <= self._n:
34            raise IndexError(i)
35        for j in range(self._n, i, -1):
36            self._data[j] = self._data[j - 1]
37        self._data[i] = value
38        self._n += 1
39 
40    def append(self, value: T) -> None:
41        self.insert_at(self._n, value)
42 
434 · Delete with left shift
44    def delete_at(self, i: int) -> T:
45        if not 0 <= i < self._n:
46            raise IndexError(i)
47        removed = self._data[i]
48        for j in range(i, self._n - 1):
49            self._data[j] = self._data[j + 1]
50        self._n -= 1
51        self._data[self._n] = None
52        return removed  # type: ignore[return-value]
53 
545 · Linear search
55    def search(self, value: T) -> int:
56        for i in range(self._n):
57            if self._data[i] == value:
58                return i
59        return -1
Walkthrough
  1. [None] * capacity allocates the fixed block; _n counts live elements.
  2. __len__ makes len(arr) work, following the sequence protocol.
  3. insert_at shifts right with range(self._n, i, -1), then stores the value and bumps _n.
  4. delete_at shifts left and clears the trailing slot so the object can be collected.
  5. search is what list.index does internally, except it returns -1 instead of raising ValueError.
Complexity (this implementation)
time O(1) access, O(n) insert/delete/search · space O(capacity)

A Python list of ints stores pointers to boxed objects, so it is far less cache-friendly than a C array; use array.array or NumPy for dense numeric data.

Language notes
  • Python has no fixed-size array in the core language; list is a dynamic array. array.array("i") and NumPy arrays are the compact fixed-type options.
  • list.insert(i, v) and del lst[i] do the same O(n) shifting in C.
  • Negative indices wrap around (lst[-1]), which hand-rolled structures should explicitly reject or support.
Common mistakes in this language
  • Building a 2-D grid with [[0] * n] * m — every row is the same list object.
  • Using lst.index(v) without catching ValueError when the value may be absent.
  • Assuming lst.insert(0, v) is O(1) — it shifts every element.
Language differences that matter here
  • Only C++ has a true fixed-size array (int[N], std::array); JS/TS arrays and Python lists are dynamic, so the "static" class is a teaching device there.
  • Out-of-range access: C++ operator[] is undefined behaviour, JS returns undefined, Python raises IndexError (and negative indices wrap).
  • Element storage: C++ arrays hold values contiguously; Python lists hold pointers to boxed objects; JS engines pick packed/holey representations dynamically.
  • Typed arrays (Int32Array) in JS/TS and array.array/NumPy in Python approximate C-style dense numeric arrays.

Complexity

OperationAverageWorstNote
AccessO(1)O(1)
SearchO(n)O(n)O(log n) if sorted, via binary search.
InsertO(n)O(n)O(1) at the end when capacity remains.
DeleteO(n)O(n)O(1) at the end.
UpdateO(1)O(1)
TraverseO(n)O(n)
ResizeO(n)O(n)Allocate a new block and copy.
SpaceO(n)Space is the full capacity, even when partially filled.

Advantages & disadvantages

Advantages
  • O(1) random access to any index — the basis of binary search, heaps and hash tables.
  • Best possible memory locality: contiguous storage means fast scans and low per-element overhead (no pointers).
  • Simple to reason about; supported natively in every language.
Disadvantages
  • Fixed capacity: growing requires a fresh allocation and an O(n) copy.
  • Insert or delete anywhere except the end costs O(n) shifting.
  • Unordered search is O(n); you need sorting or a Hash Map for faster lookups.
  • All elements must be the same size/type (in typed languages) and the block must be allocated contiguously, which can fail for very large n on fragmented heaps.

Use cases

  • Backing store for Dynamic Array, String, Matrix (2D Array), Binary Heap, Hash Table buckets and Adjacency Matrix.
  • Lookup tables indexed by a small integer key (counts of 26 letters, DP tables, sieve of primes).
  • Fixed-size buffers: audio frames, pixel rows, network packets.
  • Any problem solved by index arithmetic: prefix sums, two pointers, sliding windows, in-place partitioning.
Use it when
  • You know the size up front, or it never changes (DP tables, frequency counts over a fixed alphabet).
  • You need O(1) random access by integer index.
  • Throughput matters: scans, sorts and binary searches over arrays benefit from cache locality.
Avoid it when
  • Frequent inserts or deletes in the middle — each is O(n); consider a Linked List (with a pointer already in hand) or a balanced tree.
  • Unknown or highly variable size — use a Dynamic Array to avoid manual reallocation.
  • Lookups by non-integer key or sparse integer keys (e.g. user IDs up to 10^9) — use a Hash Map.

Alternatives

Dynamic ArrayLinked ListHash MapDeque
Compare: Array vs Linked List

Common mistakes

  • Off-by-one on bounds: iterating to n instead of n - 1, or insertAt(n) treated as invalid when it is the legal append position.
  • Forgetting that in-place insert/delete shifts indices of later elements — iterating forward while deleting skips elements.
  • Assuming O(1) insertion in the middle because the language hides the shifting (list.insert, splice).
  • Using (lo + hi) / 2 for a midpoint in fixed-width languages; it overflows near 2^31.
  • Confusing the array length with its capacity in languages that expose both.

Interview patterns

  • Two pointers from both ends on a sorted array (two-sum II, container with most water).
  • Overwrite in place with a slow/fast write pointer (remove duplicates, move zeroes).
  • Use the array itself as a hash by index (find duplicate via cycle, missing number by negation).
  • Prefix sums for O(1) range sums after O(n) preprocessing.
  • Cyclic rotation via three reversals in O(n) time and O(1) space.
Interview questions on this
Mock interviews

Interview problems

Two SumeasyTwo Sum II — Sorted InputeasyRemove Duplicates from Sorted ArrayeasyMove ZeroeseasySort Colors (Dutch National Flag)mediumFind the Duplicate NumbermediumProduct of Array Except SelfmediumMaximum Subarraymedium