Nested loops

Why this matters

Many problems have two directions. A table has rows and columns. A calendar has weeks and days. A chess board has eight files and eight ranks. A list of students compared with every other student needs every pair of names. One loop walks one direction. To cover two directions, you put a second loop inside the first. This is a nested loop, and it is the structure behind grids, patterns, pair comparisons and the simple sorting algorithms.

Nested loops also bring the first real cost problem in this module. Each extra loop multiplies the work, not adds to it. Learning to count that work, and to say it in the language interviewers use, is as important as writing the loops themselves.

Start from the first principle: one full run per outer pass

A nested loop is a loop placed in the body of another loop. The outer loop controls the big steps. The inner loop controls the small steps, and it runs from start to finish for every single pass of the outer loop.

Picture a list of four rows, each with three boxes. You fill row 1 box by box, then row 2 box by box, then row 3, then row 4. You do not fill box 1 of every row first. The inner loop is "fill the boxes in this row", and the outer loop is "go to the next row". Each pass of the outer loop finishes one row completely before the next row starts.

That order is the key to reading any nested loop. Before you think about the code, ask: what does one pass of the outer loop do? The answer is always "run the whole inner loop once", plus any work the outer body does before or after it.

An everyday analogy: the clock

A clock has an hour hand and a minute hand. The minute hand goes all the way around, from 0 to 59, and then the hour hand moves forward by one. The minute hand then goes all the way around again. For each hour, the minutes run through their full cycle. The hour is the outer loop, and the minute is the inner loop.

A clock also shows the cost of nesting. Twelve hours with sixty minutes each is 720 minute steps. The minute loop does its work many times, once for each hour. If you added a third loop for seconds, the work would multiply again, to 43,200 steps for twelve hours. Each new nested loop multiplies the total.

The precise version

Here is the shape:

for each row:                 (outer loop)
    for each column:          (inner loop)
        do the work
    finish the row            (outer body, after the inner loop)

The inner loop must have its own counter. If the inner loop used the same name as the outer loop, the inner counter would overwrite the outer one, and the outer loop would finish too early or never finish. The compiler allows a second int i inside the body of a loop that has its own int i, but it creates a new variable that hides the first one. With -Wshadow, GCC warns about it:

warning: declaration of 'i' shadows a previous local [-Wshadow]

The safe habit is to use i for the outer loop and j for the inner loop, or row and col when the meaning is clearer. Each name should say what it counts.

The picture below shows a grid of four rows and four columns. The numbers show the order in which the nested loops visit each cell. The inner loop finishes each row before the outer loop moves to the next.

Grid of four by four cells numbered in the order that nested loops visit them, row by row, with the inner loop finishing each row first

What happens inside

The computer does not treat the inner loop as special. It runs the start, test and update of the inner loop again every time the outer body reaches it. Look at this fragment:

for (int i = 1; i <= 3; i++) {
    for (int j = 1; j <= 2; j++) {
        // work
    }
}

The inner loop begins with int j = 1 every time. When the outer loop moves from i = 1 to i = 2, the inner loop's start runs again, and j is set back to 1. The variable j is created fresh for each inner loop run, and it disappears when that run ends. That is why the inner loop always starts from the beginning.

Trace it step by step. The outer counter i takes the value 1. The inner counter j runs through 1 and 2, and the inner loop ends. Then i becomes 2. The inner loop starts again with j at 1, runs through 1 and 2, and ends. Then i becomes 3, and the same thing happens. In total the work runs 3 times 2, which is 6 times.

Counting the work

If the outer loop runs a times and the inner loop runs b times, the inner body runs a * b times. When both loops go up to n, the inner body runs n * n times. That number is what interviewers mean when they say a nested pair of loops is O(n squared), or quadratic. The letter n stands for the size of the input, and the word "squared" means the work grows with the square of the size.

Here is what that growth means in practice. With n equal to 10, the inner body runs 100 times. With n equal to 1000, it runs a million times. With n equal to 100000, it runs ten billion times, which is far too slow for a one-second limit on a typical computer. A program that is fast for small inputs can fail completely on larger ones.

Not every pair of nested loops does n times n work. A common shape starts the inner loop where the outer one is. Look at the triangle below. The outer loop counts rows, and the inner loop runs once more on each row than on the row before.

Triangle of dots with four rows, where row one has one dot and row four has four dots, showing the inner loop running one, two, three and four times

For rows 1 to 4, the inner loop runs 1, 2, 3 and 4 times. The total is 1 + 2 + 3 + 4, which is 10. In general, when the inner loop runs i times on pass i for i from 1 to n, the total is n times (n + 1) divided by 2. That formula is still O(n squared), because the largest term grows with the square. The division by 2 changes the constant, not the growth. Interviewers accept either form, but the formula shows that you can count the work exactly.

Worked example 1: a multiplication grid

The first program prints a 4 by 4 grid of products. The outer loop prints one row. The inner loop prints one cell in that row. The setw function from the <iomanip> header sets the width of the next printed value, so the columns line up. The number 4 in setw(4) means "use at least four characters for this value", and smaller numbers are padded with spaces on the left.

This program needs no input. Press Run.

The output is:

   1   2   3   4
   2   4   6   8
   3   6   9  12
   4   8  12  16

Notice where endl sits. It is in the outer body, after the inner loop has finished. If you moved it inside the inner loop, every number would sit on its own line. This is one of the most common errors in grid printing, and it is covered in the mistakes section below.

Trace the first row. The outer counter i is 1. The inner loop prints 1 * 1, 1 * 2, 1 * 3 and 1 * 4, each in a field four characters wide. Then endl moves to a new line. The second row starts with i equal to 2, and the inner loop starts again from j equal to 1.

The pattern is the same for any grid: an outer loop over rows, an inner loop over columns, the work in the inner body, and the line break in the outer body. Learn this template. You will write it again for matrices, board games and image processing.

Worked example 2: a triangle whose width depends on the row

The inner limit does not have to be a fixed number. It can depend on the outer counter. This is what makes triangle patterns possible. The next program reads the number of rows from the input and prints a triangle of stars, where row r has r stars.

Type 4 into the Input box.

For the input 4, the output is:

*
**
***
****

The inner test is c <= r. On row 1, the inner loop runs once. On row 2, it runs twice. The inner loop's limit grows with the outer counter, so each row is one star longer than the row before. This is the same triangle counting shown in the diagram above.

The key idea is that the inner loop reads the outer variable. The outer variable is a fixed value for the whole inner loop, so the inner loop has a steady target on each row. Use this whenever a pattern grows by one each row.

Worked example 3: listing every pair once

Many problems ask you to compare every pair of items. The trap is that a pair such as (2, 3) and (3, 2) is the same pair listed twice. To list each pair once, let the inner loop start one position after the outer loop. Then the inner counter is always larger than the outer, and no pair appears in both orders.

Type 4 into the Input box. The program lists every pair of the numbers 1 to 4 and counts them.

The output for 4 is:

(1,2) (1,3) (1,4) (2,3) (2,4) (3,4) 
pairs: 6

Trace the outer loop. When i is 1, the inner loop starts at j equal to 2 and prints (1,2), (1,3) and (1,4). When i is 2, the inner loop starts at 3 and prints (2,3) and (2,4). When i is 3, it prints (3,4). When i is 4, the inner loop starts at 5, which is past n, so it does not run at all.

The count is 3 + 2 + 1 = 6. In general, with n items there are n times (n minus 1) divided by 2 pairs. That is the same triangular total as before, now used for a counting question. Notice that the inner loop starting at i + 1 is what halves the work compared with the full n times n. The loops are still O(n squared) in the worst case, but the constant is smaller.

This pattern is so common that you should be able to write it from memory: the outer loop starts at the first item, and the inner loop starts one after the outer counter.

Worked example 4: a table of primes

The next program puts a loop inside a loop in a different way. The outer loop tests every number from 2 up to a limit. The inner loop tries each divisor for that number. If a divisor is found, the number is not prime, and the inner loop stops early with break. This is a nested search, with the inner loop doing the test for each outer value.

Type 30 into the Input box.

The output for 30 is:

2 3 5 7 11 13 17 19 23 29 

The inner loop has the condition d * d <= n. It stops at the square root of n, because any divisor larger than the square root pairs with a smaller one that was already tested. This is the same idea used in the classic problems lesson, now inside a larger loop.

The work here is harder to count than in the grid example. For each n, the inner loop runs about the square root of n times, and it stops early for most composite numbers. A full analysis is beyond this lesson, but you can say that the work is roughly the sum of the square roots, and that it is much less than n squared. When an interviewer asks, describe the inner loop's upper bound and why it is the square root.

Worked example 5: bubble sort

The first sorting algorithm most programmers learn is bubble sort. It is built from two nested loops. The outer loop runs a series of passes, and each pass walks along the array, comparing neighbours and swapping them if they are in the wrong order. Each pass pushes the largest remaining value to the end, like a bubble rising to the top of water. The next pass ignores the values already at the end.

The inner loop compares a[j] with a[j + 1]. If the left value is bigger, the two swap. The inner loop's upper limit shrinks by one on each pass, because the last pass positions already hold the largest values in their final places.

Study the program first, then run it. It prints the array after each pass, so you can see the sort happen.

The output is:

after pass 1: 1 4 2 5 8
after pass 2: 1 2 4 5 8
after pass 3: 1 2 4 5 8
after pass 4: 1 2 4 5 8

Trace the first pass by hand. The array starts as 5, 1, 4, 2, 8. The inner loop compares 5 and 1: they are out of order, so they swap, and the array is 1, 5, 4, 2, 8. It compares 5 and 4 and swaps, giving 1, 4, 5, 2, 8. It compares 5 and 2 and swaps, giving 1, 4, 2, 5, 8. It compares 5 and 8, which are in order, so nothing changes. At the end of the pass, the largest value, 8, is in its final place at the end. The output line for pass 1 shows the array after this pass.

Pass 2 uses a shorter inner loop, because the last position is already final. It compares 1 with 4 (no swap), then 4 with 2 (swap), and then 4 with 5 (no swap). The array becomes 1, 2, 4, 5, 8. Passes 3 and 4 make no swaps at all. The array is already sorted, but the program still runs the remaining passes. That waste is the reason for the improvement described below.

Now watch the same sort in the visualizer. Each step shows the two values being compared, and the swaps as they happen.

Count the work. With n values, the first pass compares n - 1 pairs, the second n - 2, and so on, down to 1. The total number of comparisons is (n - 1) + (n - 2) + ... + 1, which equals n times (n minus 1) divided by 2. For five values that is 10 comparisons. The time is O(n squared) in the worst case, and it is O(n squared) on average too. The space is O(1), because the only extra variable is tmp.

There is a useful improvement. If a whole pass makes no swaps, the array is sorted, and the loop can stop. You add a flag that is set to true when a swap happens, and you check it in the outer loop. With that change, a sorted input takes one pass, which is O(n). The worst case stays O(n squared), so interviewers ask about both cases. Know both.

Worked example 6: selection sort

Selection sort uses the same two nested loops, but it is organised differently. Instead of swapping neighbours, it finds the smallest value in the rest of the array and swaps it into place. Each outer pass fixes one more position from the left. Selection sort does far fewer swaps than bubble sort, which can matter when a swap is expensive.

The outer counter i is the position being fixed. The inner loop searches from i + 1 to the end for the smallest value, and keeps the index of the smallest value found so far in smallest. After the inner loop, the program swaps that value into position i, but only if it is not already there.

The output is:

after step 1: 1 5 4 2 8
after step 2: 1 2 4 5 8
after step 3: 1 2 4 5 8
after step 4: 1 2 4 5 8
swaps: 2

Trace the first step. The position being fixed is 0, and smallest starts at 0. The inner loop checks positions 1 to 4. The value 1 at position 1 is smaller than 5, so smallest becomes 1. The values 4, 2 and 8 are not smaller than 1, so smallest stays at 1. The program swaps positions 0 and 1, giving 1, 5, 4, 2, 8. That is one swap.

Step 2 fixes position 1. The smallest value in positions 1 to 4 is 2, at position 3, so the program swaps positions 1 and 3, giving 1, 2, 4, 5, 8. Step 3 finds that 4 at position 2 is already the smallest of its range, so no swap happens. Step 4 does the same. The total is two swaps, against the four swaps that bubble sort used on the same input.

Watch the selection in the visualizer. Notice that the search ranges shrink from the left, and that a swap happens only when the smallest value is not already in place.

The work is the same as bubble sort: about n times (n minus 1) divided by 2 comparisons, so the time is O(n squared) in every case. Selection sort always does the full search, even on a sorted input, so it has no fast best case like bubble sort with a flag. Its advantage is the small number of swaps. Its disadvantage is that it does not finish early. Interviewers like to ask which one you would choose, and the right answer depends on what the program needs.

Breaking out of nested loops

As you learned in the previous lesson, break leaves only the innermost loop. In a nested loop, the outer loop keeps going after the inner break. When you need to stop both loops, use a flag that the outer loop's test checks, or put the loops in a function and use return. The pair search in the previous lesson shows the flag technique. Do not expect a single break to end both loops.

A method for pattern problems

Pattern problems look hard at first, but they reduce to one template. Count the rows. For each row, count what happens in that row. Then decide what the row's counts depend on. Most patterns depend on the row number in one of three ways:

• The number of items is fixed, as in the multiplication grid.
• The number of items equals the row number, as in the triangle.
• The number of items equals the total minus the row number, as in an inverted triangle.

Write the outer loop first, with the right number of rows. Then write the inner loop with the limit that depends on the row. Put any spaces or other characters in their own inner loops before the stars, so each row is built from clear parts. Test with the smallest case, which is one row, and with the largest row you need.

Common mistakes and the messages you will see

A missing closing brace. Nested loops have many braces, and one missing brace is easy to make. The compiler reports the problem at the end of the file:

error: expected '}' at end of input
note: to match this '{'

The note points to the opening brace that has no partner. Count the braces in each loop, and check the closing brace of every loop, not only the last one.

The same name in nested loops. The compiler allows it, but the inner variable hides the outer one. With -Wshadow GCC warns about it. The program below was meant to print each outer value, but it prints 1 2 1 2 1 2 , because the inner i is a new variable that goes from 1 to 2, and the outer value is never printed:

for (int i = 1; i <= 3; i++) {
    for (int i = 1; i <= 2; i++) {
        cout << i << " ";
    }
}

Give each loop its own name. The warning is declaration of 'i' shadows a previous local.

The endl in the wrong place. Putting the line break inside the inner loop prints one value per line instead of a grid. Put endl after the inner loop, in the outer body.

A forgotten reset. If you declare the inner counter outside the outer loop, it keeps its value from the previous row, and the inner loop may run zero times on later rows. Declare the inner counter inside the inner loop's header, so it is reset each time.

An inner start that counts the diagonal. The pair count from worked example 3 would be wrong if the inner loop started at j = i. That version includes the pairs (1,1), (2,2) and so on, and the count becomes 10 for n equal to 4 instead of 6. The debugging walkthrough below shows the same bug.

Modifying the outer counter in the inner loop. A statement such as i++ inside the inner body changes the outer loop's position, and the rows will not match what you expect. Keep each counter changed only by its own loop.

Work that grows too fast. Two nested loops over one million items means a trillion steps, which is far too slow. When a problem has large input, ask whether a single loop, a sorted array or a better data structure can avoid the inner loop.

Debugging walkthrough: a pair count that is too large

Here is a program that should count the pairs of positions for four items. The answer should be 6, but it prints 10:

Run it and see the output is 10. Do not guess. Trace the first two outer passes. When i is 1, the inner loop starts at j = 1, so it counts 4 values, including the pair (1,1). When i is 2, it starts at 2 and counts 3 values, including (2,2). The inner loop counts the diagonal, where a position is paired with itself.

The fix is to start the inner loop at i + 1, so the diagonal is never counted:

for (int j = i + 1; j <= n; j++) {

With that change, the count is 6, which matches the 3 + 2 + 1 total. The bug was a single number in the inner start. When a count is off by a fixed amount such as n, suspect a starting value that is one off or includes an extra case.

Variations and edge cases

A zero count for the outer loop. If the outer limit is 0, the inner loop never runs. A grid with zero rows is empty, which is correct. Check your loops with the smallest input, which is often zero.

A zero count for the inner loop. The inner loop can run zero times on some rows. In the triangle, the inner loop with c <= r always runs at least once, but the pair loop with j = i + 1 runs zero times for the last item. That is correct, and the count formula handles it.

Three levels. A third loop inside the second gives n cubed steps. Three nested loops over 100 items is one million steps, which is fine, but over 1000 items it is a billion, which is too slow. Recognise the power of the nesting depth when you estimate the cost.

A flag for early exit. Bubble sort with a swapped flag stops as soon as a pass makes no swaps. That changes the best case from n squared to n, but the worst case stays n squared.

Loops that depend on each other. The inner limit can depend on the outer counter in any way you like, as long as the result is a valid count. A limit that goes below zero makes the inner loop run zero times, which is usually what you want.

Interview questions this lesson prepares you for

What is the time complexity of two nested loops over n items? It is O(n squared) when the inner loop runs n times on every pass. If the inner loop starts at the outer counter, the total is about n squared divided by 2, which is still O(n squared). Say both, and explain the difference.

Describe bubble sort and its complexity. Two loops, a shrinking inner range, and a swap of neighbours. O(n squared) worst case, O(n) best case with the early-exit flag, O(1) extra space. Mention that it is simple but slow, and that it is useful for teaching.

Why does selection sort do fewer swaps than bubble sort? It swaps once per pass, the smallest value into place, rather than swapping every out-of-order neighbour. Both still do about n squared comparisons.

Print all pairs of an array whose values add up to a target. Use the pair loop with the inner start at i + 1. The time is O(n squared), and say that a sorted array allows a faster method, which lesson 5 covers.

Real-world uses

A spreadsheet recalculates each cell by looking at a row and a column, which is a nested loop over the grid. An image filter visits every pixel by its row and column, and a blur looks at neighbours inside a small inner window. A timetable checks every pair of classes for a clash. A sorting routine in a basic library can use the same structure as bubble sort for small lists. Each of these uses the same two-loop template, with the inner loop reading the outer position when it needs to.

The cost lesson is that nested loops are fine for small inputs and dangerous for large ones. A program that compares every pair of a million records will not finish. Experienced programmers look for a way to avoid the inner loop before they write it, often with sorting, a hash table or a sweep from both ends.

Practice

Write each program and predict its output before you run it. Hidden solutions are under each exercise.

1. Print a rectangle of stars that is 3 rows high and 5 columns wide. Hint: the outer loop prints the rows, and the inner loop prints five stars before each endl.

#include <iostream>
using namespace std;
 
int main() {
    for (int r = 0; r < 3; r++) {
        for (int c = 0; c < 5; c++) {
            cout << "*";
        }
        cout << endl;
    }
    return 0;
}

2. Print an inverted triangle of stars with 4 rows: the first row has 4 stars, the next has 3, and so on down to 1. Hint: the inner limit is the row count minus the row number.

#include <iostream>
using namespace std;
 
int main() {
    for (int r = 1; r <= 4; r++) {
        for (int c = 1; c <= 5 - r; c++) {
            cout << "*";
        }
        cout << endl;
    }
    return 0;
}

3. Read a number n and print the multiplication table from 1 to n, one row per number, with each row showing the products from 1 to n. Use setw(4). Hint: this is the grid from worked example 1, with the size taken from the input.

#include <iostream>
#include <iomanip>
using namespace std;
 
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cout << setw(4) << i * j;
        }
        cout << endl;
    }
    return 0;
}

4. Count how many pairs of numbers from 1 to n add up to exactly n, using each pair once with i < j. For n equal to 6, the pairs are (1,5), (2,4), and the answer is 2. Hint: the inner loop starts at i + 1.

#include <iostream>
using namespace std;
 
int main() {
    int n;
    cin >> n;
    int count = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (i + j == n) {
                count++;
            }
        }
    }
    cout << count << endl;
    return 0;
}

5. Print every row of Pascal's triangle up to row 5. The first and last value of each row are 1, and each middle value is the sum of the two values above it. The rows are 1, 1 1, 1 2 1, 1 3 3 1, and 1 4 6 4 1. Hint: store the previous row in an array and build the next row from it.

#include <iostream>
using namespace std;
 
int main() {
    int row[6] = {1, 0, 0, 0, 0, 0};
    for (int r = 0; r < 5; r++) {
        for (int c = r; c >= 1; c--) {
            row[c] = row[c] + row[c - 1];
        }
        for (int c = 0; c <= r; c++) {
            cout << row[c] << (c == r ? "" : " ");
        }
        cout << endl;
    }
    return 0;
}

6. Read n numbers and print the number of times the first value appears in the whole list, including itself. Use nested loops only if you need them, and compare the answer with a single loop. For the input 4 2 7 2 9 the answer is 2. Hint: one loop is enough, because you only compare each value with the first.

#include <iostream>
using namespace std;
 
int main() {
    int n;
    cin >> n;
    int a[100];
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] == a[0]) {
            count++;
        }
    }
    cout << count << endl;
    return 0;
}

7. Print every pair of positions (i, j) with i < j in an array of five values, and print how many there are. For five values the count is 10. Hint: this is the pair listing from worked example 3, with the values taken from an array.

#include <iostream>
using namespace std;
 
int main() {
    int n = 5;
    int count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            cout << "(" << i << "," << j << ") ";
            count++;
        }
    }
    cout << endl << count << endl;
    return 0;
}

8. Count the swaps that bubble sort makes on the array 4 3 2 1. The answer is 6. Hint: count the swaps in each pass and add them up, or count the inversions, which are pairs that are out of order.

9. The program below should print a 3 by 3 grid of products, one row per line. It prints nine lines instead. Find the bug and fix it. Hint: look at where endl sits.

for (int i = 1; i <= 3; i++) {
    for (int j = 1; j <= 3; j++) {
        cout << i * j << " ";
        cout << endl;
    }
}

10. Explain in plain words why bubble sort on an already sorted array does roughly n squared comparisons, and how a swapped flag makes it do about n comparisons instead.

What you now know

• A nested loop runs its inner loop from start to finish once for every pass of the outer loop. The inner loop starts again each time.
• Use different counter names in nested loops, and put endl after the inner loop, not inside it.
• If the outer loop runs a times and the inner loop runs b times, the inner body runs a * b times. Two loops over n items is O(n squared).
• An inner loop that starts at i + 1 lists each pair once, and its total is about n times (n minus 1) over 2.
• Bubble sort and selection sort are two nested loops. Bubble sort swaps neighbours and can stop early with a flag. Selection sort swaps the smallest value into place and does fewer swaps.
• Before you write a nested loop, ask whether one loop already gives the answer. Nested loops multiply the work, and large inputs make that expensive.