Array & Dynamic ArrayArrays and dynamic arrays

01Why it exists

Reach for it when you see:The i-th element, contiguous memory, random access, appending at the end, slow inserts in the middle, modifying in place, read and write pointers.

02The core idea

An array is one block of contiguous memory divided into slots of equal size. Because it is contiguous, the address of slot i can be computed directly: base + i × size. That is the array's one piece of magic, and every strength and weakness follows from it. Reading and overwriting are O(1); inserting or deleting in the middle means shifting everything after it to keep the block contiguous, which is O(n).

A fixed size is inconvenient, which is where the dynamic array comes in: it remembers its capacity and how many slots are in use, drops new elements straight into free space at the end (O(1)), and when it fills up allocates a block twice the size and copies everything across. That copy is O(n), but it happens rarely enough that a push still averages O(1) — amortised O(1), which is exactly what the previous lesson on amortised analysis was about.

Three numbers are all you need to remember: access O(1), add or remove at the end O(1), add or remove anywhere else O(n). Checking whether a value is present is O(n) as well, because without sorting there is nothing to do but look at one slot after another. If you need frequent inserts and deletes at the front, reach for a deque; if you need fast membership checks, reach for a hash table. Both come in later lessons.

03The algorithm

1. 1Work out where the operation happens: at the end it is O(1); anywhere else it has to shift everything after it, so it is O(n).
2. 2To delete or move elements in place, use a read pointer and a write pointer: read sweeps every slot, only the elements that qualify are written to the write position, and write ends up as the new length. One O(n) pass, with no new array.
3. 3When the task is something like moving the last k elements to the front, ask whether reversals can express it: reverse the whole array, then reverse each piece back, in O(1) extra space.
4. 4When you already know how many elements there will be, reserve the capacity first (reserve, [None] * n) and skip every growth copy.
5. 5insert(0, x), pop(0) or x in list inside a loop is a warning sign of O(n²); consider a deque or a set instead.

04Interactive demo

Under each slot is its memory address. Try inserting or deleting at the front and watch how many slots turn yellow, meaning they had to move; then compare an operation at the end, which touches a single slot.

05Code

The first half lists the complexity of every common operation; the second half has the two classic in-place techniques, read and write pointers and three reversals.

# Python's list is a dynamic array
nums = [12, 7, 3, 9, 15, 4]

nums[3]              # O(1): address = base + 3 × element size, so it jumps straight there
nums[3] = 10         # O(1)
nums.append(8)       # amortised O(1): if there is room at the end, it just goes there
nums.pop()           # O(1): decrement size

nums.insert(0, 99)   # O(n): every element shifts one slot right
nums.pop(0)          # O(n): every element shifts one slot left
99 in nums           # O(n): unsorted, so there is nothing to do but check one by one
del nums[2]          # O(n): everything after it closes the gap


# Remove every element equal to val, in place (LeetCode 27):
# a write pointer moves the keepers forward, with no new array
def remove_element(nums, val):
    write = 0
    for read in range(len(nums)):
        if nums[read] != val:
            nums[write] = nums[read]
            write += 1
    return write            # the first write elements are the result


# Rotate by k in place (LeetCode 189): three reversals, O(n) time and O(1) space
def rotate(nums, k):
    def reverse(i, j):
        while i < j:
            nums[i], nums[j] = nums[j], nums[i]
            i, j = i + 1, j - 1
    n = len(nums)
    k %= n
    reverse(0, n - 1)       # reverse the whole array
    reverse(0, k - 1)       # reverse the first k back
    reverse(k, n - 1)       # reverse the last n-k back

06Practice

• LeetCode 27Remove Element (read and write pointers)Easy
• LeetCode 26Remove Duplicates from Sorted ArrayEasy
• LeetCode 283Move ZeroesEasy
• LeetCode 189Rotate Array (three reversals)Medium
• LeetCode 238Product of Array Except SelfMedium