Dynamic Arrays & Amortized Resizing

Two Pointers Pattern (Converging & Symmetrical)

Master the converging two pointers technique to solve pair sum, palindrome verification, and partition problems in O(N) linear time.

1. Contiguous Memory Layout

A static array reserves a fixed block of sequential memory addresses at allocation time. A Dynamic Array (like JavaScript Arrays or Python Lists) expands automatically as new elements are added.

2. Geometric Doubling Strategy

When a dynamic array reaches maximum capacity, it cannot simply expand in-place because adjacent memory might be occupied. Instead:

1. It allocates a brand new memory block twice the size ($2 imes ext$).
2. Copies all existing $N$ elements into the new block.
3. Frees the old memory block and inserts the new item.

Initial Capacity [4]: [ 10 | 20 | 30 | 40 ] (FULL)
                               │
                Doubling Allocation (Capacity 8)
                               ▼
New Block:      [ 10 | 20 | 30 | 40 | 50 | __ | __ | __ ]
                  ▲──────────────▲    ▲
                    Copied Items    New Item

3. What is Amortized O(1) Time?

Copying $N$ elements takes $O(N)$ time, but resizing happens rarely (only after $1, 2, 4, 8, 16, dots$ elements). Averaged across $N$ insertions, the cost per push operation is $O(1)$ amortized.

4. Operation Complexities

5. Common Mistakes

• Unintended O(N) Shifts: Using arr.unshift() or arr.shift() in a loop turns an $O(N)$ algorithm into an accidental $O(N^2)$ bottleneck because every shift re-indexes all elements. Use two pointers or queues instead.

6. Next Steps

Understand array memory layouts to avoid hidden re-indexing costs. Next, let's explore the Two Pointers Pattern!