4.13 Implementing 2D Array Algorithms

4.13 Implementing 2D Array Algorithms

Each coding exercise has its own folder. Open its .java file and press Run to try it. Run Tests checks every graded exercise in this lesson at once.

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

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.

Exercise 1

What will the 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.

Open the 01-lca2dloopPart folder and edit Total.java. Press Run to try it; Run Tests checks it (2 tests).

Check your understanding: The following has the correct code to find the largest value in a 2D array. You will be told if any of the blocks are in the wrong order. — answer it on CS Awesome: https://runestone.academy/ns/books/published/csawesome2/topic-4-13-2Darray-algorithms.html#max2DArrayParsons

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

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.

Exercise 2

Looping through just part of a 2D array.

Open the 02-lca2dloopPart2 folder and run Count.java. It is an example, so it has no tests.

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!

Exercise 3

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.

Open the 03-noDups2DArray folder and run Duplicates.java. It is an example, so it has no tests.

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.

Exercise 4

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

Open the 04-rotate2DArray folder and edit Rotate.java. This one is not graded, so check it yourself.

Review and FRQ Practice with 2D arrays

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. You can wait to do College Board Progress Check C in the AP Classroom at the end of the unit.

• 2D Arrays Summary
• 2D Arrays Toggle Code Practice
• 2D Arrays Code Practice
• 2D Arrays More Code Practice
• 2D Arrays Exercises

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!

• FRQ 4 on 2D Array
• Gray Image A FRQ
• Gray Image B FRQ
• Route Cipher A and B FRQ

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