Linear
Array Fundamentals
An array is the most fundamental data structure in computer science — a contiguous block of memory that stores elements sequentially, enabling instant access to any element by its index. Every other data structure either builds on arrays or exists to compensate for their limitations.
01
Section One · Foundation
What is Array?
An array stores elements in a single contiguous block of memory. Every element occupies the same fixed number of bytes — no gaps, no pointers in between. Because the start address and element size are both known, the CPU can jump to any element in one step using address = base + (index × element_size). This is why array access is O(1) — it doesn't matter if the array has 10 elements or 10 million.
Arrays come in two flavours:
Static Array
Fixed Size
Size is set at creation and cannot change. Memory is allocated once on the stack or heap.
- Fast — no resize overhead
- Predictable memory footprint
- Typical in C, Java
int[], C#int[]
Dynamic Array
Auto-Resize
Grows automatically when full by allocating a larger backing array and copying elements over.
- Append is O(1) amortized
- May over-allocate 1.5×–2× capacity
- Python
list, JavaArrayList, JSArray
Analogy: A row of numbered post office boxes. Every box is the same size, they sit side by side in a straight line, and each has a number painted on it. If you know the box number you want, you walk directly to it — you never check the other boxes first. Adding a box in the middle means physically shifting every box after it to make room.
Key Characteristics
Contiguous memory — no gaps, no pointers
▶
Cache-friendly & fast iteration
Index-based access via address formula
▶
O(1) read & write
All elements same type & size
▶
Address arithmetic works in one step
Insert / delete in middle shifts elements
▶
O(n) worst case
Dynamic arrays double capacity on resize
▶
O(1) amortized append
02
Section Two · Operations
Core Operations
Random Access
Reads or writes any element in O(1) time by computing its exact memory address from the base pointer and index.
Pseudocode
function access(arr, i):
if i < 0 or i >= arr.length:
throw "IndexOutOfBounds"
address = arr.base + i × element_size // O(1) arithmetic return memory[address]
O(1) holds for any index. It doesn't matter if you access index 0 or index 999,999 — the address arithmetic is one multiplication and one addition. This is the defining advantage of an array over every linked structure.
Insert at Index
Places a new element at a given position by shifting all subsequent elements one slot to the right to create space.
Pseudocode
function insert(arr, index, value):
if arr.size == arr.capacity:
resize(arr) // double capacity, copy elements // shift elements right to make room for i = arr.size down to index + 1:
arr[i] = arr[i - 1] // O(n) shifts
arr[index] = value
arr.size += 1
Append is O(1) amortized. Only insertions at the end avoid the shift. Dynamic arrays double their capacity on resize so the average cost per append is O(1) amortized, even though an individual resize takes O(n).
Delete at Index
Removes an element at a given position by shifting all subsequent elements one slot to the left to close the gap.
Pseudocode
function delete(arr, index):
removed = arr[index]
// shift elements left to close gap for i = index to arr.size - 2:
arr[i] = arr[i + 1] // O(n) shifts
arr.size -= 1 return removed
Delete from the end is O(1). If order doesn't matter, swap the target element with the last element and delete from the tail — a common O(1) trick used in heaps and game object pools.
Linear Search
Scans each element from index 0 until the target is found or the array is exhausted.
Pseudocode
function search(arr, target):
for i = 0 to arr.size - 1:
if arr[i] == target:
return i // found — best case O(1) return -1 // not found — O(n)
Sort first if you search repeatedly. A single O(n log n) sort unlocks O(log n) binary search for every subsequent query. If you search more than log n times, sorting pays for itself.
Common Mistake: Off-by-one errors. Array indices run from
0 to length - 1. Accessing arr[length] is out of bounds and causes a runtime crash. Always use i < arr.length (not i <= arr.length) in loop conditions.
03
Section Three · Visuals
Diagrams & Memory Layout
Memory Layout
Array in Memory — Contiguous cells with address formula
Operation Walkthrough — Insert at Index 2
Inserting 99 at index 2 — elements shift right to make room
Complexity Comparison
Array Operation Complexities — bar chart
04
Section Four · Code
Java Quick Reference
The most common array operations using Java's built-in ArrayList — the dynamic array you'll use in real code and interviews.
Java — ArrayList Core Operations
import java.util.*;
List<Integer> arr = new ArrayList<>(Arrays.asList(10, 20, 30, 40, 50));
// O(1) — access & update by index int val = arr.get(2); // 30
arr.set(2, 99); // [10, 20, 99, 40, 50] // O(1) amortized — append to end
arr.add(60); // [10, 20, 99, 40, 50, 60] // O(n) — insert at index (shifts right)
arr.add(1, 15); // [10, 15, 20, 99, 40, 50, 60] // O(n) — delete at index (shifts left)
arr.remove(3); // removes 99 → [10, 15, 20, 40, 50, 60] // O(n) — linear search int idx = arr.indexOf(40); // 3 boolean has = arr.contains(40); // true
Array — Full Implementation
Java — DynamicArray<T> from scratch
import java.util.Arrays;
public class DynamicArray<T> {
private Object[] data;
private int size;
private int capacity;
// ── Constructor ────────────────────────────────── public DynamicArray(int capacity) {
this.capacity = capacity;
this.data = new Object[capacity];
this.size = 0;
}
public DynamicArray() { this(10); }
// ── O(1) access ────────────────────────────────── public T get(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException();
return (T) data[index];
}
// ── O(1) write ─────────────────────────────────── public void set(int index, T value) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException();
data[index] = value;
}
// ── O(1) amortized append ───────────────────────── public void append(T value) {
if (size == capacity) resize();
data[size++] = value;
}
// ── O(n) insert at index — shift right ─────────── public void insert(int index, T value) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException();
if (size == capacity) resize();
for (int i = size; i > index; i--)
data[i] = data[i - 1];
data[index] = value;
size++;
}
// ── O(n) delete at index — shift left ──────────── public T delete(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException();
T removed = (T) data[index];
for (int i = index; i < size - 1; i++)
data[i] = data[i + 1];
data[--size] = null;
return removed;
}
// ── O(n) linear search ─────────────────────────── public int indexOf(T value) {
for (int i = 0; i < size; i++)
if (data[i].equals(value)) return i;
return -1;
}
// ── Private: double capacity ───────────────────── private void resize() {
capacity *= 2;
data = Arrays.copyOf(data, capacity);
}
public int size() { return size; }
public static void main(String[] args) {
DynamicArray<Integer> arr = new DynamicArray<>(4);
arr.append(10); arr.append(20);
arr.append(30); arr.append(40);
arr.insert(2, 99); // [10, 20, 99, 30, 40]
arr.delete(1); // [10, 99, 30, 40] System.out.println(arr.indexOf(99)); // 1
}
}
Python — Built-in list operations & patterns
# ─── 1. Basic operations via built-in list ────────────────────
arr = [10, 20, 30, 40, 50]
# O(1) access / update
val = arr[2] # 30
arr[2] = 99 # [10, 20, 99, 40, 50] # O(1) amortized append
arr.append(60) # [10, 20, 99, 40, 50, 60] # O(n) insert at index — shifts right
arr.insert(1, 15) # [10, 15, 20, 99, 40, 50, 60] # O(n) delete by index — shifts left
arr.pop(3) # removes 99 → [10, 15, 20, 40, 50, 60] # O(n) search
idx = arr.index(40) # 3 # ─── 2. Two-pointer: reverse in place ───────────────────────── def reverse(arr):
lo, hi = 0, len(arr) - 1 while lo < hi:
arr[lo], arr[hi] = arr[hi], arr[lo]
lo += 1; hi -= 1 # ─── 3. Sliding window: max sum of subarray size k ─────────── def max_sum_k(arr, k):
window = sum(arr[:k])
best = window
for i in range(k, len(arr)):
window += arr[i] - arr[i - k] # slide: add right, drop left
best = max(best, window)
return best
JavaScript — Built-in Array operations & patterns
// ─── 1. Basic operations ───────────────────────────────────── const arr = [10, 20, 30, 40, 50];
// O(1) access / update const val = arr[2]; // 30
arr[2] = 99; // [10, 20, 99, 40, 50] // O(1) amortized append
arr.push(60); // [10, 20, 99, 40, 50, 60] // O(n) insert at index 1 — splice(start, deleteCount, ...items)
arr.splice(1, 0, 15); // [10, 15, 20, 99, 40, 50, 60] // O(n) delete at index 3
arr.splice(3, 1); // removes 99 // O(n) search const idx = arr.indexOf(40); // 3 // ─── 2. Two-pointer: is palindrome? ────────────────────────── function isPalindrome(a) {
let lo = 0, hi = a.length - 1;
while (lo < hi) {
if (a[lo] !== a[hi]) return false;
lo++; hi--;
}
return true;
}
// ─── 3. Prefix sum construction ────────────────────────────── function prefixSum(arr) {
const pre = [0];
for (const x of arr)
pre.push(pre[pre.length - 1] + x);
return pre; // rangeSum(l,r) = pre[r+1] - pre[l]
}
C# — Fixed array, List<T>, and LINQ
using System;
using System.Collections.Generic;
using System.Linq;
// ─── 1. Fixed array vs dynamic List ────────────────────────── int[] fixedArr = { 10, 20, 30, 40, 50 };
var list = new List<int>(fixedArr);
// O(1) access / update int val = list[2]; // 30
list[2] = 99; // [10, 20, 99, 40, 50] // O(1) amortized append
list.Add(60); // [10, 20, 99, 40, 50, 60] // O(n) insert at index
list.Insert(1, 15); // [10, 15, 20, 99, 40, 50, 60] // O(n) delete at index
list.RemoveAt(3); // removes 99 // O(n) search int idx = list.IndexOf(40); // 3 // ─── 2. LINQ filtering ─────────────────────────────────────── int[] big = list.Where(x => x > 10).ToArray();
// ─── 3. Two Sum with Dictionary (array + hash) ────────────── static int[] TwoSum(int[] nums, int target) {
var map = new Dictionary<int, int>();
for (int i = 0; i < nums.Length; i++) {
int complement = target - nums[i];
if (map.ContainsKey(complement))
return new int[] { map[complement], i };
map[nums[i]] = i;
}
return Array.Empty<int>();
}
05
Section Five · Complexity
Time & Space Complexity
| Operation | Best Case | Average Case | Worst Case | Space |
|---|---|---|---|---|
| Access / Update by index | O(1) | O(1) | O(1) | O(1) |
| Append (dynamic array) | O(1) | O(1) amortized | O(n) on resize | O(1) |
| Insert / Delete at index | O(1) at end | O(n) | O(n) | O(1) |
| Linear Search | O(1) | O(n) | O(n) | O(1) |
Why these complexities? Access is O(1) because the memory address is computed arithmetically, not traversed. Insert and delete are O(n) because shifting elements is proportional to how many sit after the target index — inserting at index 0 shifts everything. Dynamic array resize is O(n) per event, but because capacity doubles each time, the amortized cost per append across n operations is O(1).
Space Complexity Note
An array of n elements uses exactly O(n) space for the data itself. There is zero per-element overhead — no pointers, no metadata per node. Dynamic arrays over-allocate by a constant factor (typically 1.5–2×) to amortize resize cost, so actual memory may be up to twice the logical size. Auxiliary space for all operations is O(1) since shifts happen in-place.
06
Section Six · Decision Guide
When to Use Array
Use This When
- Fast reads by position — dominant operation is index lookup; O(1) access beats every linked structure.
- Data size is known or stable — no frequent mid-sequence inserts; cache-friendly layout wins.
- Building another structure — stacks, queues, heaps, and hash tables all use arrays as their backing store.
Avoid When
- Frequent mid-list inserts/deletes — every operation shifts O(n) elements; use a linked list or deque instead.
- Size is highly unpredictable — large add/remove bursts cause repeated resize overhead; a linked list never wastes capacity.
Comparison vs Alternatives
| Structure | Access | Insert | Delete | Best For |
|---|---|---|---|---|
| Array ← this one | O(1) | O(n) | O(n) | Random access, cache performance |
| Linked List | O(n) | O(1) w/ pointer | O(1) w/ pointer | Frequent mid insertions/deletions |
| Hash Map | O(1) avg | O(1) avg | O(1) avg | Key-value lookup, no ordering needed |
07
Section Seven · Interview Practice
LeetCode Problems
Array problems in interviews almost always test one of three patterns: two pointers (converging from both ends), sliding window (a moving subarray of fixed or variable size), or prefix sums (precomputed running totals for O(1) range queries). Recognising which pattern applies is more valuable than memorising solutions.
- Easy Two Sum — Use a HashMap to store each element's index as you scan — transforms O(n²) brute force into a single O(n) pass.
- Easy Best Time to Buy and Sell Stock — Track the minimum price seen so far and the maximum profit at each index — classic one-pass O(n) greedy.
- Medium Maximum Subarray — Kadane's algorithm: maintain a running sum and reset to 0 when it goes negative — local decisions yield a global optimum.
- Medium Product of Array Except Self — Build a left-products prefix array and a right-products suffix array; multiply them — achieves O(n) with no division.
- Hard Trapping Rain Water — Two-pointer approach: water at each position is bounded by the shorter of the tallest bars to its left and right — scan from both ends.
Interview Pattern: When you see a subarray or contiguous-range problem, immediately ask: "Is a sliding window applicable?" and "Can a prefix sum make range queries O(1)?" These two techniques solve the majority of medium-hard array problems at FAANG-level interviews.