Arrays, Contiguous Memory & Hash Tables
Master contiguous memory layout, CPU cache locality, dynamic array amortized doubling, and O(1) hash map collision resolution strategies.
Key Learning Objectives
- Explain how indexed array access achieves O(1) time via base pointer arithmetic.
- Analyze why dynamic array appends are amortized O(1) despite occasional O(n) reallocations.
- Construct a frequency counter and hash map lookup table to reduce O(n²) loops to O(n).
- Handle common edge cases: duplicate values, negative numbers, and memory bounds.
Contiguous Memory Allocation & Pointer Arithmetic
An array is a linear collection of elements stored at contiguous memory locations. When you allocate an array in languages like C++, Java, or Go, the runtime calculates the memory address of index i using a simple arithmetic formula: Address(i) = BaseAddress + (i * ElementSize). Because this calculation takes a fixed number of CPU cycles regardless of the array's length, array indexing is strictly O(1) time complexity. Furthermore, because array elements sit side-by-side in RAM, modern CPU cache pre-fetchers can load consecutive elements into fast L1/L2 cache lines ahead of time, providing exceptional hardware throughput compared to pointer-heavy data structures like linked lists.
// Array pointer indexing vs Dynamic Array Amortization
const numbers: number[] = [10, 20, 30, 40, 50];
// Accessing index 2: Base_Ptr + 2 * 8 bytes = direct memory jump -> 30 in O(1)
console.log(numbers[2]);
// Frequency Counter pattern using a Map
function hasDuplicates(nums: number[]): boolean {
const seen = new Set<number>();
for (const n of nums) {
if (seen.has(n)) return true; // Found in O(1) average lookup
seen.add(n);
}
return false;
}
Set lookup takes O(1) average time via hashing, enabling single-pass duplicate detection in O(n) time and O(n) space.
Hash Maps & Collision Resolution
A Hash Table implements an associative array abstract data type that maps keys to values. A hash function takes an arbitrary key (like a string or object) and converts it into a fixed-size integer index within an internal bucket array. Because the universe of possible keys is vastly larger than the array size, collisions are mathematically inevitable (by the Pigeonhole Principle). Modern production engines resolve collisions via Separate Chaining (linked lists or self-balancing Red-Black trees at each bucket, as used in Java HashMap) or Open Addressing (probing consecutive or pseudo-random empty slots, as used in Python dict). An ideal hash function minimizes clustering and distributes keys uniformly.
// The Two-Sum Complement Pattern: O(n) Time & O(n) Auxiliary Space
function twoSum(nums: number[], target: number): number[] {
// Map stores: Value -> Index in array
const complementMap = new Map<number, number>();
for (let i = 0; i < nums.length; i++) {
const current = nums[i];
const complement = target - current;
// Check if the required complement was previously stored
if (complementMap.has(complement)) {
return [complementMap.get(complement)!, i];
}
// Otherwise, store current element's index
complementMap.set(current, i);
}
return [];
}
By storing visited numbers in a hash map, we eliminate the need for an inner loop, reducing time from O(n²) to O(n).
Build It: Build an In-Memory LRU Cache with O(1) Operations
Implement a Least Recently Used (LRU) Cache combining a Hash Map and a Doubly Linked List.
Project Deliverables
- get(key) runs in O(1) average time and moves accessed node to the head of the list.
- put(key, value) inserts in O(1) time and evicts the least recently used tail node when capacity is exceeded.
Acceptance Criteria
- All operations strictly O(1) time complexity
- Handles capacity eviction cleanly without memory leaks
- Unit tests pass for duplicate keys and sequential overwrites
Next Steps & Related Learning
This interactive lesson is part of the LeetCode Practice curriculum. Continue exploring or try another interactive lesson: