Arrays

An array is the most basic data structure you'll use, and also the most underrated. Once you really understand *why* it's O(1) to read but O(n) to insert in the middle, half the harder data structures (hash tables, heaps, dynamic arrays, even strings) make sense — they're built on top of arrays.

What an Array Actually Is

An array is one contiguous block of memory holding equally-sized slots. That's it. The "magic" of O(1) indexing comes from a single arithmetic formula:

address(arr[i]) = base + i × element_size

Example: an int array starting at address 1000, ints are 4 bytes wide.

• arr[0] → 1000
• arr[1] → 1004
• arr[5] → 1020

There is no traversal. The CPU does one multiply and one add to reach any element. This is also why arrays are cache-friendly — sequential elements live next to each other in memory, so the CPU's prefetcher loves them. A linked list visiting the same n elements can be 5–10× slower in practice even though both are "O(n)".

Static vs Dynamic Arrays

Static	Dynamic
Size	Fixed at creation	Grows automatically
Memory	Often stack	Always heap
Resize cost	impossible	copy on overflow
Examples	C int[5], Java int[]	Python list, JS Array, Java ArrayList, C++ vector	Dynamic arrays grow by doubling: when full, allocate a 2× block, copy everything over, free the old. That single copy is O(n) — but it happens rarely enough that append averages O(1) amortised. The math: doing n appends costs ≈ n + (1 + 2 + 4 + … + n) ≈ 3n total = O(1) per append. Operations and Their Real Costs	Operation	Time	Why
---	:---:	---
Read at index	O(1)	one address calculation
Write at index	O(1)	same
Search unsorted	O(n)	must scan
Search sorted	O(log n)	binary search
Append	O(1) amortised	usually room; sometimes resize
Insert at front	O(n)	shift everything right
Insert at index k	O(n − k)	shift the tail
Delete at front	O(n)	shift everything left
Delete at end	O(1)	drop last slot

The single insight that explains every row: moving to a slot is free, making space for a new slot is not.

Beginner Mistakes to Skip

1. Off-by-one in loops. <= n - 1 and < n are the same; <= n is not. Test with n = 0, 1, 2 mentally before running. 2. Mutating while iterating forward. Removing an element shifts everything; the loop skips the next item. Iterate backwards when you need to delete in place. 3. Assuming length updates after delete arr[i] (JS). It doesn't — delete just sets the slot to undefined and leaves a "hole". Use splice. 4. Treating strings like char arrays everywhere. In JS/Java/Python they're immutable; s[i] = 'x' does not work. 5. Sharing references unintentionally. const grid = Array(n).fill([]) makes n references to the same inner array. Use Array.from({length: n}, () => []). 6. Trusting Array.indexOf for objects. It compares by reference, not value.

Intermediate: Two Pointers

Use two indices that move based on a condition. Variants:

• Opposite ends (sorted arrays): "two-sum sorted", reverse in place, palindrome check.
• Same direction at different speeds (fast/slow): remove duplicates, partition.

`js // Two-sum on a sorted array, O(n) function twoSumSorted(arr, target) { let l = 0, r = arr.length - 1; while (l < r) { const s = arr[l] + arr[r]; if (s === target) return [l, r]; if (s < target) l++; else r--; } return null; } `

The trick: at each step, one pointer must move, and you have a reason for *which* one. That's it.

Intermediate: Sliding Window

A two-pointer pattern where the window shape itself is the answer.

• Fixed size: max sum of any k-length subarray, average of last k.
• Variable size: longest substring with at most k distinct chars, smallest subarray with sum ≥ target.

Pattern: expand right, when the window violates the constraint shrink left, record the best window.

Intermediate: Prefix Sums

Precompute cumulative sums so any range query is O(1):

prefix[i] = arr[0] + arr[1] + … + arr[i] sum(l..r) = prefix[r] − prefix[l - 1]

Cost: O(n) to build, O(1) per query. The same trick generalises to 2D (prefix[i][j]) for rectangle sums in O(1). Use whenever you see "many range-sum queries over a fixed array".

Intermediate: Kadane's Algorithm

Maximum-subarray-sum in O(n):

`js let cur = arr[0], best = arr[0]; for (let i = 1; i < arr.length; i++) { cur = Math.max(arr[i], cur + arr[i]); best = Math.max(best, cur); } `

The decision at each index is local: start fresh here, or keep extending. This "decide at each step" pattern is your first taste of dynamic programming.

Advanced: Dutch National Flag (3-way Partition)

Sort an array of 0/1/2 in one pass, O(1) extra space:

`js let lo = 0, mid = 0, hi = arr.length - 1; while (mid <= hi) { if (arr[mid] === 0) [arr[lo++], arr[mid++]] = [arr[mid], arr[lo]]; else if (arr[mid] === 2) [arr[mid], arr[hi--]] = [arr[hi], arr[mid]]; else mid++; } `

Generalisation = quicksort's partition step. Once you know this one, you've understood quicksort.

Advanced: 2D Arrays — Row-Major vs Column-Major

A 2D array is just a 1D array under the hood, laid out in one of two orders:

Layout	Address formula	Where
Row-major	base + (r × cols + c) × size	C, C++, Java, Python (NumPy default)
Column-major	base + (c × rows + r) × size	Fortran, MATLAB, Julia	Why this matters in practice: iterating in the wrong order trashes the cache. In a row-major language, traversing column-by-column on a 10000×10000 matrix can be 10× slower than row-by-row. Always loop in storage order. Useful patterns: rotate 90° = transpose + reverse each row; search in row-and-column-sorted matrix in O(m+n) starting at top-right. Advanced: Across-Language Differences	C int[]	C++ vector	Java int[]	Java ArrayList	Python list	JS Array
Resizes	no	×2	no	×1.5	×~1.125	engine
Type-uniform	yes	yes	primitive	objects	mixed	mixed
Heap	usually no	yes	yes	yes	yes	yes	JS Array is *technically* a hash-map under the hood that V8 optimises into a real packed array when you behave (no holes, uniform types, no delete). When you violate those, it deopts and gets much slower silently. Advanced: When NOT to Use an Array	Situation	Better choice	Why
Frequent insert/delete at front	deque or linked list	array shift is O(n)
"Does X exist?" in a big list	hash set	O(1) vs O(n)
"How many of each value?"	hash map	O(n) vs O(n²)
Rolling min/max over a stream	monotonic deque	O(1) amortised
Top-k smallest/largest	heap	O(log n)
Range sum + point updates	Fenwick / segment tree	O(log n) per op

Knowing when to *leave* arrays is half the skill of competitive programming.

Practice Path

1. Implement reverse(arr) in place using two pointers. Verify on [], [1], [1,2], [1,2,3,4,5]. 2. Solve Two Sum (LC 1) twice: O(n²) brute force, then O(n) with a hash map. Time both. 3. Solve Maximum Subarray (LC 53) with Kadane's algorithm. Trace it on [-2,1,-3,4,-1,2,1,-5,4] by hand — answer is 6. 4. Solve Sort Colors (LC 75) using the Dutch National Flag in one pass. Then solve Merge Sorted Array (LC 88) in place from the back.