2.11 Nested Iteration

Nested iteration occurs when you place one loop inside another, creating multiple levels of repetition. This powerful programming pattern allows you to process two-dimensional data, generate complex patterns, and examine all combinations of elements. Understanding how nested loops execute is essential for working with 2D arrays and solving many algorithmic problems.

The fundamental principle of nested loops is that the inner loop completes all of its iterations for each single iteration of the outer loop. This creates a multiplication effect - if the outer loop runs m times and the inner loop runs n times, the total number of operations is m × n. This execution pattern is key to understanding how nested loops work and when to use them.

• Major concepts: Loop execution order, inner vs outer loop relationship, iteration counting, 2D pattern generation
• Why this matters for AP: Essential for 2D arrays, appears in complex algorithm problems, tests understanding of iteration control
• Common pitfalls: Mixing up loop variable names, incorrect iteration counting, performance issues with unnecessary nesting
• Key vocabulary: Nested iteration, inner loop, outer loop, iteration relationship, 2D processing
• Prereqs: Strong understanding of single for loops, ability to trace through loop execution step by step

Key Concepts

The Fundamental Execution Pattern

When you have one loop inside another, the inner loop runs to completion for every single iteration of the outer loop. This is the most important concept to understand about nested loops.

for (int outer = 1; outer <= 3; outer++) {
    for (int inner = 1; inner <= 2; inner++) {
        System.out.println("Outer: " + outer + ", Inner: " + inner);
    }
}

This produces:

Outer: 1, Inner: 1
Outer: 1, Inner: 2
Outer: 2, Inner: 1
Outer: 2, Inner: 2
Outer: 3, Inner: 1
Outer: 3, Inner: 2

Notice how the inner loop variable goes through all its values (1, 2) for each value of the outer loop variable.

Mental Model: The Clock Analogy

Think of nested loops like a digital clock. The outer loop is like hours, and the inner loop is like minutes. For every hour that passes, the minutes go from 0 to 59. The minutes complete their full cycle before the hour advances.

This helps you understand why nested loops are so powerful for processing two-dimensional data or examining all combinations of things.

Loop Variable Scope and Naming

Each loop has its own variable, and you need to keep them distinct. I recommend using meaningful names rather than just i, j, k when possible.

for (int row = 0; row < height; row++) {
    for (int col = 0; col < width; col++) {
        // Process position (row, col)
    }
}

This makes your code much more readable and helps prevent mistakes.

Iteration Count Calculation

If the outer loop runs A times and the inner loop runs B times, the total number of iterations is A × B. This is crucial for understanding performance and behavior.

For example:

• Outer loop: 5 iterations
• Inner loop: 3 iterations
• Total iterations: 5 × 3 = 15

Code Examples

Basic Pattern Generation

public class PatternGeneration {
    // Print a rectangle of stars
    public static void printRectangle(int rows, int cols) {
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                System.out.print("* ");
            }
            System.out.println();  // New line after each row
        }
    }

    // Print a right triangle
    public static void printTriangle(int size) {
        for (int row = 1; row <= size; row++) {
            for (int star = 1; star <= row; star++) {
                System.out.print("* ");
            }
            System.out.println();
        }
    }

    // Print numbers in a grid
    public static void printNumberGrid(int rows, int cols) {
        for (int r = 1; r <= rows; r++) {
            for (int c = 1; c <= cols; c++) {
                System.out.print((r * cols + c - cols) + "\t");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        System.out.println("Rectangle:");
        printRectangle(3, 4);

        System.out.println("\nTriangle:");
        printTriangle(4);

        System.out.println("\nNumber Grid:");
        printNumberGrid(3, 4);
    }
}

Array Processing

public class ArrayProcessing {
    // Sum all elements in a 2D array
    public static int sum2DArray(int[][] array) {
        int total = 0;
        for (int row = 0; row < array.length; row++) {
            for (int col = 0; col < array[row].length; col++) {
                total += array[row][col];
            }
        }
        return total;
    }

    // Find maximum value in 2D array
    public static int findMax2D(int[][] array) {
        if (array.length == 0 || array[0].length == 0) {
            throw new IllegalArgumentException("Array cannot be empty");
        }

        int max = array[0][0];  // Start with first element
        for (int row = 0; row < array.length; row++) {
            for (int col = 0; col < array[row].length; col++) {
                if (array[row][col] > max) {
                    max = array[row][col];
                }
            }
        }
        return max;
    }

    // Print 2D array in readable format
    public static void print2DArray(int[][] array) {
        for (int row = 0; row < array.length; row++) {
            for (int col = 0; col < array[row].length; col++) {
                System.out.print(array[row][col] + "\t");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        int[][] matrix = {
            {1, 2, 3},
            {4, 5, 6},
            {7, 8, 9}
        };

        System.out.println("Array:");
        print2DArray(matrix);
        System.out.println("Sum: " + sum2DArray(matrix));    // 45
        System.out.println("Max: " + findMax2D(matrix));     // 9
    }
}

Comparison Problems

public class ComparisonProblems {
    // Find all pairs in an array that sum to a target
    public static void findPairs(int[] array, int target) {
        System.out.println("Pairs that sum to " + target + ":");
        for (int i = 0; i < array.length; i++) {
            for (int j = i + 1; j < array.length; j++) {  // Start j at i+1 to avoid duplicates
                if (array[i] + array[j] == target) {
                    System.out.println(array[i] + " + " + array[j] + " = " + target);
                }
            }
        }
    }

    // Count inversions (how many pairs are out of order)
    public static int countInversions(int[] array) {
        int count = 0;
        for (int i = 0; i < array.length; i++) {
            for (int j = i + 1; j < array.length; j++) {
                if (array[i] > array[j]) {  // i comes before j but has larger value
                    count++;
                }
            }
        }
        return count;
    }

    // Check if two strings are anagrams by counting characters
    public static boolean areAnagrams(String str1, String str2) {
        if (str1.length() != str2.length()) {
            return false;
        }

        // Count characters in first string
        for (int i = 0; i < str1.length(); i++) {
            char ch = str1.charAt(i);
            int count1 = 0, count2 = 0;

            // Count occurrences in both strings
            for (int j = 0; j < str1.length(); j++) {
                if (str1.charAt(j) == ch) count1++;
                if (str2.charAt(j) == ch) count2++;
            }

            if (count1 != count2) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int[] numbers = {1, 2, 3, 4, 5};
        findPairs(numbers, 5);  // 1+4, 2+3

        int[] unsorted = {3, 1, 4, 2};
        System.out.println("Inversions: " + countInversions(unsorted));  // 4

        System.out.println("listen and silent are anagrams: " + 
                          areAnagrams("listen", "silent"));  // true
    }
}

Multiplication Table Generator

public class MultiplicationTable {
    public static void printTable(int size) {
        // Print header row
        System.out.print("   ");
        for (int col = 1; col <= size; col++) {
            System.out.printf("%4d", col);
        }
        System.out.println();

        // Print separator line
        System.out.print("   ");
        for (int col = 1; col <= size; col++) {
            System.out.print("----");
        }
        System.out.println();

        // Print table body
        for (int row = 1; row <= size; row++) {
            System.out.printf("%2d|", row);  // Row header
            for (int col = 1; col <= size; col++) {
                System.out.printf("%4d", row * col);
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        printTable(5);
    }
}

Search in 2D Array

public class Search2D {
    // Linear search in 2D array
    public static boolean contains(int[][] array, int target) {
        for (int row = 0; row < array.length; row++) {
            for (int col = 0; col < array[row].length; col++) {
                if (array[row][col] == target) {
                    return true;
                }
            }
        }
        return false;
    }

    // Find position of target (returns row and col)
    public static int[] findPosition(int[][] array, int target) {
        for (int row = 0; row < array.length; row++) {
            for (int col = 0; col < array[row].length; col++) {
                if (array[row][col] == target) {
                    return new int[]{row, col};
                }
            }
        }
        return new int[]{-1, -1};  // Not found
    }

    // Count occurrences of target in 2D array
    public static int countOccurrences(int[][] array, int target) {
        int count = 0;
        for (int row = 0; row < array.length; row++) {
            for (int col = 0; col < array[row].length; col++) {
                if (array[row][col] == target) {
                    count++;
                }
            }
        }
        return count;
    }

    public static void main(String[] args) {
        int[][] matrix = {
            {1, 2, 3},
            {4, 5, 6},
            {7, 8, 9}
        };

        System.out.println("Contains 5: " + contains(matrix, 5));      // true
        int[] pos = findPosition(matrix, 6);
        System.out.println("Position of 6: (" + pos[0] + ", " + pos[1] + ")");  // (1, 2)
    }
}

Common Errors and Debugging

Loop Variable Confusion

This happens when you mix up loop variables or use the wrong variable in the wrong context.

Common cause: Using similar variable names like i, j, k without keeping track of which is which.

Example scenario:

for (int i = 0; i < rows; i++) {
    for (int j = 0; j < cols; j++) {
        array[j][i] = value;  // Bug: should be array[i][j]
    }
}

How to fix: Use descriptive variable names and be consistent about which represents what.

for (int row = 0; row < rows; row++) {
    for (int col = 0; col < cols; col++) {
        array[row][col] = value;  // Clear and correct
    }
}

Debugging tip: When tracing nested loops, write down the values of both loop variables at each step.

Incorrect Loop Bounds

Off-by-one errors are even trickier with nested loops because they can occur in either the outer or inner loop.

Common cause: Wrong comparison operators or bounds that don't match array dimensions.

Example scenario:

int[][] array = new int[3][4];  // 3 rows, 4 columns
for (int r = 0; r <= 3; r++) {  // Bug: should be < 3
    for (int c = 0; c < 4; c++) {
        array[r][c] = 1;  // ArrayIndexOutOfBoundsException when r = 3
    }
}

How to fix: Always use < with .length for array bounds.

Performance Issues

Nested loops can be expensive, especially when you don't need all combinations.

Common cause: Using nested loops when a single loop or different approach would work.

Example scenario:

// Inefficient: O(n²) to find if array contains duplicates
public static boolean hasDuplicates(int[] array) {
    for (int i = 0; i < array.length; i++) {
        for (int j = i + 1; j < array.length; j++) {
            if (array[i] == array[j]) {
                return true;
            }
        }
    }
    return false;
}

Better approach: Sort first and check adjacent elements, or use a HashSet.

Debugging tip: Ask yourself if you really need to examine all combinations, or if there's a more efficient approach.

Practice Problems

Problem 1: Pascal's Triangle

Write a method that prints the first n rows of Pascal's Triangle:

public static void printPascalsTriangle(int numRows) {
    // Each row starts and ends with 1
    // Each interior number is sum of two numbers above it
}

Solution:

public static void printPascalsTriangle(int numRows) {
    for (int row = 0; row < numRows; row++) {
        // Print spaces for alignment
        for (int space = 0; space < numRows - row - 1; space++) {
            System.out.print(" ");
        }

        // Calculate and print values in this row
        for (int col = 0; col <= row; col++) {
            System.out.print(pascalValue(row, col) + " ");
        }
        System.out.println();
    }
}

private static int pascalValue(int row, int col) {
    if (col == 0 || col == row) {
        return 1;
    }
    return pascalValue(row - 1, col - 1) + pascalValue(row - 1, col);

}

Key insight: Each position's value depends on the two positions above it in the previous row.

Problem 2: Matrix Rotation

Write a method that rotates a square matrix 90 degrees clockwise:

public static void rotateMatrix(int[][] matrix) {
    // Rotate the matrix in place
}

Solution:

public static void rotateMatrix(int[][] matrix) {
    int n = matrix.length;

    // Process layer by layer from outside to inside
    for (int layer = 0; layer < n / 2; layer++) {
        int first = layer;
        int last = n - 1 - layer;

        for (int i = first; i < last; i++) {
            int offset = i - first;

            // Save top element
            int top = matrix[first][i];

            // Left -> Top
            matrix[first][i] = matrix[last - offset][first];

            // Bottom -> Left  
            matrix[last - offset][first] = matrix[last][last - offset];

            // Right -> Bottom
            matrix[last][last - offset] = matrix[i][last];

            // Top -> Right
            matrix[i][last] = top;
        }
    }
}

Key insight: Process the matrix in concentric layers, rotating four elements at a time.

Problem 3: Spiral Traversal

Write a method that prints a 2D array in spiral order (clockwise from outside to inside):

public static void printSpiral(int[][] matrix) {
    // Print elements in spiral order
}

Solution:

public static void printSpiral(int[][] matrix) {
    if (matrix.length == 0) return;

    int rows = matrix.length;
    int cols = matrix[0].length;
    int top = 0, bottom = rows - 1;
    int left = 0, right = cols - 1;

    while (top <= bottom && left <= right) {
        // Print top row
        for (int col = left; col <= right; col++) {
            System.out.print(matrix[top][col] + " ");
        }
        top++;

        // Print right column
        for (int row = top; row <= bottom; row++) {
            System.out.print(matrix[row][right] + " ");
        }
        right--;

        // Print bottom row (if exists)
        if (top <= bottom) {
            for (int col = right; col >= left; col--) {
                System.out.print(matrix[bottom][col] + " ");
            }
            bottom--;
        }

        // Print left column (if exists)
        if (left <= right) {
            for (int row = bottom; row >= top; row--) {
                System.out.print(matrix[row][left] + " ");
            }
            left++;
        }
    }
}

Key insight: Process the matrix in layers, going clockwise around each layer.

AP Exam Connections

Nested loops are essential for 2D array processing and frequently appear on AP Computer Science A exams.

Multiple Choice Patterns

You'll often see questions asking you to trace through nested loops and determine the output or final state. Pay careful attention to loop bounds and the relationship between outer and inner loop variables. Common patterns include iteration counting questions and array access patterns.

FRQ Applications

FRQ 1 (Methods and Control Structures): Methods might use nested loops for complex calculations or pattern generation.

FRQ 2 (Class Design): Classes working with 2D data structures need nested loops for processing.

FRQ 3 (Array/ArrayList): Sometimes requires comparing all pairs of elements or processing nested data structures.

FRQ 4 (2D Array): This is where nested loops are absolutely essential. You'll need them for traversing, searching, and modifying 2D arrays in various patterns.

Quick Test-Taking Tips

When tracing nested loops, work systematically through each iteration of the outer loop, completing all inner loop iterations before moving to the next outer iteration. Don't try to jump ahead or take shortcuts.

For 2D array problems, always double-check your loop bounds against the array dimensions. Remember that array.length gives you the number of rows, and array[0].length gives you the number of columns.

If you see nested loops with early termination (break or return statements), trace carefully to understand when the loops actually exit. The inner loop might not always complete all its iterations.