Arrays, Strings & Practical Measurement

The array is the most fundamental data structure, the foundation beneath almost every more complex one. And once you measure its real running time, Big O stops being a symbol on a whiteboard and becomes something you can feel.

Once that O(1) arithmetic is in your bones, four patterns — two pointers, sliding window, prefix sums, and in-place operations — turn that same fast index access into asymptotic wins on real problems. That’s the second half of this lesson.

Core idea

An array stores data in contiguous memory — slots laid out in a single unbroken row, no gaps between them.

Because the elements sit next to each other and each one is the same size, the computer can compute the location of element i instantly with simple arithmetic:

address of arr[i] = base address + (i × size of each element)

One multiply and one add, done — no matter whether the array holds a hundred elements or a million. This is why index access is O(1).

Insight: An array’s speed isn’t magic — it comes from laying data out so that addresses can be calculated.

But this contiguity has a price. To insert an element in the middle, every slot after it must shift back by one to make room. The closer to the front you insert, the more elements must move. In the worst case nearly all of them shift, making it O(n).

Operation costs

Operation	Big O	Why (one line)
Index access arr[i]	O(1)	Address computed directly with arithmetic
Append	O(1) amortized	Write into the free slot at the end (see amortized below)
Insert at front	O(n)	Every element shifts back by one
Insert in middle	O(n)	All elements after the insertion point shift
Delete	O(n)	Elements after the gap shift forward to fill it
Search	O(n)	Must scan element by element until found (if unsorted)

A note on append: Appending to a Python list is O(1) amortized. Occasionally, when the array is full, the system must grow it and copy the old contents — an O(n) event — but it happens rarely. Averaged over many appends, the cost works out to O(1).

Array vs. linked list: two different bets on memory

A linked list takes the opposite bet from an array. Instead of one contiguous block, each element lives in its own node scattered anywhere in memory, holding a pointer to the next node. That indirection is the whole story: prepending is O(1) (just repoint the head), but there is no arithmetic shortcut to “element i” — you must walk node by node from the head, so index access degrades to O(n).

Operation	Array	Linked list
Index access x[i]	O(1)	O(n) — must walk from the head
Insert/delete at front	O(n) — everyone shifts	O(1) — just repoint the head
Insert/delete at back	O(1) amortized	O(1) with a tail pointer, else O(n)
Insert/delete given a pointer to the spot	O(n) — still must shift	O(1) — no shifting, just repoint neighbors
Extra memory per element	none	one pointer (or two, if doubly linked)

Insight: Neither structure is universally “better.” Arrays win when you read by position constantly — the classic case is anything you’d naturally index into, like a lookup table. Linked lists win when you insert/delete at known positions constantly and rarely need to jump to position i.

Random access unlocks binary search

Because arr[mid] costs O(1) no matter where mid sits, a sorted array lets you throw away half the remaining candidates on every step: check the middle element, and depending on whether it’s too big or too small, recurse into the left or right half only.

def binary_search(arr: list[int], target: int) -> int:
    left: int = 0
    right: int = len(arr) - 1
    while left <= right:
        mid: int = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

Each comparison halves the search space, so the total work is O(log n) — for a billion elements, at most about 30 comparisons.

Insight: Binary search only works because arrays give O(1) random access. Try the same “jump to the middle” trick on a linked list and the jump itself costs O(n) (you still have to walk there), erasing the entire benefit. Random access is the enabling assumption behind the algorithm, not an incidental detail.

Strings are arrays of characters

A string is just a sequence of characters laid out in order — think of it as an array of letters. Accessing s[i] is therefore O(1), exactly like an array.

But in Python, strings are immutable (they cannot be changed). When you appear to “modify” a string, Python actually builds a whole new string and copies every existing character into it.

This is the classic trap — concatenating strings in a loop:

# ❌ The O(n²) trap — concatenate one piece at a time in a loop
def build_bad(n: int) -> str:
    result = ""
    for i in range(n):
        result = result + str(i)   # builds a new string each pass, copying everything
    return result

Every time result + str(i) runs, Python must copy all the characters accumulated so far into a fresh block. Pass 1 copies 1 character, pass 2 copies 2, … totalling 1 + 2 + ... + n ≈ n²/2, which is O(n²).

The fix is to collect the pieces in a list first, then join them once with "".join():

# ✅ The O(n) fix — collect into a list, then join once
def build_good(n: int) -> str:
    parts: list[str] = []
    for i in range(n):
        parts.append(str(i))       # append is O(1) amortized
    return "".join(parts)          # copies everything exactly once

Insight: Same problem, different approach — the difference is O(n²) versus O(n), which for large n is the difference between “done instantly” and “hung all day”.

Measure it yourself

The theory is convincing, but seeing the numbers appear on your own screen is another thing entirely. Use time.perf_counter to time both versions at n = 1k, 10k, 100k:

import time

def build_bad(n: int) -> str:
    result = ""
    for i in range(n):
        result = result + str(i)
    return result

def build_good(n: int) -> str:
    parts: list[str] = []
    for i in range(n):
        parts.append(str(i))
    return "".join(parts)

for n in (1_000, 10_000, 100_000):
    t0 = time.perf_counter()
    build_bad(n)
    t_bad = time.perf_counter() - t0

    t0 = time.perf_counter()
    build_good(n)
    t_good = time.perf_counter() - t0

    print(f"n={n:>7}  bad={t_bad:.4f}s  good={t_good:.4f}s")

How to read the results: each time n grows 10×

• If the time grows about 10× → the curve is linear, O(n) (this is build_good)
• If the time grows about 100× → the curve is quadratic, O(n²) (this is build_bad)

That growth multiplier is the signature of the curve — the Big O that was once abstract showing up as numbers on your screen.

Two pointers: shrinking the search space without nested loops

Picture two people starting at opposite ends of a hallway and walking toward each other, checking what they pass along the way — that’s the whole idea. Instead of a nested loop comparing every pair (O(n²)), you keep two indices, left and right, and move them based on what you observe. Each pointer moves forward at most n times total across the whole run, so the total work is O(n).

Example 1 — reverse an array in place (pointers start at opposite ends and converge):

def reverse_in_place(arr: list[int]) -> None:
    left: int = 0
    right: int = len(arr) - 1
    while left < right:
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1

Trace for arr = [1, 2, 3, 4, 5]:

Step	left	right	arr after swap
1	0	4	[5, 2, 3, 4, 1]
2	1	3	[5, 4, 3, 2, 1]
—	2	2	loop ends (left == right)

Example 2 — find a pair summing to a target in a sorted array (opposite ends, but which pointer moves depends on a comparison):

def find_pair_with_sum(nums: list[int], target: int) -> tuple[int, int] | None:
    left: int = 0
    right: int = len(nums) - 1
    while left < right:
        current_sum: int = nums[left] + nums[right]
        if current_sum == target:
            return (nums[left], nums[right])
        elif current_sum < target:
            left += 1   # sum too small, only a bigger left can help
        else:
            right -= 1  # sum too big, only a smaller right can help
    return None

Trace for nums = [1, 3, 4, 6, 8, 10], target = 12:

Step	left	right	nums[left]	nums[right]	sum	action
1	0	5	1	10	11	sum < target → left += 1
2	1	5	3	10	13	sum > target → right -= 1
3	1	4	3	8	11	sum < target → left += 1
4	2	4	4	8	12	sum == target → return (4, 8)

Sorting first costs O(n log n), but the search itself is O(n) — compare that to the naive nested-loop pair search, which is O(n²) regardless of order.

Example 3 — remove duplicates from a sorted array in place (both pointers move in the same direction — a “slow/fast” pair):

def remove_duplicates(nums: list[int]) -> int:
    if not nums:
        return 0
    slow: int = 0
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]
    return slow + 1   # number of unique elements, now packed at the front

Trace for nums = [1, 1, 2, 2, 3]:

fast	nums[fast]	nums[slow]	action	slow after	array after
1	1	1	same → skip	0	[1, 1, 2, 2, 3]
2	2	1	different → slow += 1, write	1	[1, 2, 2, 2, 3]
3	2	2	same → skip	1	[1, 2, 2, 2, 3]
4	3	2	different → slow += 1, write	2	[1, 2, 3, 2, 3]

Result: slow + 1 = 3 unique elements, sitting in nums[0:3] = [1, 2, 3] — done in one pass, O(n), with zero extra array.

Insight: The tell-tale sign a problem wants two pointers: the input is sorted (or can be treated as sorted), and a brute-force solution would compare every pair with a nested loop. Two pointers turns that O(n²) into O(n) by using the sorted order (or the visited/unvisited split) to rule out entire ranges of pairs at once.

Sliding window: reusing work instead of recomputing it

Imagine sliding a physical window over a strip of paper: as the window moves one step right, it loses the leftmost character and gains one new character on the right — everything in between is unchanged. A sliding-window algorithm exploits exactly that overlap instead of recomputing the whole window from scratch on every shift.

Example 1 — fixed-size window: maximum sum of any k consecutive elements:

def max_sum_subarray(nums: list[int], k: int) -> int:
    window_sum: int = sum(nums[:k])
    best: int = window_sum
    for i in range(k, len(nums)):
        window_sum += nums[i] - nums[i - k]   # add the new element, drop the old one
        best = max(best, window_sum)
    return best

Trace for nums = [2, 1, 5, 1, 3, 2], k = 3:

i	new element	dropped element	window_sum	best
init	—	—	2+1+5 = 8	8
3	1	2	8 + 1 - 2 = 7	8
4	3	1	7 + 3 - 1 = 9	9
5	2	5	9 + 2 - 5 = 6	9

Best sum is 9, from the window [5, 1, 3]. Without sliding, recomputing sum(nums[i:i+k]) on every step costs O(n·k); reusing the running total makes it O(n).

Example 2 — variable-size window: longest substring without repeating characters:

def longest_unique_substring(s: str) -> int:
    seen: set[str] = set()
    left: int = 0
    best: int = 0
    for right in range(len(s)):
        while s[right] in seen:
            seen.remove(s[left])
            left += 1
        seen.add(s[right])
        best = max(best, right - left + 1)
    return best

Trace for s = "pwwkew":

right	char	while-removals	left after	window	best
0	p	none	0	"p"	1
1	w	none	0	"pw"	2
2	w	remove p, remove w (2 iters)	2	"w"	2
3	k	none	2	"wk"	2
4	e	none	2	"wke"	3
5	w	remove w (1 iter)	3	"kew"	3

Here left only ever moves forward, so across the whole run it advances at most n times total — combined with right’s single pass, the algorithm is O(n), not the O(n²) you’d get from checking every substring.

Insight: Sliding window applies whenever you’re scanning for a contiguous run (subarray or substring) and can update a running answer incrementally instead of recomputing it. Fixed-size window: shift by one, add one, drop one. Variable-size window: grow right until a condition breaks, then shrink left until it’s satisfied again.

Prefix sums: paying once, querying free

Think of a running total on a receipt: if you keep a cumulative sum as you scan down the list, “how much did I spend between item 3 and item 7” is just one subtraction of two running totals — no need to re-add anything.

def build_prefix_sums(nums: list[int]) -> list[int]:
    prefix: list[int] = [0] * (len(nums) + 1)
    for i in range(len(nums)):
        prefix[i + 1] = prefix[i] + nums[i]
    return prefix

def range_sum(prefix: list[int], left: int, right: int) -> int:
    # sum of nums[left..right] inclusive
    return prefix[right + 1] - prefix[left]

Trace for nums = [4, 2, 6, 1, 3, 8] (building the prefix array):

i	nums[i]	prefix[i + 1]
0	4	4
1	2	6
2	6	12
3	1	13
4	3	16
5	8	24

prefix = [0, 4, 6, 12, 13, 16, 24]. Now range_sum(prefix, 1, 4) — the sum of nums[1..4] = [2, 6, 1, 3] — is prefix[5] - prefix[1] = 16 - 4 = 12, matching 2+6+1+3=12 without re-adding a single element.

Building the prefix array costs O(n) once. After that, every range-sum query costs O(1). Answering q queries naively (re-summing the range each time) costs O(n·q); with prefix sums it’s O(n + q) total.

Insight: Prefix sums are the right move whenever the underlying array is static (or rarely changes) and you’ll be asked many range-aggregate questions over it. You trade a one-time O(n) cost for O(1) answers forever after — a classic precompute-once, query-often trade.

In-place operations: trading a bit more thinking for zero extra memory

An in-place operation rearranges the existing array using only a constant amount of extra memory — O(1) auxiliary space — instead of building a second array to hold the result. It’s the difference between rearranging books on the same shelf versus needing a second shelf to stage them on.

Example — rotate an array right by k using three reversals, reusing the same two-pointer reverse from earlier:

def reverse_range(nums: list[int], start: int, end: int) -> None:
    while start < end:
        nums[start], nums[end] = nums[end], nums[start]
        start += 1
        end -= 1

def rotate_right(nums: list[int], k: int) -> None:
    n: int = len(nums)
    k %= n
    reverse_range(nums, 0, n - 1)   # reverse the whole array
    reverse_range(nums, 0, k - 1)   # reverse the first k elements back
    reverse_range(nums, k, n - 1)   # reverse the remaining elements back

Trace for nums = [1, 2, 3, 4, 5, 6, 7], k = 3:

Step	Call	Array after
0	initial	[1, 2, 3, 4, 5, 6, 7]
1	reverse_range(0, 6)	[7, 6, 5, 4, 3, 2, 1]
2	reverse_range(0, 2)	[5, 6, 7, 4, 3, 2, 1]
3	reverse_range(3, 6)	[5, 6, 7, 1, 2, 3, 4]

Result: [5, 6, 7, 1, 2, 3, 4] — correctly rotated right by 3, using only a fixed handful of variables (start, end, n, k) no matter how large nums is. Compare that to a naive nums[-k:] + nums[:-k], which is correct too but allocates a whole new list — O(n) extra memory instead of O(1).

Insight: In-place operations are built from the same primitives as two pointers — reverse_range above is exactly the swap-and-converge pattern from the two-sum example. Recognizing that composition is what lets you build “rotate,” “partition,” and “deduplicate” out of one small reusable building block instead of inventing a new trick each time.

Real-world problem

Suppose you write a script that builds a large report or log file by joining text line by line:

# Fast in testing against a short log of a few hundred lines
report = ""
for line in log_lines:          # but in production there are hundreds of thousands
    report = report + line + "\n"

With small test data it runs fine. But once it hits production with hundreds of thousands of log lines, the script slows down more and more until it nearly grinds to a halt.

Diagnosis: Concatenating strings in a loop is O(n²). Every added line forces Python to copy the entire accumulated text again. The longer the report grows, the slower each pass becomes.

Fix:

# ✅ Collect into a list, then join once — O(n)
parts: list[str] = []
for line in log_lines:
    parts.append(line)
report = "\n".join(parts)

Insight: Performance bugs hide perfectly in small datasets, then surface to hurt you in production — thinking about Big O from the start is the cheapest armor you can buy.

Beyond this one example

The four patterns above aren’t just interview tricks — they’re the same techniques production systems lean on constantly:

• Two pointers — merging two already-sorted log streams from different servers, or deduplicating a sorted batch of records before writing it to disk.
• Sliding window — rate limiters (“how many requests has this user made in the last 60 seconds”), and streaming analytics computing a moving average without re-scanning history each tick.
• Prefix sums — dashboards answering “total revenue between two dates,” precomputed nightly so every dashboard load is instant instead of re-summing millions of rows.
• In-place operations — embedded and memory-constrained systems where doubling an array’s memory footprint just to shift it isn’t an option.

Exercises

1. A script takes 0.5 seconds at n = 10,000. If the algorithm is O(n²), how long should it take at n = 100,000?

Answer

n grows 10×. For O(n²) the time grows 10² = 100×. So 0.5 × 100 = 50 seconds.

2. The code below builds a CSV from data and is very slow on large input. Identify the problem and fix it to be O(n).

csv = "id,name\n"
for row in rows:
    csv = csv + str(row.id) + "," + row.name + "\n"

Answer

Problem: csv = csv + ... concatenates strings in a loop — O(n²).

parts: list[str] = ["id,name"]
for row in rows:
    parts.append(f"{row.id},{row.name}")
csv = "\n".join(parts) + "\n"

3. You have an array of one million elements and frequently add new data. Should you use append or insert(0, x) (insert at front)? Why?

Answer

Use append — it is O(1) amortized, writing to the end without moving anyone. insert(0, x) is O(n) because every element shifts back by one each time. If you frequently add at the front, consider collections.deque, which adds to either end in O(1).

4. When n grows from 1,000 to 4,000 (a 4× increase), the running time grows from 0.1s to 1.6s. What is this algorithm’s likely Big O?

Answer

Time grows 1.6 / 0.1 = 16× when n grows 4×. 16 = 4², so it is O(n²).

5. Predict the output: trace find_pair_with_sum (the two-pointer function from this lesson) on nums = [1, 2, 4, 6, 10], target = 8. Which pair does it return, and how many comparisons does it make?

Answer

Step	left	right	sum	action
1	0 (1)	4 (10)	11	sum > target → right -= 1
2	0 (1)	3 (6)	7	sum < target → left += 1
3	1 (2)	3 (6)	8	sum == target → return (2, 6)

It returns (2, 6) after 3 comparisons — far fewer than the O(n²) pairs a nested loop would check.

6. Spot the bug (and the missed optimization) in this fixed-window max-sum attempt:

def max_sum_subarray_buggy(nums: list[int], k: int) -> int:
    best: int = 0
    for i in range(len(nums) - k):
        best = max(best, sum(nums[i:i + k]))
    return best

Answer

Two problems:

1. Off-by-one bug: range(len(nums) - k) skips the last valid window. It should be range(len(nums) - k + 1) — otherwise, for nums = [1, 2, 3], k = 2, the window starting at index 1 ([2, 3]) is never checked.
2. Missed optimization: sum(nums[i:i+k]) recomputes the whole window from scratch every iteration, costing O(n·k) total. Use the running-sum sliding-window technique from this lesson instead (add the new element, subtract the one that fell out of the window) to get O(n).

def max_sum_subarray(nums: list[int], k: int) -> int:
    window_sum: int = sum(nums[:k])
    best: int = window_sum
    for i in range(k, len(nums)):
        window_sum += nums[i] - nums[i - k]
        best = max(best, window_sum)
    return best

7. You need to answer 100,000 range-sum queries on a static array of 1,000,000 numbers (the array itself never changes). Which approach would you pick, and what’s the total time complexity?

Answer

Pick prefix sums. Build the prefix array once in O(n), then answer each of the q queries in O(1) by subtracting two prefix values. Total: O(n + q) — here roughly 1,000,000 + 100,000 operations.

The naive alternative (re-summing the requested range for every query) costs O(n · q) in the worst case — up to 10^11 operations, which would not finish in a reasonable time.

8. The rotate_right function in this lesson uses reverse_range (a two-pointer swap) three times instead of building a new list with slicing (nums[-k:] + nums[:-k]). What’s the auxiliary (extra) space complexity of each approach, and why does it matter for very large arrays?

Answer

reverse_range-based rotate_right uses O(1) auxiliary space — it only swaps elements within the existing array using a fixed number of index variables, regardless of the array’s size.

nums[-k:] + nums[:-k] is correct and simpler to read, but it builds two new slice copies and concatenates them into a brand-new list, costing O(n) extra memory. For an array with hundreds of millions of elements, that’s the difference between an operation that fits comfortably in memory and one that might not.

AI Code Critique

Critique 1. You ask an AI to write a function that joins all usernames into one comma-separated string, and it returns this:

def join_names(users: list[str]) -> str:
    output = ""
    for name in users:
        output = output + name + ", "
    return output[:-2]   # trim the trailing ", "

The code is correct, but measure its time at len(users) = 10,000 and 100,000 and watch whether the time grows quadratically. Then make it efficient.

Answer

Problem: output = output + name + ", " concatenates strings in a loop — O(n²). When n grows 10×, the time grows about 100×.

Fix it with ", ".join(), which is O(n) and easier to read:

def join_names(users: list[str]) -> str:
    return ", ".join(users)

join handles the separators between elements for you — no need to trim a trailing “, “ — and it copies the characters only once.

Critique 2. You ask an AI: “Write a function that checks whether a sorted array contains two numbers that sum to a target.” It returns this:

def has_pair_with_sum(nums: list[int], target: int) -> bool:
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return True
    return False

Read it, judge it, then improve it. What did the AI’s answer fail to use?

Answer

The code is correct — it will find the pair if one exists. The judgment call is that it’s O(n²), and it completely ignores the one piece of information the prompt handed it for free: the array is sorted. That invariant is exactly what enables the two-pointer pattern from this lesson, dropping the cost to O(n):

def has_pair_with_sum(nums: list[int], target: int) -> bool:
    left: int = 0
    right: int = len(nums) - 1
    while left < right:
        current_sum: int = nums[left] + nums[right]
        if current_sum == target:
            return True
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    return False

The lesson: an AI’s answer can be functionally correct and still miss the structural hint in the problem (sortedness, monotonicity, uniqueness) that unlocks a faster pattern. Reading for “did it notice what it was given” is a judgment skill, not a syntax one.

🎮 Game Dev: Arrays & Strings

A tilemap is nothing but a 2D array — a list of lists — so looking up the tile at (row, col) costs O(1), exactly like indexing a 1D array costs O(1). Two rectangles overlapping (an AABB check, used constantly for hitboxes and camera culling) reduces to four coordinate comparisons instead of scanning pixels, and a depth/z-order buffer is just an array indexed by draw order. Same address-math intuition from the top of this lesson, just applied twice.

Worked example — indexing a tilemap in O(1), and AABB overlap:

# ---- Represent the tilemap as a 2D array ----
ROWS: int = 5
COLS: int = 8
EMPTY: int = 0
WALL: int = 1

tilemap: list[list[int]] = [[EMPTY] * COLS for _ in range(ROWS)]
tilemap[2][4] = WALL   # place a wall at row 2, col 4

def get_tile(grid: list[list[int]], row: int, col: int) -> int | None:
    # Bounds check first — an out-of-range index would crash, not just misbehave
    if row < 0 or row >= len(grid) or col < 0 or col >= len(grid[0]):
        return None
    return grid[row][col]   # O(1): two index lookups, no scanning

def is_walkable(grid: list[list[int]], row: int, col: int) -> bool:
    tile: int | None = get_tile(grid, row, col)
    return tile is not None and tile != WALL


# ---- Bounding boxes and AABB overlap ----
class Rect:
    def __init__(self, x: int, y: int, w: int, h: int) -> None:
        self.x: int = x
        self.y: int = y
        self.w: int = w
        self.h: int = h

# ❌ Naive: walk every pixel — O(w×h)
def overlaps_naive(a: Rect, b: Rect) -> bool:
    for px in range(a.x, a.x + a.w):
        for py in range(a.y, a.y + a.h):
            if b.x <= px < b.x + b.w and b.y <= py < b.y + b.h:
                return True
    return False

# ✅ AABB — compare coordinates directly, O(1) no matter how big the boxes are
def aabb_overlap(a: Rect, b: Rect) -> bool:
    return (
        a.x < b.x + b.w and a.x + a.w > b.x and   # overlap on the x-axis?
        a.y < b.y + b.h and a.y + a.h > b.y        # overlap on the y-axis?
    )

get_tile never scans — it’s the same base + offset arithmetic from the top of this lesson, just applied to two dimensions instead of one. aabb_overlap swaps a pixel-by-pixel scan for four comparisons: two boxes fail to overlap only if one sits entirely to one side of the other on some axis, so “not separated on either axis” is exactly “overlapping.”

Figure: a 5×8 tilemap — tilemap[row][col] looks up the highlighted tile at (2, 4) in O(1).

Exercises

G1. Given the tilemap above (5 rows × 8 cols, with a wall at (2, 4)), what does get_tile(tilemap, 2, 4) return? What about get_tile(tilemap, 0, 7)?

Answer

get_tile(tilemap, 2, 4) returns 1 (WALL), since that position was explicitly set to a wall. get_tile(tilemap, 0, 7) returns 0 (EMPTY) — it’s in bounds (the last column of the first row) but was never set to a wall.

G2. Here’s a buggy get_tile that only bounds-checks the row:

def get_tile_buggy(grid: list[list[int]], row: int, col: int) -> int:
    if row < 0 or row >= len(grid):
        return None
    return grid[row][col]

What happens when you call get_tile_buggy(tilemap, 2, 20)? Fix it.

Answer

Since col is never bounds-checked, grid[row][20] raises an IndexError — each row only has 8 columns (indices 0-7). The fix is to check col too, exactly like the original get_tile:

if row < 0 or row >= len(grid) or col < 0 or col >= len(grid[0]):
    return None

G3. Trace aabb_overlap for player = Rect(10, 10, 20, 20) and enemy = Rect(25, 15, 20, 20). Do they overlap? Which of the four conditions hold?

Answer

player spans x: 10-30, y: 10-30. enemy spans x: 25-45, y: 15-35.

• a.x < b.x+b.w → 10 < 45 → true
• a.x+a.w > b.x → 30 > 25 → true
• a.y < b.y+b.h → 10 < 35 → true
• a.y+a.h > b.y → 30 > 15 → true

All four conditions hold, so aabb_overlap returns True — they overlap.

G4. You need to redraw every tile on screen, row by row, left to right. With tilemap stored row-major (tilemap[row][col], each row its own list), should your loop be for row: for col: or for col: for row:? Which is more cache-friendly, and why?

Answer

Use for row in range(ROWS): for col in range(COLS):, with col innermost. Because each row is stored as one contiguous block (row-major), walking col within a row touches consecutive memory addresses. The flipped order (for col: for row:) jumps between different rows on every single step, which misses the CPU cache far more often.

Challenge 1 — Flood-fill bounds. Write flood_fill(grid, start_row, start_col, new_tile) that fills every tile connected to (start_row, start_col) with new_tile, like the paint-bucket tool in an image editor. Watch out for two things: (1) never index outside the grid, (2) never revisit tiles you’ve already filled, or you’ll loop forever.

Approach

Use BFS/DFS with an explicit stack/queue of coordinates to visit. Before touching any coordinate, call get_tile (which already bounds-checks and returns None outside the grid) instead of indexing directly, and only fill tiles whose value still matches the original tile. Checking against the original value is exactly what prevents infinite revisits — once a tile is filled it no longer matches, so it’s skipped:

def flood_fill(grid: list[list[int]], start_row: int, start_col: int, new_tile: int) -> None:
    old_tile: int | None = get_tile(grid, start_row, start_col)
    if old_tile is None or old_tile == new_tile:
        return
    stack: list[tuple[int, int]] = [(start_row, start_col)]
    while stack:
        row, col = stack.pop()
        if get_tile(grid, row, col) != old_tile:
            continue   # out of bounds, already filled, or a different tile
        grid[row][col] = new_tile
        stack.extend([(row + 1, col), (row - 1, col), (row, col + 1), (row, col - 1)])

Challenge 2 — Sprite-sheet slicing. A sprite sheet is one big image containing many sub-sprites arranged in a row-major grid, same idea as the tilemap. Given SHEET_COLS and a fixed sprite size (TILE_W × TILE_H), write a function that takes a single linear sprite index (0, 1, 2, …) and returns the (x, y, w, h) rectangle of that sprite on the sheet, without scanning any pixels.

Approach

This is the same base + (i × size) address arithmetic from the top of this lesson, applied in two dimensions: split the linear index into a row and column with row, col = divmod(index, SHEET_COLS), then x = col * TILE_W, y = row * TILE_H. All O(1).

def sprite_rect(index: int, sheet_cols: int, tile_w: int, tile_h: int) -> Rect:
    row: int = index // sheet_cols
    col: int = index % sheet_cols
    return Rect(col * tile_w, row * tile_h, tile_w, tile_h)

Going deeper

• MIT 6.006 — Introduction to Algorithms: Lectures on arrays and dynamic arrays cover append cost and array resizing. (ocw.mit.edu)
• CLRS — Introduction to Algorithms (Cormen, Leiserson, Rivest, Stein): chapters on arrays and amortized analysis (aggregate, accounting, and potential methods in particular).
• Sedgewick & Wayne — Algorithms (4th ed.), Princeton: the chapters on elementary data structures ground the array-vs-linked-list cost table above in working Java-flavored implementations you can port directly.
• Goodrich, Tamassia & Goldwasser — Data Structures and Algorithms in Python: Chapter 5, “Array-Based Sequences,” is the Python-native treatment of exactly this lesson’s dynamic-array and amortized-append material.
• Skiena — The Algorithm Design Manual (3rd ed.): strong on the “which technique when” intuition — its treatment of two-pointer and window techniques pairs well with the worked examples above.
• Bhargava — Grokking Algorithms (2nd ed.): Chapter 2’s illustrated array-vs-linked-list comparison is the friendliest on-ramp to the trade-off table in this lesson.
• Python docs — list running times: the TimeComplexity wiki summarizes the Big O of each list operation.
• Python docs — str: the Text Sequence Type explains string immutability and the join method.