8.2 Traversing 2D Arrays

When working with 2D arrays, we often need to process every element in the array - maybe to display all values, calculate a sum, find a specific element, or transform the data. This is called traversing (or iterating through) a 2D array. In this guide, we'll explore different techniques for navigating through all elements of a 2D array, using nested loops to systematically access each value without writing individual code for each element.

Understanding 2D Array Traversal

Traversal means visiting each element in a systematic way. Since 2D arrays are structured as rows and columns (like a grid), we need a strategy to ensure we access every element exactly once.

Remember that 2D arrays in Java are stored as arrays of arrays, so our traversal methods need to account for this structure.

Standard Traversal Patterns

There are two main ways to traverse a 2D array:

1. Row-Major Order

Row-major traversal processes the array one row at a time. In this approach:

• Start at the first element of the first row
• Move across the row from left to right
• When the row is finished, move to the first element of the next row
• Repeat until all rows are processed

Think of this like reading a book - you read each line from left to right, then move to the next line.

2. Column-Major Order

Column-major traversal processes the array one column at a time. In this approach:

• Start at the first element of the first column
• Move down the column from top to bottom
• When the column is finished, move to the first element of the next column
• Repeat until all columns are processed

Think of this like reading a newspaper column - you read from top to bottom, then move to the next column.

Nested Loops for 2D Array Traversal

To traverse a 2D array, we use nested loops - one loop inside another. The outer loop handles rows (or columns), and the inner loop handles columns (or rows).

Console Output When Traversing

When working with 2D arrays, we often want to print the elements to see their values. Java provides two key console output methods:

• System.out.print(): Displays text without moving to a new line. This is useful for printing elements in a row side by side.

• System.out.println(): Displays text and then moves the cursor to the beginning of the next line. This helps create a visual separation between rows when printing a 2D array.

By combining these methods appropriately, we can display 2D arrays in a grid-like format that resembles their actual structure.

Row-Major Traversal with Nested for Loops

int[][] matrix = new int[3][4]; // A 3×4 matrix

// Row-major traversal
for (int row = 0; row < matrix.length; row++) {
    for (int col = 0; col < matrix[row].length; col++) {
        // Process matrix[row][col]
        System.out.print(matrix[row][col] + " ");
    }
    System.out.println(); // Move to next line after finishing a row
}

In this code:

• The outer loop iterates through each row (from 0 to matrix.length - 1)

• For each row, the inner loop iterates through each column (from 0 to matrix[row].length - 1)

• This ensures we visit every element exactly once, row by row

Column-Major Traversal with Nested for Loops

int[][] matrix = new int[3][4]; // A 3×4 matrix

// Column-major traversal
for (int col = 0; col < matrix[0].length; col++) {
    for (int row = 0; row < matrix.length; row++) {
        // Process matrix[row][col]
        System.out.print(matrix[row][col] + " ");
    }
    System.out.println(); // Move to next line after finishing a column
}

In this code:

• The outer loop iterates through each column (from 0 to matrix[0].length - 1)

• For each column, the inner loop iterates through each row (from 0 to matrix.length - 1)

• This ensures we visit every element exactly once, column by column

Using Enhanced For Loops

Java's enhanced for loop (also called the "for-each" loop) can make 2D array traversal more readable. Since 2D arrays are arrays of arrays, the enhanced for loop works well for row-major traversal:

int[][] matrix = new int[3][4]; // A 3×4 matrix

// Row-major traversal with enhanced for loops
for (int[] row : matrix) {        // Outer loop gets each row
    for (int element : row) {     // Inner loop gets each element in the row
        // Process the element
        System.out.print(element + " ");
    }
    System.out.println();
}

In this code:

• The outer loop gets each row as a 1D array
• The inner loop gets each element in that row
• This automatically handles row-major traversal

Important Note about Enhanced For Loops

According to the College Board specification (VAR-2.G.3), when using nested enhanced for loops for 2D arrays:

• The outer loop variable must be a 1D array type that matches each row
• The inner loop variable must be the same type as the elements stored in the 1D array

// For a 2D array of integers:
for (int[] row : matrix) {    // Outer variable is int[] (a 1D array)
    for (int val : row) {     // Inner variable is int (matches what's in the 1D array)
        // Process val
    }
}

Applying Search Algorithms to 2D Arrays

According to the College Board (CON-2.N), we can apply sequential/linear search to 2D arrays by:

1. Searching each row individually
2. Treating each row as a 1D array

Example: Searching for a Value in a 2D Array

public static boolean contains(int[][] matrix, int target) {
    // Row-by-row search
    for (int row = 0; row < matrix.length; row++) {
        // Apply 1D array search to each row
        for (int col = 0; col < matrix[row].length; col++) {
            if (matrix[row][col] == target) {
                return true; // Found the target
            }
        }
    }
    return false; // Target not found
}

Common 2D Array Traversal Algorithms

Let's look at some common algorithms that use 2D array traversal:

1. Sum All Elements

public static int sumAll(int[][] matrix) {
    int sum = 0;
    for (int[] row : matrix) {
        for (int element : row) {
            sum += element;
        }
    }
    return sum;
}

2. Find Maximum Value

public static int findMax(int[][] matrix) {
    // Start with the first element
    int max = matrix[0][0];
    
    for (int[] row : matrix) {
        for (int element : row) {
            if (element > max) {
                max = element;
            }
        }
    }
    return max;
}

3. Count Occurrences of a Value

public static int countOccurrences(int[][] matrix, int target) {
    int count = 0;
    for (int[] row : matrix) {
        for (int element : row) {
            if (element == target) {
                count++;
            }
        }
    }
    return count;
}

Modifying Elements During Traversal

One of the powerful aspects of traversal is the ability to modify elements as you go:

// Double all values in the matrix
for (int row = 0; row < matrix.length; row++) {
    for (int col = 0; col < matrix[row].length; col++) {
        matrix[row][col] = matrix[row][col] * 2;
    }
}

Practical Examples

Example 1: Calculating Row and Column Sums

public static int[] rowSums(int[][] matrix) {
    int[] sums = new int[matrix.length];
    
    for (int row = 0; row < matrix.length; row++) {
        int rowSum = 0;
        for (int col = 0; col < matrix[row].length; col++) {
            rowSum += matrix[row][col];
        }
        sums[row] = rowSum;
    }
    
    return sums;
}

public static int[] columnSums(int[][] matrix) {
    int[] sums = new int[matrix[0].length];
    
    for (int col = 0; col < matrix[0].length; col++) {
        int colSum = 0;
        for (int row = 0; row < matrix.length; row++) {
            colSum += matrix[row][col];
        }
        sums[col] = colSum;
    }
    
    return sums;
}

Example 2: Checking for a Magic Square

A magic square is a grid where all rows, columns, and diagonals sum to the same value.

public static boolean isMagicSquare(int[][] square) {
    // Square must be n×n
    if (square.length != square[0].length) {
        return false;
    }
    
    int n = square.length;
    int magicSum = 0;
    
    // Calculate sum of first row as reference
    for (int col = 0; col < n; col++) {
        magicSum += square[0][col];
    }
    
    // Check each row
    for (int row = 0; row < n; row++) {
        int rowSum = 0;
        for (int col = 0; col < n; col++) {
            rowSum += square[row][col];
        }
        if (rowSum != magicSum) {
            return false;
        }
    }
    
    // Check each column
    for (int col = 0; col < n; col++) {
        int colSum = 0;
        for (int row = 0; row < n; row++) {
            colSum += square[row][col];
        }
        if (colSum != magicSum) {
            return false;
        }
    }
    
    // Check main diagonal (top-left to bottom-right)
    int diagSum1 = 0;
    for (int i = 0; i < n; i++) {
        diagSum1 += square[i][i];
    }
    if (diagSum1 != magicSum) {
        return false;
    }
    
    // Check other diagonal (top-right to bottom-left)
    int diagSum2 = 0;
    for (int i = 0; i < n; i++) {
        diagSum2 += square[i][n - 1 - i];
    }
    if (diagSum2 != magicSum) {
        return false;
    }
    
    return true; // All checks passed
}

Common Errors and Best Practices

Common Errors

1. Index Out of Bounds: Always ensure your loop conditions prevent accessing elements outside the array bounds.

2. Row vs. Column Confusion: Remember that in Java, the first index is for rows, and the second is for columns: matrix[row][col].

3. Outer vs. Inner Loop: The outer loop should iterate through rows (for row-major) or columns (for column-major), with the inner loop handling the other dimension.

4. Assuming Rectangular Arrays: In Java, each row can technically have a different length. Always use array[row].length for the inner loop condition, not array[0].length.

Best Practices

1. Use Clear Variable Names: Use row and col (or similar) instead of i and j to make your code more readable.

2. Check Bounds: For safety, especially with user input, verify array dimensions before processing.

3. Consider Enhanced For Loops: For simple traversal without index manipulation, enhanced for loops can make your code cleaner.

4. Reuse Standard Algorithms: Many common 2D array operations can be implemented by adapting 1D array algorithms to work row by row.

Conclusion

Traversing 2D arrays is a fundamental skill in Java programming that allows us to process large grids of data efficiently. By using nested loops, either standard for loops or enhanced for loops, we can systematically access every element in a 2D array to search, calculate, or modify data. Understanding the difference between row-major and column-major order gives you flexibility in how you process your data. These traversal techniques let programmers manage complex data relationships without creating individual variables for each value - a powerful capability in data processing.