Arrays and Dynamic Arrays

Welcome to Phase 3. Every data structure you’ll meet from here on is either built on top of an array, or exists specifically to fix one of its limitations. Get comfortable with arrays first and half of interview prep gets easier immediately.

What you’ll learn

• Fixed-size array vs dynamic array, and why Python’s list is the latter.
• Why list.append is amortized $O(1)$ thanks to geometric over-allocation.
• The real complexity of index, append, insert, and pop at different positions.
• The two-pointer technique for in-place array work.
• Prefix sums for O(1) range-sum queries after one O(n) pre-pass.
• LeetCode-style problems to drill the pattern.

The cue

Reach for an array when…

• Access is by position and you need it in $O(1)$.
• You iterate far more often than you insert or delete in the middle.
• Cache locality matters — a contiguous block is dramatically faster to scan than a linked structure, and that constant factor is often the whole reason a solution passes.

Reach for something else when you insert or delete at the front repeatedly (collections.deque, $O(1)$ at both ends versus $O(n)$ for list.pop(0)), when lookup is by key rather than position (a dict), or when you need the smallest element repeatedly (heapq).

Fixed array vs dynamic array

A fixed-size array (like a C array) reserves one contiguous block of memory for exactly n elements, decided up front. Growing it means allocating a whole new block and copying everything over — there’s no “just add one more”.

A dynamic array hides that pain behind a friendly append. Python’s built-in list is a dynamic array: contiguous storage under the hood, but it over-allocates — when it runs out of room it grabs a bigger block (roughly 1.125x the old capacity once the list is large) and copies the existing pointers across, once. Because that expensive copy happens less and less often as the list grows, the average cost per append stays $O(1)$ — this is called amortized analysis.

array_growth.py

import sys
 
arr = []
prev_capacity_hint = sys.getsizeof(arr)
growths = 0
 
for i in range(25):
    arr.append(i)
    size = sys.getsizeof(arr)
    if size != prev_capacity_hint:
        growths += 1
        print(f"n={i + 1:<3} underlying buffer resized (event #{growths})")
        prev_capacity_hint = size
 
print(f"\n25 appends, only {growths} real reallocations — the rest were free.")

Notice the buffer only resizes a handful of times across 25 appends, not once per element. Each resize is $O(n)$, but it happens on a shrinking fraction of the appends, so the total cost for n appends is $O(n)$, which averages out to $O(1)$ per append.

Watch a dynamic array double

When the backing block fills up, CPython allocates a bigger one and copies every existing element across before the new item is written in:

sketch Dynamic array growth on append p5.js Pause Restart

The array starts with room for 4 items. Once full, a new, bigger block is allocated and every old element is copied across (shown in amber) before the new element (green) is added.

Complexity of common list operations

Operation	Example	Complexity
Index / update	arr[i], arr[i] = x	$O(1)$
Append (end)	arr.append(x)	$O(1)$ amortized
Pop (end)	arr.pop()	$O(1)$ amortized
Insert at front/middle	arr.insert(0, x)	$O(n)$
Pop from front/middle	arr.pop(0)	$O(n)$
Search / membership	x in arr	$O(n)$
Length	len(arr)	$O(1)$

Rule of thumb

Anything at the end of a Python list is cheap. Anything at the front or middle forces every element after it to shift — that’s the hidden $O(n)$ that turns an innocent-looking loop into $O(n^2)$.

Two pointers

The two-pointer technique uses two indices moving through the array — usually from both ends inward, or both from the same side at different speeds — to solve problems in one pass instead of a nested loop.

two_pointers.py

def reverse_in_place(arr):
    left, right = 0, len(arr) - 1
    while left < right:
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1
    return arr
 
 
def is_palindrome_array(arr):
    left, right = 0, len(arr) - 1
    while left < right:
        if arr[left] != arr[right]:
            return False
        left += 1
        right -= 1
    return True
 
 
print(reverse_in_place([1, 2, 3, 4, 5]))
print(is_palindrome_array([1, 2, 3, 2, 1]))
print(is_palindrome_array([1, 2, 3]))

Both functions do a single $O(n)$ pass with $O(1)$ extra space — no temporary copy of the array needed.

Prefix sums

If you need the sum of many sub-ranges of the same array, don’t re-sum each range from scratch (that’s $O(n)$ per query). Precompute a prefix sum array once, then answer every range-sum query in $O(1)$.

prefix_sums.py

def build_prefix(arr):
    prefix = [0] * (len(arr) + 1)
    for i, x in enumerate(arr):
        prefix[i + 1] = prefix[i] + x
    return prefix
 
 
def range_sum(prefix, left, right):
    # inclusive sum of arr[left..right], O(1) after the O(n) pre-pass
    return prefix[right + 1] - prefix[left]
 
 
nums = [2, 4, 6, 8, 10, 12]
prefix = build_prefix(nums)
 
print("sum(1..3):", range_sum(prefix, 1, 3))   # 4 + 6 + 8
print("sum(0..5):", range_sum(prefix, 0, 5))   # whole array

$$\text{prefix}[i] = \sum_{k=0}^{i-1} \text{arr}[k] \quad\Rightarrow\quad \text{sum}(l, r) = \text{prefix}[r+1] - \text{prefix}[l].$$

One $O(n)$ pass builds the prefix array; every query after that is $O(1)$.

LeetCode problem set

Generated from the problem database, so each entry carries its sheet membership and reported companies. Tick them off as you go — progress is saved in this browser, and the Export button writes it to a file you can keep.

7 problems

3 easy3 medium1 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

AllEasyMediumHard

Unsolved onlyExportImportReset

• ○1Two SumeasyThe canonical array-plus-hash-map warm-up: one pass, check the complement before insertingNeetCode 150Blind 75LeetCode Top Interview 150amazongooglemetamicrosoftapplebloomberg
• ○121Best Time to Buy and Sell StockeasyA single scan tracking the running minimum -- no need to store anything elseNeetCode 150Blind 75LeetCode Top Interview 150amazonmetamicrosoftbloomberg
• ○169Majority ElementeasyLeetCode Top Interview 150
• ○75Sort Colorsmediumamazonmicrosoftmeta
• ○189Rotate ArraymediumLeetCode Top Interview 150
• ○274H-IndexmediumLeetCode Top Interview 150
• ○135CandyhardLeetCode Top Interview 150

Practice — real LeetCode problems

Each exercise is the actual LeetCode problem with its real method signature and LeetCode’s own examples as the test. Write the body, press Run, and match the expected output.

LC 121 — Best Time to Buy and Sell Stock · Easy

Problem. Given prices[i] for day i, choose one day to buy and a later day to sell to maximise profit. Return the maximum profit, or 0 if none is possible.

Constraints. 1 <= len(prices) <= 10^5, 0 <= prices[i] <= 10^4.

Examples. [7,1,5,3,6,4] gives 5 (buy at 1, sell at 6) · [7,6,4,3,1] gives 0 (never profitable)

pch.exerciseTag pch.exerciseTitle

Editorial

For each day, the best possible sale is that price minus the cheapest price seen before it. Tracking a running minimum makes that $O(1)$ per day.

Time $O(n)$. Space $O(1)$.

[7,6,4,3,1] returning 0 matters: prices only fall, so no transaction is made at all. Initialising best = 0 rather than to a negative sentinel is what encodes “you may decline to trade”.

Note this is also Kadane’s algorithm applied to the array of day-to-day differences — the maximum subarray sum of [-1, 4, -2, 3, -2] is 5. Seeing the connection is worth mentioning.

Follow-ups: “Unlimited transactions (LC 122)?” — sum every positive difference. “At most two transactions (LC 123)?” — DP over four states. “With a cooldown (LC 309) or a fee (LC 714)?” — state-machine DP.

LC 283 — Move Zeroes · Easy

Problem. Move all 0s to the end of the array in place, keeping the relative order of the non-zero elements. You must not copy the array.

Constraints. 1 <= len(nums) <= 10^4, -2^31 <= nums[i] <= 2^31 - 1.

Examples. [0,1,0,3,12] gives [1,3,12,0,0] · [0] gives [0]

pch.exerciseTag pch.exerciseTitle

Editorial

write marks where the next non-zero belongs. Every non-zero found is swapped into that slot, which simultaneously pushes whatever was there — necessarily a zero, or the element itself — to the read position.

Time $O(n)$. Space $O(1)$.

Swapping matters. Assigning nums[write] = nums[read] would also compact the non-zeros, but you would then need a second loop to zero out the tail. The swap does both jobs in one pass.

This is the same read/write pointer idea behind LC 26 and LC 27 — a same-direction two-pointer scan rather than the converging kind.

Follow-ups: “Minimise writes?” — assign only when read != write, skipping no-op swaps. “Move zeroes to the front?” — scan from the right. “Remove all instances of a value (LC 27)?” — identical structure.

LC 26 — Remove Duplicates from Sorted Array · Easy

Problem. Given a sorted array, remove duplicates in place so each unique element appears once, keeping relative order. Return k, the number of unique elements; the first k slots must hold them.

Constraints. 1 <= len(nums) <= 3 * 10^4, sorted non-decreasing.

Examples. [1,1,2] gives k = 2 with [1,2] · [0,0,1,1,1,2,2,3,3,4] gives k = 5 with [0,1,2,3,4]

pch.exerciseTag pch.exerciseTitle

Editorial

Sortedness guarantees duplicates are adjacent, so one pass suffices. The subtlety is what to compare against.

Time $O(n)$. Space $O(1)$.

Comparing with nums[write - 1] — the last element actually kept — is correct. Comparing with nums[read - 1] happens to work here too, but the “last kept” formulation is the one that generalises: LC 80 allows each value twice, and there the test becomes nums[read] != nums[write - 2]. Learning the general shape now saves rederiving it.

[0,0,1,1,1,2,2,3,3,4] includes a run of three, which is where a careless comparison shows up.

Follow-ups: “Allow up to two of each (LC 80)?” — compare against nums[write - 2]. “Unsorted input?” — you need a set, so $O(n)$ space, and order preservation becomes a separate concern. “Return the array rather than the count?” — slice to nums[:write].

Dry run

Amortised growth. CPython over-allocates on append, so most appends are $O(1)$ and an occasional one copies everything:

appends	capacity	copy?	cost
1	4	allocate	1
2–4	4	no	1 each
5	8	copy 4	5
6–8	8	no	1 each
9	16	copy 8	9
10–16	16	no	1 each

Total for 16 appends: 16 cheap steps plus 4 + 8 = 12 copies, so about 28 operations. Because capacity multiplies rather than adding a constant, the copies form a geometric series that sums to $O(n)$ overall — hence $O(1)$ amortised per append. Grow by a fixed amount instead and the same argument gives $O(n^2)$ total, which is the point of the question.

list.pop(0) is O(n), and it is the most common accidental quadratic

Removing the front element shifts every remaining element left. Inside a loop that turns an $O(n)$ traversal into $O(n^2)$ — fine on the samples, TLE on the real tests. Use collections.deque and popleft() whenever you consume from the front.

The variant map

Need	Structure	Front insert/remove	Access by index
Indexed sequence, append-heavy	list	$O(n)$	$O(1)$
Queue or sliding window	collections.deque	$O(1)$	$O(n)$
Fixed-size numeric buffer	array.array	$O(n)$	$O(1)$
Sorted, with binary search	list + bisect	$O(n)$ insert	$O(1)$
Lookup by key	dict	—	—

Two Python specifics worth knowing: slicing copies, so arr[1:] inside a loop is a hidden $O(n^2)$; and list.insert(0, x) has the same problem as pop(0).

Pitfalls

• pop(0) or insert(0, x) in a loop. $O(n)$ each, so $O(n^2)$ overall. Use a deque.
• Slicing in a loop. arr[i:] allocates a copy every iteration. Pass indices instead of slices, especially in recursion.
• [[0] * n] * m for a 2-D grid. That creates m references to the same row, so writing one cell writes a whole column. Use a comprehension: [[0] * n for _ in range(m)].
• Mutating a list while iterating it. Skips elements silently. Iterate a copy, or build a new list.
• Assuming in is fast. x in list is $O(n)$; x in set is $O(1)$. This is the most common accidental quadratic after pop(0).

Interview follow-ups

They ask	What they’re checking	The answer
“Why is append $O(1)$ if it sometimes reallocates?”	Amortised reasoning	Capacity multiplies rather than increments, so the copies form a geometric series summing to $O(n)$ across $n$ appends
“What if it grew by a fixed 10 slots?”	Whether you understand why	Copies become an arithmetic series, so total work is $O(n^2)$ — the multiplication is load-bearing
“Why not always use a linked list for insertions?”	Practical judgement	$O(1)$ insertion requires already holding the node. Finding the position is $O(n)$, and cache locality makes the array faster in practice for most sizes
“Delete from the middle in $O(1)$”	Whether you know the trick	If order does not matter, swap the target with the last element and pop. This is the idea behind LC 380 Insert Delete GetRandom
“How would you rotate by k in $O(1)$ space?”	In-place reasoning	Three reversals: whole array, first k, then the rest. Or a cyclic-replacement walk using gcd(n, k) cycles

Self-check

pch.quizTag Arrays and dynamic arrays — self-check

1. Why is append O(1) amortised rather than O(n)?

   A Because reallocation never happens in practice B Because capacity multiplies rather than increments, so the copy costs form a geometric series summing to O(n) over n appends C Because CPython pre-allocates a large fixed buffer D It is not — append is O(n)
   pch.quizShowAnswer

   B — Because capacity multiplies rather than increments, so the copy costs form a geometric series summing to O(n) over n appends — The growth factor is the load-bearing detail. Grow by a fixed amount instead and total copying becomes an arithmetic series, giving O(n squared) overall.

2. What is wrong with list.pop(0) inside a loop?

   A Nothing — it is O(1) B It shifts every remaining element left, so it is O(n) per call and O(n squared) in a loop C It raises an error on an empty list D It returns the wrong element
   pch.quizShowAnswer

   B — It shifts every remaining element left, so it is O(n) per call and O(n squared) in a loop — This is the most common accidental quadratic in Python. collections.deque.popleft() is O(1) and is what you want whenever you consume from the front.

3. What does [[0] * 3] * 2 create?

   A A 2x3 grid of independent zeros B Two references to the SAME row, so writing one cell appears to write a whole column C A syntax error D A 3x2 grid
   pch.quizShowAnswer

   B — Two references to the SAME row, so writing one cell appears to write a whole column — The outer multiplication copies the reference, not the row. Use [[0] * 3 for _ in range(2)]. The bug shows up as mysteriously correlated cells.

4. You must delete an arbitrary element in O(1) and order does not matter. How?

   A Use list.remove() B Swap the target with the last element, then pop from the end C Set it to None D It is impossible
   pch.quizShowAnswer

   B — Swap the target with the last element, then pop from the end — Popping from the end is O(1), so moving the target there first makes the whole operation O(1). This is the core trick behind LC 380 Insert Delete GetRandom.

Recall card

• Use when — access by position, iteration-heavy, cache locality matters.
• Costs — index $O(1)$; append $O(1)$ amortised; insert/delete at the front or middle $O(n)$; in $O(n)$.
• Amortised argument — capacity multiplies, so copies form a geometric series summing to $O(n)$.
• Python traps — pop(0) and insert(0, x) are $O(n)$; slicing copies; [[0]*n]*m shares rows; x in list is $O(n)$.
• Swap-with-last deletes in $O(1)$ when order does not matter.

Recap

• Python’s list is a dynamic array: contiguous storage that over-allocates so append is amortized $O(1)$.
• End operations are cheap ($O(1)$); front/middle operations are expensive ($O(n)$) because everything after them has to shift.
• Two pointers solve many array problems in one $O(n)$ pass with $O(1)$ extra space.
• Prefix sums trade one $O(n)$ pre-pass for $O(1)$ range-sum queries afterward.

Next: Strings — why Python strings are immutable, and the patterns that follow from that.