🚂 Arrays

The Egg Carton Analogy

Think of an egg carton with 12 numbered slots (0-11).

To get the egg from slot #5:

• You don't check slots 0, 1, 2, 3, 4 first
• You reach directly to slot #5
• Instant access!

Arrays work exactly like egg cartons.

Each element sits in a numbered "slot" (index). You can access any slot instantly because they're arranged in a row in memory.

Why Arrays Are So Fast

Memory Layout

Array: [10, 20, 30, 40, 50]

In memory (consecutive addresses):
┌──────┬──────┬──────┬──────┬──────┐
│  10  │  20  │  30  │  40  │  50  │
└──────┴──────┴──────┴──────┴──────┘
 1000   1004   1008   1012   1016
  [0]    [1]    [2]    [3]    [4]

Each element is 4 bytes apart.

Direct Address Calculation

To find element at index i:

Address = BaseAddress + (i × ElementSize)

For arr[3]:
Address = 1000 + (3 × 4) = 1012

One calculation → Direct jump!

No need to traverse through elements. That's O(1) access.

The Trade-offs

What Arrays Do Well

*Amortized - occasionally needs resizing

What Arrays Do Poorly

The Shift Problem

Insert 15 at index 1:

Before: [10, 20, 30, 40, 50]
               ↓  ↓  ↓  ↓  (shift right first!)
After:  [10, 15, 20, 30, 40, 50]

5 elements shifted → O(n) work!

Static vs Dynamic Arrays

Static Arrays

Fixed size, determined at creation:

Pros:
  - Memory-efficient (no wasted space)
  - Predictable behavior

Cons:
  - Can't grow if you need more space
  - Waste space if you allocate too much

Dynamic Arrays

Grow automatically when needed (Python lists, JavaScript arrays):

Start: capacity = 4, size = 3
       [1, 2, 3, _]

Add element 4:
       [1, 2, 3, 4]  capacity still 4

Add element 5 → RESIZE!
New array: [1, 2, 3, 4, 5, _, _, _]
           capacity doubled to 8!

Resizing is O(n), but happens rarely enough that append is O(1) "amortized."

Common Array Patterns

Pattern 1: Two Pointers

For sorted arrays or when comparing ends:

Find pair that sums to 10 in [1, 2, 4, 5, 8, 9]:

Left pointer → 1, Right pointer → 9
Sum = 10! Found!

If sum too small: move left pointer right
If sum too big: move right pointer left

Pattern 2: Sliding Window

For contiguous subarrays:

Max sum of 3 consecutive elements in [2, 1, 5, 1, 3, 2]:

Window [2,1,5]: sum = 8
Slide: [1,5,1]: sum = 8 - 2 + 1 = 7
Slide: [5,1,3]: sum = 7 - 1 + 3 = 9 ← Max!

Pattern 3: Prefix Sum

For range sum queries:

Array: [1, 2, 3, 4, 5]
Prefix: [0, 1, 3, 6, 10, 15]

Sum from index 1 to 3?
prefix[4] - prefix[1] = 10 - 1 = 9 ✓

Any range sum in O(1)!

2D Arrays (Matrices)

Arrays of arrays:

     Col 0  Col 1  Col 2
Row 0  [1]    [2]    [3]
Row 1  [4]    [5]    [6]
Row 2  [7]    [8]    [9]

Access: matrix[row][col]
matrix[1][2] = 6

Common 2D Operations

• Traverse row by row: O(rows × cols)
• Rotate 90°: Transpose then reverse rows
• Spiral order: Track boundaries, shrink inward

Arrays vs Linked Lists

Rule of thumb: Often start with arrays. Consider linked lists if you're doing many middle insertions/deletions.

Common Mistakes

1. Index Out of Bounds

arr = [1, 2, 3]  # Valid indices: 0, 1, 2
arr[3]           # Error! Out of bounds
arr[-4]          # Error! Python allows negative, but not beyond array

2. Modifying While Iterating

Dangerous! Use indices or create a copy.

3. 2D Array Trap (Python)

# WRONG: All rows share same list!
matrix = [[0] * 3] * 3
matrix[0][0] = 1
# Result: [[1,0,0], [1,0,0], [1,0,0]] ← All changed!

# RIGHT: Each row is independent
matrix = [[0] * 3 for _ in range(3)]

4. Using Insert at Start

If you're inserting at the beginning often, use a deque instead. Array insert at index 0 is O(n).

When to Use Arrays

Use arrays when:

• Accessing elements by index frequently
• Data size is known or mostly stable
• Iterating through all elements
• Need cache-friendly memory layout

Consider alternatives when:

• Frequent insertions/deletions in the middle (→ linked list)
• Need fast lookups by value (→ hash table)
• Need sorted order with fast operations (→ balanced tree)

FAQ

Q: Why is insert at beginning slow?

Elements typically shift right to make room. In the worst case, shifting across $n$ elements is $O(n)$.

Q: What's the difference between array and list?

In many languages, "array" is fixed-size and same-type. "List" (like Python's) is dynamic and can hold mixed types.

Q: How does dynamic array doubling help?

Doubling means resizes are rare. After n appends, total resize work is proportional to n, so amortized cost per append is O(1).

Q: Should I use array or linked list?

Arrays are often a good default because they're simpler and fast for many use cases. Consider linked lists if you need $O(1)$ insertion/deletion when you already have a node/position.

Summary

Arrays store elements in contiguous memory, enabling O(1) random access by index.

Key Takeaways:

• O(1) access by index (the killer feature)
• O(n) insert/delete in middle (elements shift)
• Dynamic arrays resize automatically
• Common patterns: two pointers, sliding window, prefix sum
• Cache-friendly due to contiguous memory
• Watch for index bounds and 2D initialization traps

Arrays are the foundation - nearly every data structure and algorithm builds on them!