Chapter 02 — Arrays: The Foundation
Chapter 02 — Arrays: The Foundation
Hey everyone! Welcome back to Namaste DSA!
In Chapter 01 we learned how to measure code with Big-O. Now we meet the data structure you'll use more than any other: the Array. Almost every problem you'll ever solve starts with an array. Master it deeply and half your DSA battle is won.
By the end you'll know not just how to USE an array, but how it actually lives in memory — which explains why some operations are lightning fast (O(1)) and others are slow (O(n)).
What we will cover:
- How arrays are stored in memory (contiguous boxes)
- Why index access is O(1) — the address formula
- The real cost of insert, delete, and search
- Static vs Dynamic arrays (how JS arrays grow)
- Traversal and in-place patterns
- Prefix Sum — turning O(n) queries into O(1)
- Kadane's Algorithm — maximum subarray
- Interview Questions
1. How Arrays Live in Memory
An array is a row of boxes placed side by side in memory (contiguous). Each box holds one element, and every box is the same size.
┌─────────────────────────────────────────────────────────────┐ │ ARRAY IN MEMORY │ ├─────────────────────────────────────────────────────────────┤ │ │ │ Index: 0 1 2 3 4 │ │ ┌────┐ ┌────┐ ┌────┐ ┌────┐ ┌────┐ │ │ Value: │ 10 │ │ 20 │ │ 30 │ │ 40 │ │ 50 │ │ │ └────┘ └────┘ └────┘ └────┘ └────┘ │ │ Address: 100 104 108 112 116 │ │ (each int = 4 bytes, so +4 each time) │ │ │ └─────────────────────────────────────────────────────────────┘
This contiguous layout is the secret to the array's superpower: instant access by index.
2. Why Index Access is O(1) — The Address Formula
When you write arr[3], the computer does NOT walk through boxes 0, 1, 2, then 3. It calculates the exact memory address in one shot:
address of arr[i] = startAddress + (i × sizeOfElement) Example: arr[3] = 100 + (3 × 4) = 100 + 12 = 112 ← jump straight there!
One multiplication and one addition — that's it. It takes the same time whether the array has 5 elements or 5 billion. That is why array access is O(1).
3. The Real Cost of Each Operation
| Operation | Time | Why |
|---|---|---|
Access by index — arr[i] | O(1) | Address formula, direct jump |
Update by index — arr[i] = x | O(1) | Jump there, overwrite |
| Search (unsorted) | O(n) | Might check every box |
| Push (add at end) | O(1)* | Last slot is known |
| Pop (remove from end) | O(1) | Nothing shifts |
| Unshift (add at start) | O(n) | Every element shifts right |
| Shift (remove from start) | O(n) | Every element shifts left |
| Insert in middle | O(n) | Shift everything after it |
The key insight: anything at the END is cheap; anything at the START or MIDDLE is expensive because the contiguous layout must stay packed with no gaps.
WHY unshift IS O(n) — inserting 5 at the front:
Before: [ 10 | 20 | 30 ]
every element must move right
Step: [ 5 | 10 | 20 | 30 ]
↑ ← ← ←
3 elements shifted → O(n). For a million elements, a million shifts!
4. Static vs Dynamic Arrays
┌─────────────────────────────────────────────────────────────┐ │ STATIC ARRAY vs DYNAMIC ARRAY │ ├─────────────────────────────────────────────────────────────┤ │ Fixed size at creation │ Grows automatically │ │ (C, Java int[]) │ (JS Array, Python list) │ │ Can't add beyond capacity │ Resizes behind the scenes │ └─────────────────────────────────────────────────────────────┘
JavaScript arrays are dynamic. When a dynamic array runs out of room, it secretly does this:
1. Allocate a NEW bigger array (usually 2× the size) 2. COPY all old elements over ← this copy is O(n) 3. Add the new element
So a single push is usually O(1), but occasionally O(n) when it must resize. Averaged out over many pushes, it works out to O(1) — this is called amortized O(1) (we prove it in Deep Dive 02).
5. Traversal & In-Place Patterns
// Standard traversal
for (let i = 0; i < arr.length; i++) {
console.log(arr[i]);
}
// Reverse in place — O(n) time, O(1) space (two pointers!)
function reverse(arr) {
let left = 0, right = arr.length - 1;
while (left < right) {
[arr[left], arr[right]] = [arr[right], arr[left]]; // swap
left++;
right--;
}
return arr;
}
HAND TRACE: reverse([1, 2, 3, 4])
start: [1, 2, 3, 4] left=0 right=3 → swap 1,4 → [4,2,3,1]
left=1 right=2 → swap 2,3 → [4,3,2,1]
left=2 right=1 → left >= right, STOP
result: [4, 3, 2, 1] ✔
6. Prefix Sum — The O(n)→O(1) Pattern
Problem: given an array, answer many queries of "what's the sum from index i to j?" A naive sum is O(n) per query. With prefix sum, after O(n) setup, every query is O(1).
Idea: build an array where prefix[i] = sum of all elements up to index i.
arr = [ 2, 4, 6, 8 ] prefix = [ 2, 6, 12, 20 ] ← running total Sum from index 1 to 3 (4+6+8 = 18): = prefix[3] - prefix[0] = 20 - 2 = 18 ✔ (one subtraction → O(1)!)
function buildPrefix(arr) {
const prefix = [arr[0]];
for (let i = 1; i < arr.length; i++) {
prefix[i] = prefix[i - 1] + arr[i];
}
return prefix;
}
// Sum of range [i, j] inclusive:
function rangeSum(prefix, i, j) {
if (i === 0) return prefix[j];
return prefix[j] - prefix[i - 1]; // O(1)!
}
7. Kadane's Algorithm — Maximum Subarray
Problem: find the contiguous subarray with the largest sum. Brute force checks every subarray — O(n²). Kadane's does it in one pass — O(n).
Idea: at each element, decide — "do I extend the previous subarray, or start fresh from here?"
function maxSubArray(arr) {
let currentMax = arr[0];
let globalMax = arr[0];
for (let i = 1; i < arr.length; i++) {
// extend OR restart at arr[i]
currentMax = Math.max(arr[i], currentMax + arr[i]);
globalMax = Math.max(globalMax, currentMax);
}
return globalMax;
}
HAND TRACE: [-2, 1, -3, 4, -1, 2, 1] i=0: cur=-2 glob=-2 i=1: cur=max(1, -2+1)=1 glob=1 i=2: cur=max(-3, 1-3)=-2 glob=1 i=3: cur=max(4, -2+4)=4 glob=4 ← restart paid off i=4: cur=max(-1, 4-1)=3 glob=4 i=5: cur=max(2, 3+2)=5 glob=5 i=6: cur=max(1, 5+1)=6 glob=6 ← answer! Max subarray sum = 6 (the subarray [4,-1,2,1]) ✔
Interview Questions — Quick Fire!
Q: Why is accessing an array element by index O(1)?
"Arrays are stored contiguously in memory, so the address of any element can be calculated directly with startAddress + index × elementSize. It's a single arithmetic step regardless of array size — no scanning needed."
Q: Why is inserting at the beginning of an array O(n)?
"Because the array must stay contiguous with no gaps. Inserting at the front means every existing element has to shift one position to the right, which is n moves. Inserting at the end is O(1) since nothing needs to shift."
Q: Why is push amortized O(1) and not just O(1)?
"Dynamic arrays occasionally run out of capacity and must allocate a bigger array and copy everything over, which is O(n). But that doubling happens rarely, so when you average the cost across many pushes it comes out to O(1) per push — that's amortized O(1)."
Q: What is the prefix sum technique?
"You precompute a running total array once in O(n). Then any range-sum query becomes a single subtraction, prefix[j] - prefix[i-1], in O(1). It's perfect when you have many sum queries over the same array."
Q: Explain Kadane's algorithm.
"It finds the maximum-sum contiguous subarray in O(n). At each element you choose whether to extend the current subarray or start a new one from that element, keeping a running best. It works because a negative running sum can never help a future subarray, so you drop it and restart."
Quick Recap
| Concept | Key Takeaway |
|---|---|
| Memory layout | Contiguous boxes, same size each. |
| Index access | O(1) via the address formula. |
| End vs front | End ops O(1); front/middle ops O(n) (shifting). |
| Dynamic array | Grows by doubling + copy → push is amortized O(1). |
| Prefix sum | O(n) setup → O(1) range-sum queries. |
| Kadane's | Max subarray sum in O(n), one pass. |
What's Next?
In Chapter 03 we tackle Strings — which are really just arrays of characters, but with a twist: in JavaScript they're immutable. We'll see why that makes naive string-building O(n²), and learn palindromes, anagrams, and frequency counting.
Make sure you can explain WHY front-insertion is O(n), and try implementing prefix sum and Kadane's from memory.
Keep coding, keep grinding! See you in the next one!
Post a Comment