All Roadmaps›🧠 Data Structures & Algorithms›Phase 2›Arrays — Deep Dive & Internal Implementation

Arrays — Deep Dive & Internal Implementation

0/14 in this phase0/57 across the roadmap

📖 Concept

Arrays are the most fundamental data structure — a contiguous block of memory that stores elements at indexed positions. In JavaScript, arrays are actually objects with integer keys and special length tracking, but modern engines optimize them to behave like true arrays when possible.

Internal Implementation:

  • Dense arrays (all elements same type, no holes): V8 stores these like C arrays — contiguous memory, O(1) access
  • Sparse arrays (holes or mixed types): V8 falls back to hash map storage — slower
  • Typed arrays (Int32Array, Float64Array): True fixed-size contiguous memory, closest to C arrays

Key operations & complexity:

Operation Complexity Why
Access by index O(1) Direct memory offset calculation
Push (end) O(1) amortized Append + occasional resize
Pop (end) O(1) Remove last, no shifting
Unshift (front) O(n) Must shift ALL elements right
Shift (front) O(n) Must shift ALL elements left
Insert (middle) O(n) Shift elements after insertion point
Delete (middle) O(n) Shift elements to fill gap
Search (unsorted) O(n) Must scan all elements
Search (sorted) O(log n) Binary search

When to use arrays:

  • Need fast access by index
  • Data is ordered/sequential
  • Size is known or grows at the end
  • Cache-friendly iteration (contiguous memory)

🏠 Real-world analogy: An array is like a row of lockers numbered 0, 1, 2, ... You can instantly go to locker #50 (O(1) access). But inserting a new locker in the middle means renumbering everything after it (O(n)).

💻 Code Example

codeTap to expand ⛶
1// ARRAY INTERNALS — Dense vs Sparse
2const dense = [1, 2, 3, 4, 5];     // V8 optimizes: contiguous memory
3const sparse = [1, , , , 5];        // Sparse! V8 uses hash map (slower)
4const mixed = [1, "two", true, {}]; // Mixed types → less optimized
5

6// KEY OPERATIONS WITH COMPLEXITY
7const arr = [10, 20, 30, 40, 50];
8

9// O(1) — access, push, pop
10console.log(arr[2]);        // 30
11arr.push(60);               // [10,20,30,40,50,60]
12arr.pop();                  // [10,20,30,40,50]
13

14// O(n) — unshift, shift, splice
15arr.unshift(5);             // [5,10,20,30,40,50] — shifts everything!
16arr.shift();                // [10,20,30,40,50]
17arr.splice(2, 0, 25);       // [10,20,25,30,40,50] — insert at index 2
18

19// BUILDING FROM SCRATCH (TypeScript)
20class MyArray<T> {
21  private data: Record<number, T> = {};
22  private _length: number = 0;
23

24  get length(): number { return this._length; }
25

26  push(item: T): number {
27    this.data[this._length] = item;
28    this._length++;
29    return this._length;
30  }
31

32  get(index: number): T | undefined {
33    return this.data[index];
34  }
35

36  pop(): T | undefined {
37    if (this._length === 0) return undefined;
38    const last = this.data[this._length - 1];
39    delete this.data[this._length - 1];
40    this._length--;
41    return last;
42  }
43

44  delete(index: number): T | undefined {
45    const item = this.data[index];
46    this.shiftItems(index);
47    return item;
48  }
49

50  private shiftItems(index: number): void {
51    for (let i = index; i < this._length - 1; i++) {
52      this.data[i] = this.data[i + 1]; // O(n) shifting
53    }
54    delete this.data[this._length - 1];
55    this._length--;
56  }
57}
58

59// COMMON ARRAY PATTERNS
60// Reverse in-place — O(n) time, O(1) space
61function reverseInPlace(arr: number[]): number[] {
62  let l = 0, r = arr.length - 1;
63  while (l < r) {
64    [arr[l], arr[r]] = [arr[r], arr[l]];
65    l++; r--;
66  }
67  return arr;
68}
69

70// Rotate array by k positions — O(n) time, O(1) space
71function rotate(arr: number[], k: number): void {
72  k = k % arr.length;
73  reverse(arr, 0, arr.length - 1);
74  reverse(arr, 0, k - 1);
75  reverse(arr, k, arr.length - 1);
76}
77function reverse(arr: number[], start: number, end: number): void {
78  while (start < end) {
79    [arr[start], arr[end]] = [arr[end], arr[start]];
80    start++; end--;
81  }
82}

🏋️ Practice Exercise

Practice Problems (Easy → Hard):

  1. Remove duplicates from a sorted array in-place — O(1) extra space
  2. Rotate an array to the right by k steps
  3. Find the missing number from 0 to n
  4. Move all zeros to the end while maintaining order
  5. Find the majority element (appears > n/2 times)
  6. Merge two sorted arrays into one sorted array
  7. Find the contiguous subarray with the largest sum (Kadane's)
  8. Product of array except self — without division
  9. Find the first missing positive integer — O(n) time, O(1) space
  10. Trapping rain water — compute water trapped between bars

⚠️ Common Mistakes

  • Using unshift/shift for frequent front operations — O(n) each time; use a deque or linked list instead

  • Creating sparse arrays with new Array(n) without filling — leads to slower hash map storage

  • Mutating arrays during iteration — can skip elements or cause infinite loops

  • Not knowing that arr.length = 0 truncates the array — this is a valid way to clear it

  • Using delete arr[i] which leaves a hole — use splice instead for proper deletion

💼 Interview Questions

🎤 Mock Interview

Practice a live interview for Arrays — Deep Dive & Internal Implementation

← Previous30/90-Day Learning Plans & Practice StrategyNext →String Manipulation & Pattern Matching