5 Steps to a 5: AP Computer Science A 2024 - Klipp D.B., Johnson D.R., Paymer C.A. 2023

Unit 8 2D Array
STEP 4 Review the Knowledge You Need to Score High

IN THIS UNIT

Summary: The data structures that we've worked with so far have all been one-dimensional arrays because they stored a simple list of data values. Sometimes using an array or ArrayList is not enough. A two-dimensional array stores values in rows and columns like in a table. In this unit we will discuss 2D arrays. We will also look back at some of the code that we already wrote and modify it to work with a 2D array.

Key Ideas

A two-dimensional (2D) array is a data structure that is an array of arrays.

The 2D array simulates a rectangular grid with coordinates for each location based on the row and the column.

2D arrays can be traversed using row-major or column-major order.

All standard array or ArrayList algorithms can be applied to 2D arrays.

The 2D Array

Definition of a 2D Array

A two-dimensional (2D) array is a complex data structure that can be visualized as a rectangular grid made up of rows and columns. Technically, it is an array of arrays. It can store any kind of data in its slots; however, each piece of data has to be of the same data type.

Two-dimensional arrays are actually fun to work with and are very practical when creating grid-style games. Many board games are based on a grid: checkers, chess, Scrabble, etc. Many apps are based on grids too: CandyCrush, 2048, Ruzzle. I’m sure you can think of others.

Declaring a 2D Array and Initializing It Using a Predefined List of Data

When you know the values that you want to store in the 2D array, you can declare the array and store the values in it immediately. This operation is just like what we did for the one-dimensional array. Two pairs of brackets, [ ][ ], are used to tell the computer that it is not a regular variable.

General Form for Creating a 2D Array Using an Initializer List

Note: Pairs of curly braces are used to wrap the first row, then the second row, and so on. If you look closely at this visual, you will see how a 2D array is really an array of arrays.

Example

Declare a 2D array that represents a CandyCrush board with four rows and three columns. Notice that the four rows are numbered 0 through 3 and the three columns are numbered 0 through 2.

This is the visual representation of what the candyBoard array looks like inside the computer.

Rows and Columns of the 2D Array

Every cell in a 2D array is assigned a pair of coordinates that are based on the row number and the column number. The first pair of brackets represents the row number and the second pair of brackets represents the column number. The rows and columns both begin at zero and end with one less than the number of rows or columns, just like they did with arrays and ArrayLists.

Example

Change the “Lozenge” in row 2 and column 0 to be a “Lemon Drop”.

candyBoard[2][0] = "Lemon Drop";

Declaring a 2D Array Using the Keyword new

A 2D array object can be created using the keyword new. Every cell in the 2D array is filled with the default value for its data type.

General Form for Creating a 2D Array Using the Keyword new

dataType[][] nameOfArray = new dataType[numberOfRows][numberOfColumns];

Example

Declare a 2D array that represents a Sudoku Board that has nine rows and nine columns. Put the number 6 in row 2, column 7:

How to Refer to the Rows and Columns in a 2D Array

The position, myBoard[0][5], is read as row 0, column 5.

The position, myBoard[3][0], is read as row 3, column 0.

Using the length Field to Find the Number of Rows and Columns

The number of rows in a 2D array is found by accessing the length field. The number of columns in a 2D array is found by accessing the length field on the name of the array along with one of the rows (it doesn’t matter which row).

Example 1

Retrieve the number of rows from a 2D array:

Example 2

Retrieve the number of columns from a 2D array:

Accessing a 1-D Array from Within the 2D Array

Consider this 2D array declaration:

double[][] myBoard = new double[8][3];

myBoard[0] is a 1-D array that consists of the row with index 0.

myBoard[5] is a 1-D array that consists of the row with index 5.

Traversing a 2D Array in Row-Major Order

Traversing a 2D array means to visit every cell in the grid. This can be done in many different ways, but for the AP Computer Science A exam, you need to know two specific ways.

Row-Major order is the process of traversing a 2D array in the manner that English-speaking people read a book. Start at the top left cell and move toward the right along the first row until you reach the end of the row. Then start at the next row at the left-most cell, and then move along to the right until you reach the end of that row. Repeat this process until you have visited every cell in the grid and finish with the bottom-right cell.

Example

Traverse an array in Row-Major order. Start with row 0 and end with the last row. For each row, start with column 0 and end with the last column.

Java Code 1: Using a nested for loop

Java Code 2: Using enhanced for loop

Traversing a 2D Array in Column-Major Order

Column-Major order is the process of traversing a 2D array by starting at the top-left cell and moving downward until you reach the bottom of the first column. Then start at the top of the next column and work your way down until you reach the bottom of that column. Repeat this until you have visited every cell in the grid and finish with the bottom-right cell.

Example

Traverse an array in column-major order using a nested for loop. Start with column 0 and end with the last column. For each column, start with row 0 and end with the last row.

ArrayIndexOutOfBoundsException

As with a 1-D array, if you use an index that is not within the 2D array, you will get an ArrayIndexOutOfBoundsException.

Fun Fact: Java provides support for multi-dimensional arrays, such as 3D arrays; however, the AP Computer Science A Exam does not require you to know about them.

More Algorithms

All standard array/ArrayList algorithms can be applied to 2D arrays. Let’s revisit a few of them from units 6 and 7.

The Accumulate Algorithm

Remember the baseball scenario from unit 6 where we found the total number of hits the team had? We are going to make modifications so instead of finding the total hits from one game (1D array) we will find the total number of hits for all the games in the season (2D array).

General Problem: Add up all of the hits for a baseball team.

Refined Problem: Write a method that finds the sum of all of the hits in an 2D array of hits.

Final Problem: Write a method called findSum that has one parameter: a 2D array of ints. The method should return the sum of all of the elements in the array.

Algorithm:

Step 1: Create a variable called sum and set it equal to zero

Step 2: Look at each of the elements in the list

Step 3: Add the element to the sum

Step 4: Continue until you reach the end of the list

Step 5: Return the sum

Pseudocode:

Java code using a 2D array (Row-Major order)

The Find-Highest Algorithm

What is the highest score on your favorite video game? As more people play a game, how does the computer figure out what is the highest score in the list?

General Problem: Find the highest score out of all the scores for a video game.

Refined Problem: Write a method that finds the highest score in a list of scores.

Final Problem: Write a method called findHigh that has one parameter: a 2D array. The method should return the largest value in the array.

Solution: Let the highest be the first element in the list.

Algorithm:

Step 1: Create a variable called high and set it to the first element in the list

Step 2: Look at each of the scores in the list

Step 3: If the score is greater than the high score, then make it be the new high score

Step 4: Continue until you reach the end of the list

Step 5: Return the high score

Pseudocode:

Java code using a 2D array (Row-Major order)

The Connect-Four Advanced Algorithm

Connect Four is a two-player game played on a grid of six rows and seven columns. Players take turns inserting disks into the grid in hopes of connecting four disks in a row to win the game. You have been hired to work on the app version of the game, and it is your responsibility to determine whether a player has won the game.

General Problem: Determine if a player has won the game of Connect Four.

Refined Problem: The Connect Four app version uses a 2D array that is 6 × 7. After a player makes a move, determine if he or she has won by checking all possible ways to win. If four of the same color disks are found in a line, then the game is over. Decide who won the game (player one or player two). A way to win can be vertical, horizontal, diagonally downward, or diagonally upward.

Final Problem: Write a method called checkForWinner that has one parameter: a 2D array of int. The 2D array consists of 1s and 2s to represent a move by player one or player two. Cells that do not contain a move have a value of 0. This method checks all four directions to win (vertical, horizontal, diagonally downward, and diagonally upward). The method should return the number of the player who won or return 0 if nobody has won.

Algorithm (for vertical win):

Note: There are a total of 21 ways to win vertically. Start with the top left cell and move in Row-Major order.

Step 1: Start with row 0 and end with row 2 (row 2 is four less than the number of rows)

Step 2: Start with column 0 and end with column 6 (use every column)

Step 3: If current cell value is not equal to 0 and the current cell = cell below it = cell below it = cell below it, then a player has won

Step 4: Continue until you reach the end of row 2

Step 5: Return the player who won or zero

Pseudocode (for vertical win):

Algorithm (for diagonal downward win):

Note: There are a total of 12 ways to win diagonally downward. Start with the top left cell and go in Row-Major order.

Step 1: Start with row 0 and end with row 2 (row 2 is four less than the number of rows)

Step 2: Start with column 0 and end with column 3 (column 3 is four less than the number of columns)

Step 3: If current cell value is not equal to 0 and the cell below and to the right = cell below and to the right = cell below and to the right, then a player has won

Step 4: Continue until you reach the end of row 2

Step 5: Return the player who won or zero

Pseudocode (for diagonal downward win):

Note: I have provided the algorithm and pseudocode for only the vertical win and the diagonal downward win. The code for these, as well as the horizontal win and the diagonal upward win, are provided in the Java code that follows.

Java Code: Using a 2D array and nested for loops (includes all four ways to win):

Rapid Review

The 2D Array

• A 2D array is a complex data structure that can store a grid of data of the same type.

• The 2D array is actually an array of arrays.

• The rows and columns are numbered starting with zero.

• The top row is row zero. The left-most column is column zero.

• The access to each cell in the 2D array is always [row][column].

• The indices of the top-left cell are [0][0].

• The index of the bottom-right cell is [numberOfRows − 1][numberOfColumns − 1].

• Two-dimensional arrays can store primitive data or object data.

• To store a value in a 2D array: arrayName[rowNumber][columnNumber] = value;

• To retrieve the number of rows in a 2D array, use arrayName.length.

• To retrieve the number of columns in a rectangular 2D array, use arrayName[0].length. Note: Any valid row number works instead of 0.

• Using an index that is not in the range of the 2D array will throw an ArrayIndexOutOfBoundsException.

Traversing a 2D Array

• To traverse a 2D array means to visit each element in every row and column.

• The most common way to traverse a 2D array is called Row-Major order.

• Row-Major order starts in the upper-left location [0][0], and travels to the right until the end of the row is reached. Then the next move is to the next row [1][0]. The process is repeated until the right-most column in the bottom row is reached.

• The second most common way to traverse a 2D array is called Column-Major order.

• Column-Major order also starts in the upper-left location [0][0]; however, it travels down until the end of the first column is reached. Then, the next move is to the top of the next column [0][1]. The process is repeated until the bottom row in the right-most column is reached.

• All of the 2D arrays on the AP Computer Science A Exam will be rectangular.

Accumulate Algorithm

• The accumulate algorithm finds the sum of all the items in a list.

• It looks at each element in the list one at a time, adding the value to a total.

Find-Highest Algorithm

• The find-highest algorithm finds the largest value in a list.

• It looks at each element in the list one at a time, comparing the value to the current high value.

• Common ways to implement this algorithm include initializing the highest value with the first value in the list or to an extremely small negative number.

• The find-highest algorithm can be modified to find the lowest item in a list.

Review Questions

Basic Level

1. Consider the following code segment.

What value will sum contain after the code segment is executed?

(A) The sum of all the values in the table

(B) The sum of all the values in the major diagonal (top left to bottom right)

(C) The sum of all the values in the minor diagonal (top right to bottom left)

(D) The sum of all the values in both diagonals

(E) The sum of all the values in the last row

2. Consider the following code segment.

Which of the following best describes the result of executing the code segment?

(A) Each element in the two-dimensional array table contains the value 0.

(B) Each element in the two-dimensional array table contains a nonnegative value.

(C) Each element in the two-dimensional array table contains a nonpositive value.

(D) Each element in the two-dimensional array table contains the opposite value from when it was initialized.

(E) Each element in the two-dimensional array table contains the value row — col.

3. Consider the following incomplete method.

Method findRowSum is intended to return the sum of elements in parameter mat that are in row n, also passed as a parameter. Which of the following code segments could be used to replace // missing code so that findRowSum will work as intended?

Advanced Level

4. Consider the following definition and code segment.

What values will table contain after the code segment is executed?

5. Modifying a 2D array

Write a method that takes a 2D array as a parameter and returns a new 2D array.

The even rows of the new array should be exactly the same as the array passed in.

The odd rows of the new array should be replaced by the contents of the row above.

Here is the declaration for your method.

public int[][] modify(int[][] arr)

6. Filling a 2D array

Write a method that will fill in a 2D boolean array with a checkerboard pattern of alternating true and false. The upper-left corner (0, 0) should always be true.

Given a grid size of 3 × 4, the method should return:

The method will take the number of rows and columns as parameters and return the completed array. Here is the method declaration and the array declaration:

7. Find all the songs that contain the word “Love” in the title.

One of the most popular themes in music lyrics is love. Suppose a compilation of thousands of songs is stored in a grid. Count the number of songs that contain the word “Love” in the title.

Write a method that counts the number of song titles that contains a certain string in the title. The method has two parameters: a 2D array of String objects and a target string. The method should return an integer that represents the number of strings in the 2D array that contains the target string.

The 2D array passed to the method:

Answers and Explanations

1. The answer is C.

• This is not a nested for loop, which means each element of the 2D array will not be accessed.

• The first element that is accessed would be the last row, 1st column, table [length - 0 - 1] [0].

• The second element that is accessed would be the next to last row and the 2nd column. Table[length - 1 - 1] [1].

• The loop will continue moving upwards along the minor diagonal until all elements are accessed and added to sum.

2. The answer is B

• This uses a nested for loop with both loop control variables starting at 0 and ending at the length of the row or column, which means each element of the 2D array is potentially accessed.

• It tests each element against 0. If that element is negative (< 0), it will be changed to the opposite, which is positive.

• After the loops are complete, each element in the table will be nonnegative (positive or 0).

3. The answer is D.

• Only one row needs to be summed, so a single for loop is appropriate.

• Since row n is the row to be summed, this value needs to remain unchanged throughout the loop.

• Choice D correctly accesses each element in the correct row in mat.

4. The answer is D.

• Choice A would be the result if both loops ended at the length of the table instead of length-1.

• Choice B would be the result if both loops ended at the length of the table instead of length-1 and the operation was addition (+) and not multiplication (*).

• Choice C would be the result if the operation was addition (+) and not multiplication (*).

• Choice E would be the result if the loop started at the last row.

5. We can find the even rows by using the condition (row % 2 == 0). In other words, if I can divide the row number by 2 and not have a remainder, it’s an even row. Even rows just get copied as is. Odd rows get copied from the row above [row − 1].

Here is the completed method.

6. There are many ways to solve this problem. This implementation uses the fact that grid[row][col] is true when row + col is even.

Here is a tester class so you can see if the way you wrote the method was also correct. Copy in your code. Try it with all shapes and sizes of grid to test it thoroughly.

7. Find all the songs that contain the word “Love” in the title.

Algorithm:

Step 1: Initialize a count variable to zero

Step 2: Look at each of the scores in the 2D array (using Row-Major order)

Step 3: If the song title contains the target String, then increment the count

Step 4: Continue until you reach the end of the list

Step 5: Return count

Pseudocode:

Java code: