Pattern GuideArrays & Strings
Fundamental Data Structure

Arrays & Strings

"The foundation of all data structures."

8 min read
Fundamental
Time: O(1) Access
01
CORE INTUITION

The Contiguous Advantage

šŸ“¦

If you want to store a single number, like a score of 10, you can just put it in a simple variable. But what if you have 1,000 scores to keep track of? Creating 1,000 separate variables would be a nightmare.

This is exactly the problem that Arrays solve. An array is simply a way to group a large list of items together under a single name. Under the hood, the computer finds a single chunk of memory and packs all of your items right next to each other in a sequential line.

Because they are lined up perfectly, we can retrieve any item instantly as long as we know its position (its "index").

A String is essentially the exact same concept, just exclusively designed for text! Instead of a list of numbers, a string is just an array where every item is a single letter or character. If you understand arrays, you already understand strings.

A Matrix (2D Array) is just an array where every item is another array! Instead of a 1D line of items, it forms a geometric grid with rows and columns. Matrices are incredibly common in grid-based problems (like mazes, game boards, or image processing), where you traverse or access elements using two coordinates: matrix[row][col].

02
VISUALIZATION

Instant Memory Access

Accessing arr[i] jumps directly to the exact memory address in an instant O(1) operation.

0
10
1
20
2
30
3
40
4
50
arr[0]ā†’10
address = base + index Ɨ 4=0x100 + 0Ɨ4=0x100

This is the mechanism behind O(1): the CPU computes the exact memory address with one multiply and one add ā€” no searching required.

03
THE OTHER SIDE

Insert & Delete: The Shifting Problem

Insert & Delete: The Shifting Problem

Accessing is instant, but inserting or removing at the front means every other element has to move to keep the array contiguous.

99
10
20
30
40
50

Press a button to see what actually happens in memory.

04
PERFORMANCE SNAPSHOT

Speed vs. Memory

Time Metrics

Random Access
O(1)
Linear Search
O(N)
Append (End)
O(1)*
Insert / Delete (Middle)
O(N)
Insert / Delete (Start)
O(N)

*Why append is usually free: dynamic arrays over-allocate and double their capacity when full, so most pushes just write into already-reserved space. The occasional resize-and-copy is O(N), but averaged ("amortized") over many pushes, it washes out to O(1).

Space Footprint

O(N)
Linear Growth
05
IMPLEMENTATION

Mastering the Basics

arrays.js
1
const arr = new Array(5).fill(0);
2
arr.push(10); // Append to end
3
arr.pop(); // Remove from end
4
5
// Linear Traversal
6
let sum = 0;
7
for (let i = 0; i < arr.length; i++) {
8
sum += arr[i];
9
}
strings.js
1
const s = "hello";
2
// Building a fast frequency map
3
const count = new Array(26).fill(0);
4
for (let i = 0; i < s.length; i++) {
5
// 97 is the char code for "a", so this maps a->0, b->1, ...
6
count[s.charCodeAt(i) - 97]++;
7
}
matrices.js
1
const rows = 3, cols = 4;
2
// Create a 2D Array initialized to 0
3
const mat = Array.from({ length: rows }, () => new Array(cols).fill(0));
4
5
// 2D Traversal
6
for (let r = 0; r < rows; r++) {
7
for (let c = 0; c < cols; c++) {
8
console.log(mat[r][c]);
9
}
10
}
06
PITFALLS

Common Mistakes

Off-by-One Errors

Looping with i <= arr.length instead of i < arr.length is the single most common array bug ā€” the valid indices are always 0 to length - 1.

Out-of-Bounds Access

In JS, arr[100] on a 5-element array silently returns undefined instead of erroring. In C++, it's undefined behavior ā€” it might read garbage memory instead of crashing. Always validate an index before trusting it.

String Concatenation in a Loop

In Java and Python, strings are immutable ā€” s += ch inside a loop allocates a brand-new string every iteration, copying everything so far. Over N iterations that's O(NĀ²). Use a StringBuilder (Java) or build a list and "".join(...) (Python) instead.

Sparse Arrays in JS

arr[10] = 5 on a 3-element JS array doesn't error ā€” it creates a sparse array with holes, and arr.length silently becomes 11. Methods like forEach skip the holes, which can make bugs invisible until you least expect it.

07
WHERE ARRAYS LEAD

Patterns Built On This Foundation

Two Pointers

Sorted array, looking for a pair or triplet? Converge from both ends.

Sliding Window

Contiguous subarray/substring with a size or sum constraint? Slide instead of re-scanning.

Prefix Sum

Repeated range-sum queries? Precompute once, answer in O(1).

Binary Search

Sorted data, or a monotonic yes/no answer? Halve the search space each step.

"Constant access for the known, linear search for the lost."