Unit 4.13: 2D Array Algorithms

Standard 2D Array Algorithms

Standard algorithms are applied to 2D arrays using nested traversals. These operations can be performed on the entire array or restricted to a specific row, column, or subsection.

Common Algorithms (EK 4.13.A.1)

Minimum and Maximum

Initializing & Updating

To find the min or max of the whole grid, initialize with grid[0][0]. For a specific row or column, initialize with the first element of that subsection.

Task: Finding the maximum value in a 2D array.

// In the main method ...
int max = matrix[0][0];
for (int[] row : matrix) {
    for (int val : row) {
        if (val > max) max = val;
    }
}

Sum, Average, and Counting

Accumulation

Use a nested traversal to visit every element and update a running total or a counter variable.

Task: Calculating the average and counting negative numbers in a 2D array.

// In the main method ...
int total = 0;
int countNegative = 0;
for (int[] row : grid) {
    for (int val : row) {
        total += val;
        if (val < 0) countNegative++;
    }
}
double average = (double) total / (grid.length * grid[0].length);

Property Checks (All / At Least One)

Boolean Flagging

Use a flag. For "All", assume true and set to false if any element fails. For "At Least One", assume false and set to true if a match is found.

Task: Checking if at least one element in a 2D array matches a target value.

// In the main method ...
boolean hasTarget = false;
for (int[] row : grid) {
    for (int val : row) {
        if (val == target) {
            hasTarget = true;
            break; 
        }
    }
}

Accessing Row or Column Subsections

Targeted Traversal

To process a single row, use one loop over columns. To process a single column, use one loop over rows.

Task: Summing the elements of a specific column.

// In the main method ...
// Summing only the 3rd column (index 2)
int colSum = 0;
for (int r = 0; r < matrix.length; r++) {
    colSum += matrix[r][2];
}

Duplicate Detection & Consecutive Pairs

Relative Comparisons

Use nested indexing to compare neighboring elements (consecutive) or nested loops to compare every element against others (duplicates).

Task: Checking for consecutive duplicate elements within rows.

// In the main method ...
// Checking for consecutive duplicates in rows
boolean found = false;
for (int r = 0; r < grid.length; r++) {
    for (int c = 0; c < grid[0].length - 1; c++) {
        if (grid[r][c] == grid[r][c+1]) found = true;
    }
}

Reversing, Shifting, and Rotating

Reordering Elements

These algorithms often apply 1D reordering logic to a specific row or column. Reversing a row involves swapping elements from the outside in.

Task: Reversing the elements of the first row in a 2D array.

// In the main method ...
// Reversing Row 0
int[] row = matrix[0];
for (int i = 0; i < row.length / 2; i++) {
    int temp = row[i];
    row[i] = row[row.length - 1 - i];
    row[row.length - 1 - i] = temp;
}