Time estimate: 90 min.

4.13. Implementing 2D Array Algorithms¶

All of the array algorithms can be applied to 2D arrays too. There are standard algorithms that utilize 2D array traversals to:

determine a minimum or maximum value of all the elements or for a designated row, column, or other subsection
compute a sum or average of all the elements or for a designated row, column, or other subsection
determine if at least one element has a particular property in the entire 2D array or for a designated row, column, or other subsection
determine if all elements of the 2D array or a designated row, column, or other subsection have a particular property
determine the number of elements in the 2D array or in a designated row, column, or other subsection having a particular property
access all consecutive pairs of elements
determine the presence or absence of duplicate elements in the 2D array or in a designated row, column, or other subsection
shift or rotate elements in a row left or right or in a column up or down
reverse the order of the elements in a row or column

Remember that with 1D arrays, many algorithms followed the following patterns with a for loop or enhanced for loop.

// 1 Dimensional Array Traversal
for (int value : array)
{
    if (value ....)
        ...
}

for(int i=0; i < array.length; i++)
{
   if (array[i] ....)
       ...
}

But with 2D arrays, you will need to use nested loops to traverse the rows and columns of the 2D array. We often use indexed for loops for this to better control the row and column index values, but you can also use enhanced for loops.

// 2 Dimensional Array Traversal
for (int row = 0; row < array.length; row++)
{
    for (int col = 0; col < array[0].length; col++)
    {
        if (array[row][col] ....)
            ...
    }
}

// enhanced for loops
for (int[] row : array)
{
    for (int value : row)
    {
        if (value ....)
            ...
    }
}

4.13.1. Sum, Average, Min, Max 2D Array Algorithms¶

For example, counting and searching algorithms work very similarly in 1D and 2D arrays. The following code adds all of the values in a given row.

Coding Exercise

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);
    }
}

Mixed up programs

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 and indent them as well. Check your solution by clicking on the Check button. You will be told if any of the blocks are in the wrong order or have the wrong indention.

        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

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

4.13.2. Subsection of a 2D Array for a Property¶

You can loop through just part of a 2D array. You can change the starting value and ending value to loop through a subset of a 2D array. 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.

Looping through just part of a 2D array.

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);
    }
}

4.13.3. Duplicates in 2D Arrays¶

You can determine the presence or absence of duplicate elements in the 2D array or in a designated row, column, or other subsection. With 1D arrays, we sometimes needed 2 nested loops to check for duplicates or pairs. With 2D arrays, you often need 4 nested loop to check the whole array!

The method noDups(nums) returns true if there are no repeated (duplicate) items in the array nums. It should return false if it does find a repeated element using nested loops.

4.13.4. Rotate and Reverse¶

We can also rotate or reverse the order of the elements in a row or column. The following code rotates the elements in a row to the right by one position. This algorithm is very similar to the 1D array rotation algorithm since we are dealing with a single row or column.

language:: java
autograde:: unittest
practice:: T

Create a method rotateRowRight that rotates the elements in a row to the right by one position. It should return the rotated array.

public class Rotate
{
     public static int[][] rotateRowRight(int[][] nums, int row)
     {
          int last = nums[row][nums[0].length - 1];
          // Write a backwards loop through the row's columns
          //  to copy elements at col-1 to col

// Copy the last element to the first element at col 0

return nums;
     }

public static void main(String[] args)
     {
          int[][] matrix = { {3, 2, 3}, {4, 3, 6}, {8, 9, 3}, {10, 3, 3}};
          int[][] rotated = rotateRowRight(matrix, 1);
          for (int row = 0; row < rotated.length; row++)
          {
            for (int col = 0; col < rotated[0].length; col++)
            {
                 System.out.print(rotated[row][col] + " ");
            }
            System.out.println();
          }
     }
}

====
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 = "3 2 3\n6 4 3\n8 9 3\n10 3 3\n";
          boolean passed = getResults(expect, output, "Expected output from main", true);
          assertTrue(passed);
     }
     @Test
        public void test2()
        {
            int[][] array = { {1, 4, 8}, {6, 7, 9}};
            int value = 0;
            Object[] args = {array, 0};

String output = getMethodOutput("rotateRowRight", args);
            String expect = "8 1 4\n6 7 9\n";

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

4.13.5. Review and FRQ Practice with 2D arrays¶

Time estimate: 90 min.

This lesson ends the 2D arrays section of this unit. You can now do the following review lessons and FRQs at the end of the unit and College Board Progress Checks in the AP Classroom.

We encourage you to work in pairs or groups to tackle the following challenging FRQ problems and take them one step at a time. These will get easier with practice!

We also encourage you to finish the very fun Picture Lab lessons at the end of the unit in PictureLab.

You have attempted of activities on this page

Before you keep reading...

Before you keep reading...

4.13. Implementing 2D Array Algorithms¶

4.13.1. Sum, Average, Min, Max 2D Array Algorithms¶

4.13.2. Subsection of a 2D Array for a Property¶

4.13.3. Duplicates in 2D Arrays¶

4.13.4. Rotate and Reverse¶

4.13.5. Review and FRQ Practice with 2D arrays¶