UNIT 8
2D Array
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.
Example
Change the "Lozenge" in row 2 and column 0 to be a "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
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:
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 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 3-D 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.
The Accumulate Algorithm
Suppose you have a list of all the baseball players on a team and you want to find the total number of hits that the team had. As humans, we can do this quite easily. Just add them up. But how do you teach a computer to add up all of the hits?
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?
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.
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):
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
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?
(A) 
(B) 
(C) 
(D) 
(E) 
Advanced Level
4. Consider the following definition and code segment.
What values will table contain after the code segment is executed?
(A) 
(B) 
(C) 
(D) 
(E) 
5. Free-Response Practice: 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.
For example, if the input array is:
Then the returned array should be:
Here is the declaration for your method.
6. Free-Response Practice: 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:
