Arrays & Dynamic Arrays

The foundation of almost every data structure you'll ever use

An array is a contiguous block of memory that stores elements of the same type. It's the simplest data structure, and understanding it deeply unlocks everything else.
Static arrays have a fixed size. Dynamic arrays (like Python's list) grow automatically, but that growth has a cost.

Array operations & their complexitiespython

nums = [10, 20, 30, 40, 50]

# O(1), direct index access (no searching needed)
print(nums[2])        # → 30

# O(1), append to end (amortized)
nums.append(60)

# O(n), insert at position (shifts elements right)
nums.insert(0, 5)     # now [5, 10, 20, 30, 40, 50, 60]

# O(n), remove from middle (shifts elements left)
nums.pop(0)           # shifts everything

# O(n), search (must check each element)
print(30 in nums)     # → True (scanned until found)

Why is append() O(1)? Python lists double their capacity when full. Most appends just place the value and increment a counter, O(1). Occasionally a resize copies everything, O(n). But the *amortized* cost across many appends is O(1).

🎬In the Real World...

Video frames in memory are stored as arrays of pixel values. Accessing frame #500 is instant (O(1)) because you can jump directly: frame_start + (500 × frame_size).

🤔Quick Check

Why is nums[i] O(1) but nums.index(value) O(n)?

Practice Exercises

0/2 solved

Exercise 1 of 2easy

⏱ 00:00

Running Sum

Given a list of numbers, return a new list where each element is the sum of all previous elements including itself.
Expected output: [1, 3, 6, 10, 15]

solution.py

1 / 2

Exercise 2 of 2medium

⏱ 00:00

Rotate Array

Rotate an array to the right by k steps in-place.
rotate([1,2,3,4,5], 2) → [4, 5, 1, 2, 3]
Expected output: [4, 5, 1, 2, 3]

solution.py

2 / 2

Solve all 2 exercises to unlock completion

Previous Next