Complexity Drills

How to drill

Back on the warehouse floor one last time — six scenarios, six snippets. For each snippet: commit to a time and auxiliary-space answer before answering the quiz, then open the worked reasoning. If you miss one, don't just accept the answer — find which rule you misapplied (iteration count? body price? stack depth?).

Drill 1

The scenario: two separate passes over the same cart — first tallying every package's weight, then subtracting half of each one, one task after another.

def drill1(nums: list[int]) -> int:
    total = 0
    for x in nums:
        total += x
    for x in nums:
        total -= x // 2
    return total

Drill 2

The scenario: the handshake greeting, warehouse edition — every package checked against every package that comes after it, hunting for a pair that cancels out to zero.

def drill2(nums: list[int]) -> list[int]:
    out = []
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == 0:
                out.append(i)
    return out

Drill 3

The scenario: the phone-tree round shrinks by half each time, but each round still requires a full sweep of all n packages before moving to the next round.

def drill3(n: int) -> int:
    count = 0
    i = n
    while i > 1:
        for _ in range(n):
            count += 1
        i //= 2
    return count

Drill 4

The scenario: the deceptive single task — for every package, a "quick check" that secretly re-scans a whole slice of the remaining pile before moving on, exactly the hidden-scroll trap from the loops lesson.

def drill4(nums: list[int], target: int) -> bool:
    for x in nums:                 # n iterations
        if x in nums[1:]:          # slice + scan!
            pass
        if x == target:
            return True
    return False

Drill 5

The scenario: the branching-and-halving delegation — a task handed to two assistants, each getting exactly half the load, over and over.

def drill5(n: int) -> int:
    if n <= 1:
        return 1
    return drill5(n // 2) + drill5(n // 2)

Drill 6

The scenario: the grid layout — packages arranged in a full n×n storage grid, and the job is to scan every slot in every row to find the single heaviest one.

def drill6(matrix: list[list[int]]) -> int:
    n = len(matrix)        # n × n matrix
    best = matrix[0][0]
    for row in matrix:
        for value in row:
            if value > best:
                best = value
    return best