Nested Iteration Optimization (Avoiding accidental O(n²))

Nested loops can mean O(n²) or worse—optimize by reordering, hashing inner lookups, sorting + two pointers, or mathematical closed forms when the inner scan is redundant.

Why this shows up in the real world

Collision detection uses spatial hashing to avoid all-pairs checks. Join algorithms in databases replace naive nested loops with index seeks.

Core idea (explained for students)

Replace for i: for j: if a[i]==b[j] with counting keys in a dict from b then single pass over a. Turn inner linear search into O(1) or O(log n).

Try this in Python

def count_pairs_sum_to_target(a: list[int], t: int) -> int:
    seen: dict[int, int] = {}
    c = 0
    for x in a:
        c += seen.get(t - x, 0)
        seen[x] = seen.get(x, 0) + 1
    return c


print(count_pairs_sum_to_target([1, 2, 3, 4, 3], 6))

Common mistakes

• Still quadratic if you sort inside the outer loop each iteration.
• Off-by-one when early-breaking inner loop changes outer assumptions.

Key takeaways

• Profile with input size pairs where naive dies first.
• Learn the handful of standard reductions (two-sum style).