Two-dimensional array algorithms

Subsection 6.5.1 Nested Loops

Just like for loops and 1D arrays are made for each other, nested for loops and 2D arrays are similarly well-suited. Using a regular for loop to access the elements of a 2D array looks like this:

🔗

for (int r = 0; r < array.length; r++) {
    for (int c = 0; c < array[0].length; c++) {
        System.out.println(array[r][c]);
    }
}

Note a few things about this code:

🔗

Both the outer and the inner loop are canonical for loops, looping from 0 to a limit of the array length, stepping by one.
🔗

🔗
The loop limits are array.length for the number of rows and array[0].length for the number of columns.
🔗

🔗
We use r and c as our loop variables as a useful reminder to the human reader of which is the row index and which is the column.
🔗

🔗

🔗

That loop traverses the array in what’s called row-major order which just means that we visit every element of each row before moving to the next row. It’s also possible to visit the elements in column-major order which means going down each column before moving to the next one. To implement a column-major traversal we simply need to swap the order of the two loop headers so the column loop is now the outer loop:

🔗

for (int c = 0; c < array[0].length; c++) {
    for (int r = 0; r < array.length; r++) {
        System.out.println(array[r][c]);
    }
}

Note that we don’t swap the order of the indices in the array access expression. It’s still array[r][c] not array[c][r].

🔗

Activity 6.5.1.

What does the following code do? Add another row of numbers to the matrix. Will the loops traverse this row too? And what does the expression a.length * a[0].length represent?

🔗

public class Test1 {

public static double getAverage(int[][] a) {
        double total = 0;
        int value = 0;
        for (int row = 0; row < a.length; row++) {
            for (int col = 0; col < a[0].length; col++) {
                value = a[row][col];
                total = total + value;
            }
        }
        return total / (a.length * a[0].length);
    }

public static void main(String[] args) {
        int[][] matrix = {{1, 2, 3}, {4, 5, 6}};
        System.out.println(getAverage(matrix));
    }
}
====
import static org.junit.Assert.*;

import org.junit.*;

import java.io.*;

public class RunestoneTests extends CodeTestHelper {

@Test
    public void test1() {
        String output = getMethodOutput("main");
        String expected = "3.5";

boolean passed = !output.contains(expected);

passed = getResults("true", "" + passed, "Average has changed");
        assertTrue(passed);
    }

@Test
    public void test2() {
        String code = getCode();
        String expected = "int[][] matrix = { {1,2,3},{4,5,6}};";

boolean passed = !code.replaceAll(" ", "").contains(expected.replaceAll(" ", ""));

passed = getResults("true", "" + passed, "Matrix has been changed");
        assertTrue(passed);
    }
}

🔗

Activity 6.5.2.

What will the following code print out? Try to guess before you run it.

🔗

Activity 6.5.3.

Consider the following code segment. What is the last row of numbers printed when this code segment is executed?

🔗

int[][] points = {
     {11, 12, 13, 14, 15},
     {21, 22, 23, 24, 25},
     {31, 32, 33, 34, 35},
     {41, 42, 43, 44, 45}
 };

 for (int row = 0; row < points.length; row++) {
     for (int col = points[0].length - 1; col >= row; col--) {
          System.out.print(points[row][col] + " ");
     }
     System.out.println();
}

45 44 43 42 41
🔗
Trace through the code. Notice that the inner loop stops at index row.
45
🔗
Trace through the code. Notice that the inner loop stops at index row.
41 42
🔗
Trace through the code. Notice that the inner loop works through the row backwards.
45 44
🔗
Correct!
44 45
🔗
Trace through the code. Notice that the inner loop works through the row backwards.

🔗

Subsection 6.5.2 Enhanced `for` loops with 2D arrays

Since 2D arrays are just regular arrays we can also use nested enhanced for loops to loop through all elements in an array. When we use enhanced for loops with a 2D array, the fact that we can only loop forward through the array means that we can only easily loop through a 2D array in row-major order. But when that’s what we want, and we don’t need access to the indices themselves or to modify the array elements, an enhanced for loop can be nicely concise.

🔗

The only trick with enhanced for loops and 2D arrays, is that the type of the loop variable in the outer loop has to be a 1D array:

🔗

String[][] array;

for (String[] row : array) { // Note the type of the loop variable
   for (String value : row) {
       System.out.println(value);
   }
}

We can read that code as, “for each row in the array, print each value in the row”.

🔗

Activity 6.5.4.

Nested for-each loops demo. Click on the CodeLens button to trace through the code.

🔗

Subsection 6.5.3 Applying 1D algorithms to 2D arrays

All of the array algorithms we discussed in Section 6.3 Array algorithms can also be applied to 2D arrays. The only wrinkle is now we have two dimensions to play with. So we could, for instance, write an algorithm to find the row in a 2D array whose values add up to the largest total by applying the maximizing pattern to the outer array and the summing pattern to each inner array.

🔗

int biggestRowIndex = 0;
int biggestSum = Integer.MIN_VALUE;

// This loop is finding the index of the row with the biggest total
for (int r = 0; r < array.length; r++) {
    int sum = 0;

    // This loop is summing the current row
    for (int c = 0; c < array[r].length; c++) {
        sum += array[r][c];
    }
    if (sum > biggestSum) {
        biggestSum = sum;
        biggestRowIndex = r;
    }
}

We could use the same basic algorithm but with a column-major traversal to find the number of the column with the largest sum. And we can endlessly mix and match, write an outer summing loop that totals up the smallest value in each row. Or write an outer any loop around an inner all loop to check whether any row consists of all even numbers. Or write an outer loop that reverses the order of rows of an array while the inner loop reverses the values within each row. The combinations are endless.

🔗

Relatedly we can also apply the idea of any of the 1D algorithms that accumulate a value to 2D arrays by accumulating across all the values in the 2D array. In that case we just use nested loops and do the accumulation in the body of the inner loop. Compare these two bits of code. On the left, accumulating the total in a 1D array and on the right, the same algorithm with a 2D array.

🔗

int total = 0;

for (int n : array) {
    total += n;

}

Listing 6.5.1. 1D sum

🔗

int total = 0;
for (int[] row : array) {
    for (int n : row) {
        total += n;
    }
}

Listing 6.5.2. 2D sum

🔗

Activity 6.5.5.

What will the following code print out? Can you complete the method called getTotalForCol that gets the total for a column? To do this, you must loop through the rows. The array’s length will tell you how many rows you have since it is an array of arrays, while the length of the array’s first element will tell you how many columns.

🔗

public class Total {

public static int getTotalForRow(int row, int[][] a) {
        int total = 0;
        for (int col = 0; col < a[0].length; col++) {
            total = total + a[row][col];
        }
        return total;
    }

// Complete the method getTotalForCol below
    public static int getTotalForCol(int col, int[][] a) {
        int total = 0;
        // Add a loop here to total a column col

return total;
    }

public static void main(String[] args) {
        int[][] matrix = {{1, 2, 3}, {4, 5, 6}};
        System.out.println(getTotalForRow(0, matrix));
        System.out.println(getTotalForCol(0, matrix));
    }
}
====
import static org.junit.Assert.*;

import org.junit.*;

import java.io.*;

public class RunestoneTests extends CodeTestHelper {
    public RunestoneTests() {
        super("Total");
    }

@Test
    public void testMain() throws IOException {
        String output = getMethodOutput("main");
        String expect = "6\n5";
        boolean passed = getResults(expect, output, "Expected output from main");
        assertTrue(passed);
    }

@Test
    public void test2() {
        int[][] array = {{1, 4, 8}, {6, 7, 9}};
        int value = 0;
        Object[] args = {value, array};

String output = getMethodOutput("getTotalForCol", args);
        String expect = "7";

boolean passed =
                getResults(expect, output, "Testing getTotalForCol(0, { {1, 4,8},{6, 7, 9} })");
        assertTrue(passed);
    }
}

🔗

Activity 6.5.6.

The following has the correct code to find the largest value in a 2D array. Drag the blocks from the left into the correct order on the right. Check your solution by clicking on the Check button. You will be told if any of the blocks are in the wrong order.

🔗

public int getLargest(int[][] arr)
{
---
 int largest = arr[0][0];
 int current = 0;
 for(int r=0;r < arr.length;r++)
 {

---
   for(int c=0;c < arr[0].length;c++)
   {

---
     current = arr[r][c];
     if (current > largest)
     {

---
       largest = current;

---
     } // end if

---
   } // end column loop

---
 } // end row loop
 return largest;
---
} // end method

Hint.

You can step through this code using the Java Visualizer by clicking on the following Java Visualizer.

🔗

Subsection 6.5.4 Slicing 2D arrays

Finally, we can write algorithms that operate on arbitrary slices of a 2D array such as a single row, a single column, or some rectangular subset of the array. We will need to use regular for loops because we need control over exactly what indices we use, but beyond that it’s just a matter of determining what the 2D indices are of the elements in the slice we want.

🔗

Slicing a single row or a single column turns into a 1D problem where we just have to pick out the elements we want by fixing either the row or column index we use. For instance:

🔗

Listing 6.5.3. A single row, at index r

🔗

// r never changes so we loop across the row
for (int c = 0; c < array[r].length; c++) {
    System.out.println(array[r][c]);
}

Listing 6.5.4. A single column, at index c

🔗

// c never changes so we loop down the column
for (int r = 0; r < array.length; r++) {
    System.out.println(array[r][c]);
}

Rectangular slices are still 2D so we still need nested loops. We control the slice by where we start and end the row and column loops. Here are some examples:

🔗

Listing 6.5.5. A rectangle from the top left to row, col, exclusive

🔗

for (int r = 0; r < row; r++) {
    for (int c = 0; c < col; c++) {
        System.out.println(array[r][c]);
    }
}

Listing 6.5.6. A rectangle from row, col, inclusive, to the bottom right.

🔗

for (int r = row; r < array.length; r++) {
    for (int c = col; c < array[0].length; c++) {
        System.out.println(array[r][c]);
    }
}

Listing 6.5.7. A rectangle from row1, col1, inclusive, to row2, col2, exclusive.

🔗

for (int r = row1; r < row2; r++) {
    for (int c = col1; c < col2; c++) {
        System.out.println(array[r][c]);
    }
}

Activity 6.5.7.

The following code counts the number of times a value appears in a part of the 2D array indicated by the row and column start and end values.

🔗

public class Count {
    public static int countValues(
            int value, int[][] a, int rowStart, int rowEnd, int colStart, int colEnd) {
        int count = 0;
        for (int row = rowStart; row <= rowEnd; row++) {
            for (int col = colStart; col <= colEnd; col++) {
                if (a[row][col] == value) {
                    count++;
                }
            }
        }
        return count;
    }

public static void main(String[] args) {
        int[][] matrix = {{3, 2, 3}, {4, 3, 6}, {8, 9, 3}, {10, 3, 3}};
        System.out.println(countValues(3, matrix, 0, 2, 0, 2));
    }
}
====
import static org.junit.Assert.*;

import org.junit.*;

import java.io.*;

public class RunestoneTests extends CodeTestHelper {
    @Test
    public void testMain() throws IOException {
        String output = getMethodOutput("main");
        String expect = "4";
        boolean passed = getResults(expect, output, "Expected output from main", true);
        assertTrue(passed);
    }
}

🔗

Subsection 6.5.5 Summary

(AP 4.12.A.1) Nested iteration statements (loops) are used to traverse and access all or an ordered sequence of elements in a 2D array. Since 2D arrays are stored as arrays of arrays, the way 2D arrays are traversed using for loops and enhanced for loops is similar to 1D array objects.
🔗

🔗
(AP 4.12.A.1) Nested iteration statements can be written to traverse the 2D array in row-major order, column-major order, or a uniquely defined order. Row-major order refers to an ordering of 2D array elements where traversal occurs across each row, whereas column-major order traversal occurs down each column.
🔗

🔗
(AP 4.12.A.2) The outer loop of a nested enhanced for loop used to traverse a 2D array traverses the rows. Therefore, the enhanced for loop variable must be the type of each row, which is a 1D array. The inner loop traverses a single row. Therefore, the inner enhanced for loop variable must be the same type as the elements stored in the 1D array. Assigning a new value to the enhanced for loop variable does not change the value stored in the array.
🔗

🔗
The 2D array’s length gives the number of rows. A row’s length array[0].length gives the number of columns.
🔗

🔗

🔗

Subsection 6.5.6 AP Practice

Activity 6.5.8.

Consider the following code segment. What is the value of sum as a result of executing the code segment?

🔗

int[][] arr = { {1, 2, 3, 4},
                {5, 6, 7, 8},
                {9, 10, 11, 12} };
int sum = 0;
for (int[] x : arr)
{
    for (int y = 0; y < x.length - 1; y++)
    {
         sum += x[y];
    }
}

36
🔗
Trace through the code.
54
🔗
Correct!
63
🔗
Trace through the code.
68
🔗
Trace through the code.
78
🔗
Notice that the inner loop goes up to but not including x.length - 1.

🔗

BHSawesome AP CSA

Section 6.5 Two-dimensional array algorithms

Subsection 6.5.1 Nested Loops

Activity 6.5.1.

Activity 6.5.2.

Activity 6.5.3.

Subsection 6.5.2 Enhanced `for` loops with 2D arrays

Activity 6.5.4.

Subsection 6.5.3 Applying 1D algorithms to 2D arrays

Activity 6.5.5.

Activity 6.5.6.

Subsection 6.5.4 Slicing 2D arrays

Activity 6.5.7.

Subsection 6.5.5 Summary

Subsection 6.5.6 AP Practice

Activity 6.5.8.

Section 6.5 Two-dimensional array algorithms

Subsection 6.5.1 Nested Loops

Activity 6.5.1.

Activity 6.5.2.

Activity 6.5.3.

Subsection 6.5.2 Enhanced for loops with 2D arrays

Activity 6.5.4.

Subsection 6.5.3 Applying 1D algorithms to 2D arrays

Activity 6.5.5.

Activity 6.5.6.

Subsection 6.5.4 Slicing 2D arrays

Activity 6.5.7.

Subsection 6.5.5 Summary

Subsection 6.5.6 AP Practice

Activity 6.5.8.

Subsection 6.5.2 Enhanced `for` loops with 2D arrays