Arrays
EasyArrays store elements in contiguous memory locations, allowing O(1) access by index. They're the most fundamental data structure and the building block for many others. Understanding when arrays excel and when they struggle is crucial for algorithm design.
Interactive Visualization
Memory Layout (Contiguous)address = base + (index × size)
0x3e8
10
[0]
0x3ec
20
[1]
0x3f0
30
[2]
0x3f4
40
[3]
0x3f8
50
[4]
accessArray stored in contiguous memory. Each element is 4 bytes apart.
1 / 5
Key Insight: Arrays provide O(1) access because memory address can be calculated directly from the index. No need to traverse!
Time Complexity
| Operation | Average |
|---|---|
| Access | O(1) |
| Search | O(n) |
| Insert (end) | O(1) |
| Insert (middle) | O(n) |
| Delete (end) | O(1) |
| Delete (middle) | O(n) |
Key Points
- Elements stored in contiguous (sequential) memory
- O(1) access by index - direct memory address calculation
- O(n) search in unsorted array - must check each element
- O(n) insert/delete in middle - must shift elements
- Fixed size in most languages (JS arrays are dynamic)
- Great cache performance due to memory locality
Code Examples
Array Access O(1)
const arr = [10, 20, 30, 40, 50]
// Direct access by index
arr[0] // 10 - instant
arr[2] // 30 - instant
arr[4] // 50 - instant
// Why O(1)? Memory address calculation:
// address = baseAddress + (index × elementSize)
// No iteration needed!Index gives direct memory location
Array Search O(n)
const arr = [10, 20, 30, 40, 50]
// Find index of value 30
function indexOf(arr, target) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) return i
}
return -1
}
indexOf(arr, 30) // Returns 2
indexOf(arr, 99) // Returns -1
// Must check elements one by one
// Worst case: check ALL elementsMust scan until found or end
Insert at End O(1)*
const arr = [10, 20, 30]
// Append to end - usually O(1)
arr.push(40) // [10, 20, 30, 40]
// * Amortized O(1) because:
// - Usually just adds to next slot
// - Occasionally needs to resize (copy all)
// - Resize doubles capacity, so rare
// JS handles this automatically
// In other languages, you manage capacityFast append, occasional resize
Insert in Middle O(n)
const arr = [10, 20, 40, 50]
// Insert 30 at index 2
arr.splice(2, 0, 30)
// Result: [10, 20, 30, 40, 50]
// What happened internally:
// 1. Shift 40 to index 3
// 2. Shift 50 to index 4
// 3. Place 30 at index 2
// Must shift all elements after insertion point
// Inserting at index 0 is O(n) - shifts everything!Must shift all elements after
Delete from Middle O(n)
const arr = [10, 20, 30, 40, 50]
// Remove element at index 2
arr.splice(2, 1)
// Result: [10, 20, 40, 50]
// What happened internally:
// 1. Remove 30
// 2. Shift 40 to index 2
// 3. Shift 50 to index 3
// Same issue as insert - must close the gapMust shift elements to fill gap
When to Use Arrays
// ✅ GOOD for arrays:
// - Need random access by index
// - Mostly reading, few writes
// - Iterating in order
// - Fixed or known size
// ❌ AVOID arrays when:
// - Frequent insert/delete in middle
// - Frequent insert/delete at beginning
// - Unknown/highly variable size
// - Need fast search (use hash table)
// Common array operations:
arr.push(x) // O(1) - add to end
arr.pop() // O(1) - remove from end
arr.shift() // O(n) - remove from start
arr.unshift(x) // O(n) - add to start
arr[i] // O(1) - access
arr.includes(x) // O(n) - searchKnow when arrays are the right choice
Common Mistakes
- Using array.shift() in a loop (O(n²) total)
- Not considering that splice is O(n)
- Assuming JS arrays work like other languages (they're actually objects)
- Using arrays when a hash map would give O(1) lookup
Interview Tips
- Arrays are great when you need index-based access
- For frequent front operations, consider a deque or linked list
- Sorted arrays enable O(log n) binary search
- Two-pointer techniques often work well on sorted arrays