050. Nested Loops

RAM Manager: Multi-Process Analysis

Aryan’s RAM manager now collects data over time — a 2D structure where each row is a time snapshot and each column is a process:

snapshots = [
    [544, 398, 256],   # t=0: chrome, python3, slack (MB)
    [612, 401, 260],   # t=1
    [580, 390, 0],     # t=2: slack crashed (0 MB)
]

He needs to flatten the snapshots into a single list, sum all values, and count processes that crashed (0 MB). Nested loops traverse this 2D data — outer loop for time snapshots, inner loop for processes within each snapshot.

The flatten function has a classic bug: result = row replaces the entire accumulator with the current row on each iteration, so only the last row survives.

💡 Fun fact: The time complexity of nested loops multiplies rather than adds — two loops each of size n give O(n²), not O(2n). This is why the famous bubble sort algorithm (two nested loops comparing adjacent elements) becomes unusably slow on large datasets, while algorithms like merge sort use a divide-and-conquer approach to achieve O(n log n). Understanding nested loop complexity is the first step toward writing algorithms that actually scale.

⚠️ Watch out: result = row vs result += row vs result.append(val) are three completely different operations that look deceptively similar. result = row replaces the list; result += row extends it with all of row’s elements; result.append(row) adds row as a nested list rather than flattening it. Getting these wrong produces subtly different wrong answers with no error.

🤔 Think about it: Flattening a matrix with nested loops is O(r×c). Python also has `[val for row in matrix for val in row]` — a single list comprehension that does the same thing. Is there a performance difference, and in what situation would the explicit nested `for` loop be preferable to the comprehension?

Learning objectives

Write nested for loops to traverse 2D data
Accumulate results from all elements of a matrix
Debug nested loop bugs (replacing vs appending)

Key concepts

nested loops
matrix
2D iteration

Try it

Concept detail

Nested loops have an outer loop and one or more inner loops. For a matrix with r rows and c columns, the body runs r*c times total.

for row in matrix: # runs r times for val in row: # runs c times per outer iteration process(val) # runs r*c times total

Time complexity: O(r*c) for 2D traversal, O(n³) for a 3D structure. Nested loops are the natural way to handle 2D data.

Common bug — replace vs append: result = row # WRONG: replaces accumulator, only last row survives result.extend(row) # RIGHT: adds all elements from row to result result += row # RIGHT: same as extend (list + list) result.append(val) # RIGHT: in inner loop, appends one element at a time

break in nested loops only exits the INNER loop: for row in matrix: for val in row: if val == target: break # exits inner loop, outer loop continues! To exit both loops from inside: use a function and return.

List comprehension alternative for simple nested loops: flatten = [val for row in matrix for val in row] This reads: “for each row in matrix, for each val in that row, collect val”

Solution

def flatten(matrix):
    result = []
    for row in matrix:
        for val in row:
            result.append(val)
    return result

def matrix_sum(matrix):
    total = 0
    for row in matrix:
        for val in row:
            total += val
    return total

def count_zeros(matrix):
    count = 0
    for row in matrix:
        for val in row:
            if val == 0:
                count += 1
    return count

Tests

M = [[1, 2, 3], [4, 0, 6], [7, 8, 0]]

def test_flatten():
    assert flatten(M) == [1, 2, 3, 4, 0, 6, 7, 8, 0]

def test_flatten_all_rows():
    # broken code: result = row replaces result, so only last row survives
    result = flatten(M)
    assert len(result) == 9, f"Got {len(result)} elements — broken code returns only last row (3 elements)"

def test_flatten_single_row():
    assert flatten([[1, 2, 3]]) == [1, 2, 3]

def test_flatten_empty():
    assert flatten([]) == []

def test_matrix_sum():
    assert matrix_sum(M) == 31

def test_count_zeros():
    assert count_zeros(M) == 2

def test_count_zeros_none():
    assert count_zeros([[1, 2], [3, 4]]) == 0

def test_count_zeros_all():
    assert count_zeros([[0, 0], [0, 0]]) == 4