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 listlist is the latter.
• Why list.appendlist.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.

Fixed array vs dynamic array

A fixed-size array (like a C array) reserves one contiguous block of memory for exactly nn 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 appendappend. Python’s built-in listlist 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 appendappend stays $O(1)$ — this is called amortized analysis.

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.")

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 nn 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:

Complexity of common list operations

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.

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]))

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)$.

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

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

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

LeetCode problem set

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]prices[i] for day ii, choose one day to buy and a later day to sell to maximise profit. Return the maximum profit, or 00 if none is possible.

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

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

LC 283 — Move Zeroes · Easy

Problem. Move all 00s 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^41 <= len(nums) <= 10^4, -2^31 <= nums[i] <= 2^31 - 1-2^31 <= nums[i] <= 2^31 - 1.

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

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 kk, the number of unique elements; the first kk slots must hold them.

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

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

Recap

• Python’s listlist is a dynamic array: contiguous storage that over-allocates so appendappend 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.