Nested loops are where a program stops being a list of steps and starts doing real work: comparing every row with every column, scanning every option against every rule. They are also where programs get slow and where break quietly does less than you expect. And Python has a loop construct that looks like a mistake until you see its purpose, a for loop with an else clause that runs only when nothing was found.
What happens when you put one loop inside another?
The outer loop runs once per item and the inner loop runs completely for each of those, so a nested loop over two collections of ten items executes a hundred iterations. That multiplication is the whole cost story, and it is why nested loops are the first thing to reconsider when a program slows down.
for row in range(3):
for column in range(4):
symbol = 'o' if (row + column) % 2 == 0 else '.'
print(symbol, end=' ')
print()
Here is the detail that catches people out: break and continue apply to the loop they sit inside, and nothing else. A break in the inner loop leaves the inner loop and carries on with the next iteration of the outer one. There is no built-in way to break out of two loops at once.
numbers = [1, 2, 3]
print('break leaves the inner loop only:')
for outer in numbers:
for inner in numbers:
print(f' outer={outer} inner={inner}')
break
print(' back in the outer loop')
How can you stop both loops at once?
There are three approaches, and the best one is usually the simplest: do not nest the loops at all. If you are looking for the first matching pair, return as soon as you find it, and the function ends with both loops gone.
def find_pair(values, target):
"""Return the first pair that adds up to target, or None."""
for index, value in enumerate(values):
for other in values[index + 1:]:
if value + other == target:
return value, other
return None
print('found ->', find_pair([3, 7, 11, 15], 26))
print('missing ->', find_pair([1, 2, 3], 100))
Returning is clean because it also carries the answer with it. The slice values[index + 1:] avoids comparing an element with itself and avoids finding the same pair twice in a different order.
When you genuinely cannot return, a flag variable is the straightforward approach: set it when you find what you are looking for, then check it after the outer loop and break. That works, and it reads worse than the version that returns. The third option, a break inside the inner loop followed by a condition check in the outer loop, is the same idea with more moving parts.
values = [3, 7, 11, 15]
target = 26
found = None
for outer in values:
for inner in values:
if outer + inner == target:
found = (outer, inner)
break
if found is not None:
break
print('flag version ->', found)
Compare that with the returning version from a moment ago and you can see why the early return is worth preferring: the flag version has to keep the answer somewhere, keep a second condition, and remember to check it after the inner loop. The returning version has one path through the code.
What is the loop-else construct, and why does it exist?
Python lets you attach an else block to a for or while loop. The block fires when the loop ends normally, and it does not run if you left the loop with break. In other words, the else block means "the loop finished without being interrupted".
def locate(values, target):
for index, value in enumerate(values):
if value == target:
print(f'found {target} at index {index}')
break
else:
print(f'{target} is not in the list')
return None
return index
print(locate([10, 20, 30], 20))
print(locate([10, 20, 30], 99))
This is exactly the shape of a search. The else block is the "not found" branch, and it replaces the flag variable that older languages force you to declare, initialise and remember to check. The while version works the same way.
attempts = 0
while attempts < 3:
attempts += 1
print('attempt', attempts)
else:
print('the loop finished without a break')
print('---')
attempts = 0
while attempts < 3:
attempts += 1
if attempts == 2:
print('stopping early')
break
else:
print('this line is skipped because we broke out')
Most people meet this construct and assume it is a mistake, because an else after a loop looks like it should mean "when the condition was false". It nearly does: the else runs when the loop ends without a break, which for a while loop means the condition became false, and for a for loop means the iterable ran out.
When should you avoid nesting loops?
Whenever the inner loop is doing a lookup that a dictionary can do for you. Searching a list of pairs for each item is quadratic work; indexing the pairs once and then looking each item up directly is linear.
rows = [('a', 1), ('b', 2), ('c', 3)]
targets = ['a', 'c', 'z']
# Nested search
found = []
for target in targets:
for name, value in rows:
if name == target:
found.append((target, value))
break
# One lookup instead
lookup = dict(rows)
found = [(target, lookup[target]) for target in targets if target in lookup]
print('found ->', found)
Two other habits keep nesting under control. Give the inner loop a meaningful name, because i and j make a three-level nest unreadable. And if you find yourself needing a third level, it is usually a sign that the data should be restructured rather than that the loop should be deeper.
It also helps to keep the inner loop's body trivial. A nested loop whose inner body spans twenty lines is hard to reason about, because you have to hold two pieces of state in your head at once. When that happens, extract the inner work into a function and call it, so each level has one job.
Your turn: find pairs in a grid
- Write a function that takes a list of numbers and a target and returns every pair that adds up to the target, using two nested loops. Print the pairs for
[3, 7, 11, 15, 20]and26. - Add a guard so the same pair is never reported twice, and confirm the count of results matches what you expect by hand.
- Rewrite the function so it returns immediately on the first match, and check that it finds the same pair as the version that collects everything.
- Now write a search function that reports "not found" using the
for ... elseconstruct rather than a flag variable, and confirm the message appears only when the item is genuinely missing. - Finally, build a small two-dimensional list of numbers, print it as a grid, and use a nested loop to find every position holding the maximum value. Print the coordinates.
Patterns to remember
- A nested loop multiplies the work: ten by ten is a hundred iterations.
breakandcontinueonly affect the loop they are written in.- Return early rather than trying to break out of two loops at once.
- A loop's
elseclause runs only when the loop finished without abreak, which makes it the natural home for "nothing was found". - Replace an inner search loop with a dictionary lookup when the inner work is really a lookup.