CATEGORY 5 OF 13

Iteration Patterns

Master the loop patterns that form the backbone of every algorithm: single passes, nested loops, two-pointer scans, accumulators, and early termination strategies.

Time: O(n) to O(n²) depending on pattern

Space: O(1) to O(n) depending on output

Learn & Reference

Understanding the Pattern

Iteration Patterns

Every algorithm ultimately boils down to how you loop through data. Understanding common iteration patterns lets you decompose problems into familiar building blocks instead of reinventing the wheel each time.

Core Loop Types

Single Pass (Linear Scan)

The most common pattern: iterate through an array once, building up a result. Used for sums, max/min, counting, filtering, and transformations.

Nested Loops

When you need to compare every pair of elements, or process a 2D structure. The key is knowing when O(n²) is unavoidable vs. when a hash map or sorting can eliminate the inner loop.

Accumulator Pattern

Carry a running value through the loop — a sum, product, max, or any aggregate. Initialize before the loop, update inside, return after.

Early Termination

Break out of a loop as soon as you find your answer. Don't scan the remaining elements if you already know the result.

Enumerate / Index Tracking

Often you need both the element AND its position. Use enumerate() (Python), index-based for loops, or range with index.

Zip / Parallel Iteration

Process two sequences in lockstep. Useful for comparing arrays element-by-element, merging sorted lists, or pairing related data.

Key Principles

Choose the simplest loop — a single for loop is clearer than while with manual index management
Avoid unnecessary work — if you can break early or skip irrelevant elements, do it
Track what you need — decide upfront whether you need the index, the value, or both
Watch boundary conditions — off-by-one errors are the #1 loop bug. Always verify the first and last iterations manually

Common Mistakes

Off-by-one errors: Using < vs <=, or starting at 0 vs 1. Always trace through the first and last iterations
Modifying a collection while iterating: Adding or removing elements during a for-each loop causes bugs. Build a new collection instead
Unnecessary nested loops: Many O(n²) solutions can be reduced to O(n) with a hash map or sorting
Forgetting to initialize the accumulator: Starting a sum at 0, a product at 1, or a min at infinity
Infinite loops: Forgetting to update the loop variable in a while loop, or using the wrong termination condition

When to Use

Process every element in a collection

Find a pair or combination satisfying a condition

Build a running total, product, or aggregate

Compare two arrays element by element

Generate a 2D structure like Pascal's triangle or a spiral

Need to stop as soon as a condition is met

Template

1# Iteration Patterns
2# for x in arr:           — iterate values
3# for i, x in enumerate:  — index + value
4# for a, b in zip(l1, l2): — parallel iteration
5
6def solve(arr):
7    result = 0
8    for x in arr:
9        result += x
10    return result

{ }

Syntax Reference

1# === Basic for loop ===
2for x in arr:              # iterate values
3for i in range(len(arr)):  # iterate indices
4for i, x in enumerate(arr): # both index and value
5
6# === While loop ===
7i = 0
8while i < len(arr):
9    i += 1
10
11# === Range variations ===
12range(5)          # 0, 1, 2, 3, 4
13range(2, 8)       # 2, 3, 4, 5, 6, 7
14range(0, 10, 2)   # 0, 2, 4, 6, 8
15range(5, 0, -1)   # 5, 4, 3, 2, 1
16
17# === Zip (parallel iteration) ===
18for a, b in zip(list1, list2):  # pairs from two lists
19for i, (a, b) in enumerate(zip(l1, l2)):  # with index
20
21# === List comprehensions ===
22[x * 2 for x in arr]                    # transform
23[x for x in arr if x > 0]               # filter
24[x * 2 for x in arr if x > 0]           # both
25
26# === Built-in aggregates ===
27sum(arr)           # sum of elements
28max(arr)           # maximum
29min(arr)           # minimum
30any(x > 0 for x in arr)  # True if any match
31all(x > 0 for x in arr)  # True if all match

📋

Common Recipes

1# --- Running Sum ---
2def running_sum(arr):
3    result = []
4    total = 0
5    for x in arr:
6        total += x
7        result.append(total)
8    return result
9
10# --- Zip Two Lists ---
11def zip_merge(a, b):
12    return [[x, y] for x, y in zip(a, b)]
13
14# --- Sliding Window Average ---
15def sliding_avg(arr, k):
16    result = []
17    window_sum = sum(arr[:k])
18    result.append(window_sum / k)
19    for i in range(k, len(arr)):
20        window_sum += arr[i] - arr[i - k]
21        result.append(window_sum / k)
22    return result
23
24# --- Pascal's Triangle ---
25def pascal(n):
26    tri = [[1]]
27    for i in range(1, n):
28        prev = tri[-1]
29        row = [1]
30        for j in range(1, i):
31            row.append(prev[j-1] + prev[j])
32        row.append(1)
33        tri.append(row)
34    return tri

O(n)

Complexity

Pattern	Time	Notes
Single pass	O(n)	One loop through the data
Nested loops (all pairs)	O(n²)	Every pair of elements
Triple nested	O(n³)	Rare — usually avoidable
Accumulator (sum/max/min)	O(n)	Single pass with running value
Zip / parallel scan	O(min(m,n))	Stops at shorter sequence
Sliding window (fixed)	O(n)	Maintain window sum/state
Build 2D (n rows, m cols)	O(n×m)	E.g., Pascal triangle, matrix

Watch Out

✗Off-by-one errors: Using `<` vs `<=`, or starting at 0 vs 1. Always trace through the first and last iterations
✗Modifying a collection while iterating: Adding or removing elements during a for-each loop causes bugs. Build a new collection instead
✗Unnecessary nested loops: Many O(n²) solutions can be reduced to O(n) with a hash map or sorting
✗Forgetting to initialize the accumulator: Starting a sum at 0, a product at 1, or a min at infinity
✗Infinite loops: Forgetting to update the loop variable in a while loop, or using the wrong termination condition

PRACTICE PROBLEMS

Hash Map Basics

Conditionals & Logic