4.4

Nested Loops

AP Computer Science A

How nested loops work

java
for (int i = 1; i <= 3; i++) {
    for (int j = 1; j <= 4; j++) {
        System.out.print("(" + i + "," + j + ") ");
    }
    System.out.println();   // new line after inner loop finishes
}
(1,1) (1,2) (1,3) (1,4)
(2,1) (2,2) (2,3) (2,4)
(3,1) (3,2) (3,3) (3,4)

Execution order

i=1: j runs 1234, then inner loop ends
i=2: j runs 1234, then inner loop ends
i=3: j runs 1234, then inner loop ends
outer loop ends

Counting total iterations

java
for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
        // this line runs m × n times
    }
}

Classic patterns

Multiplication table

java
for (int i = 1; i <= 5; i++) {
    for (int j = 1; j <= 5; j++) {
        System.out.printf("%4d", i * j);
    }
    System.out.println();
}
   1   2   3   4   5
   2   4   6   8  10
   3   6   9  12  15
   4   8  12  16  20
   5  10  15  20  25

Right triangle of stars

java
for (int row = 1; row <= 5; row++) {
    for (int col = 1; col <= row; col++) {
        System.out.print("* ");
    }
    System.out.println();
}
*
* *
* * *
* * * *
* * * * *

Rectangle of numbers

java
for (int row = 0; row < 3; row++) {
    for (int col = 0; col < 4; col++) {
        System.out.print(row + col + " ");
    }
    System.out.println();
}
0 1 2 3
1 2 3 4
2 3 4 5

Dependent inner loops

java
for (int i = 1; i <= 4; i++) {
    for (int j = 1; j <= i; j++) {
        System.out.print(j);
    }
    System.out.println();
}
1
12
123
1234

Nested loops with Strings

Find all pairs of characters

java
String word = "CAT";
for (int i = 0; i < word.length(); i++) {
    for (int j = 0; j < word.length(); j++) {
        String pair = word.substring(i, i + 1) + word.substring(j, j + 1);
        System.out.print(pair + " ");
    }
    System.out.println();
}
CC CA CT
AC AA AT
TC TA TT

Check for duplicate characters

java
public boolean hasDuplicates(String str) {
    for (int i = 0; i < str.length(); i++) {
        for (int j = i + 1; j < str.length(); j++) {
            if (str.substring(i, i + 1).equals(str.substring(j, j + 1))) {
                return true;   // found a duplicate!
            }
        }
    }
    return false;   // no duplicates
}

hasDuplicates("hello")    // true (two l's)
hasDuplicates("world")    // false

Trace practice

java
int total = 0;
for (int i = 1; i <= 3; i++) {
    for (int j = 1; j <= i; j++) {
        total += i + j;
    }
}

while loops nested in for loops (and vice versa)

java
// for inside while
int row = 1;
while (row <= 3) {
    for (int col = 1; col <= row; col++) {
        System.out.print("X");
    }
    System.out.println();
    row++;
}
// X
// XX
// XXX

AP Exam Tips

Common Mistakes

Key Vocabulary