Nested Loops and Patterns

New words in this topic, in plain English. Come back here whenever one feels fuzzy.

Nested loop

A loop placed inside the body of another loop.

Outer loop

The enclosing loop. It moves one step at a time.

Inner loop

The loop inside. It runs completely for every single step of the outer loop.

Row and column

Positions in a grid: rows go down, columns go across.

Pair

Two different elements taken together, like (3, 8). n items have n(n-1)/2 unordered pairs.

Time complexity

How the amount of work grows as the input grows. Two nested loops over n items usually mean n² work, written O(n²).

printf

A print method that formats values with a template, like %4d for 'an integer in a field 4 characters wide'.

1. 1

   Flip the triangle

   In 'Four classic patterns', make the right triangle upside down (4 stars first, 1 last) by changing only the inner loop's bound. Hint: row i should print n - i + 1 stars.

2. 2

   Predict the count

   Add n = 2000 to sizes in 'Counting the work'. Predict full and pairs before running (4,000,000 and 1,999,000).

3. 3

   Make a diamond

   Below the pyramid, add a second loop that counts i down from n - 1 to 1 with the same body. Together they print a diamond.

Errors are the best teachers. Make each change, read the error, guess what went wrong, then reveal the answer.

public class Main {
    public static void main(String[] args) {
        int j = 0;
        for (int i = 1; i <= 3; i++) {
            for (; j < 3; j++) {
                System.out.print("*");
            }
            System.out.println(" row " + i);
        }
    }
}

public class Main {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3};
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < 3; i++) {
                System.out.println(arr[i]);
            }
        }
    }
}

1. 1

   With an outer loop of R iterations and an inner loop of C, the inner body runs R × C times. For a square of size n that's n², so doubling n makes the work four times bigger. This is your first taste of time complexity, which the DSA course (/dsa) builds on.

2. 2

   The usual reading for printing: the outer loop picks the row, the inner loop prints the columns of that row, and a println() after the inner loop ends the line. Almost every pattern question is solved by working out, for row i, how many spaces and how many symbols to print.

3. 3

   The inner loop's bounds may depend on the outer variable: for (int j = 0; j <= i; j++) prints a growing triangle, and for (int j = i + 1; j < n; j++) visits each pair once (n(n-1)/2 times instead of n²).

4. 4

   Use different names for each level (i/j, or row/col) and declare each counter in its own loop header. Two classic bugs: incrementing the wrong variable in the inner header (j < n; i++), and declaring the inner counter outside the outer loop so it never resets.

5. 5

   A plain break or continue only affects the innermost loop. To stop both loops, use a labelled break (Topic 2.8) or a return from a method.

6. 6

   Nested loops over a 2D array (Topic 3.9) should normally put the row index outside and the column inside. Java stores each row as a separate array, so walking along a row touches neighbouring memory, which the CPU cache rewards.

• ↔

  Nested loops are the simplest correct solution for grids and pairs, but O(n²) work becomes too slow somewhere between thousands and millions of items; then use hashing, sorting or a smarter algorithm.

• ↔

  Printing patterns character by character is easy to reason about; building each line with repeat or a StringBuilder is faster and shorter but hides the per-character logic beginners need to see.

• Done when you can trace a nested loop and state how many times the inner body runs.

• Done when you can print a triangle, pyramid and hollow square from a row/space/symbol table.

• Done when you can write the every-pair loop with j = i + 1 and give its iteration count.

• Done when you can spot an inner counter that isn't reset or a wrong variable in the inner header.

• Done when you can explain why row-then-column order is faster for 2D arrays.