8.2 Traversing 2D Arrays
As discussed in the previous lesson, individual elements in a 2D array can be accessed using [row][column]
indexing:
The process of accessing an individual element can be used during a 2D array traversal, which can be used to return all elements in a 2D array.
Traversing a 1D array required the use of a for
loop to iterate through each element in the array:
For a 2D array, this initial traversal is used to access each array in the 2D array, and a nested for
loop is needed to access each element within the selected array:
The outer for
loop accesses each list in the 2D array nums
, while the inner for
loop accesses each value within the list. During the first iteration of the outer for
loop, the value of row
is 0. When the inner for
loop iterates, the value of col
will increase each time. The values nums[0][0]
, nums[0][1]
, nums[0][2]
, nums[0][3]
, nums[0][4]
will all be printed to the console, and then the value of row
will increase to 1. This process will continue until all values in the 2D array have been printed.
Notice that the inner for
loop uses the length of the individual list that is being accessed. This ensures that each element in the array will be iterated over.
This form of iteration is referred to as row-major order. Row-major order is the practice of iterating over each row in an array. In the example above, each list is searched from beginning to end before the next list is searched:
2D arrays can also be searched in column-major order, where a single column in a 2D array is searched before the next column is iterated over:
Column major order requires a slight alteration to the row-major traversal algorithm:
For column-major order, the inner for
loop iterates through all row values, while the outer for
loop iterates through each column. During the first iteration of the outer for
loop, the value of col
is 0. When the inner loop iterates, the value of row
increases by one until the entire 2D array has been searched. The values num[0][0]
, nums[1][0]
, nums[2][0]
will be printed to the console before the value of col
increases to 1.
While column-row major can be useful when iterating through 2D arrays, Java is more efficient at iterating over row-major order iterations. For smaller 2D arrays, this difference is inconsequential, but for larger 2D arrays, column-major order iteration may take a substantial amount of time compared to row-major iteration.
2D arrays can also be iterated over using an enhanced for
loop:
Enhanced for
loops with 2D arrays still require the use of nested loops. In the outer for
loop, the enhanced for
loop is accessing each list in the 2D array. Notice that the data type int[]
is included in the for
loop call, indicating that the variable list
in each iteration will be an array of integers. The inner for
loop then iterates over each item in the list
, and prints out the integer which has been stored in the variable num
. The type of the variable in the inner for
loop should match the same type of the array.
Because enhanced for
loops iterate through each array in a 2D array, enhanced for
loops always use row-major order to iterate through a 2D array.
Just as arrays used linear search to find elements, 2D arrays can also use linear search to find values. Here is the general algorithm for searching a 2D array:
In the case of 2D arrays, each row needs to be searched individually. The outer loop simply accesses each individual row of the 2D array while the inner loop is applying search to the array. If the item is not found in any of the arrays, then the return value indicating that the key cannot be found should be placed outside of both for
loops. This is to ensure that this only returns if none of the arrays in the 2D array contain that particular value.
2D arrays have a series of standard algorithms that can be used to traverse their values:
- Mathematical Analysis
- Determine a minimum or maximum value
- Compute a sum, average, or mode
- Analyzing Element Properties
- Determine if at least one element has a particular property
- Determine if all elements have a particular property
- Access all consecutive pairs of elements
- Determine the presence or absence of duplicate elements
- Determine the number of elements meeting specific criteria
- Reordering Elements
- Shift or rotate elements left or right
- Reverse the order of the elements
Each of these subsets uses a distinct algorithm to analyze arrays:
Mathematical Analysis
Mathematical analysis is done by initializing a value, like sum before the nested for
loops, and then performing calculations on the array values within the inner for
loop so that all values in the 2D array are added to the final calculation. The results can be reported after the nested loop is finished executing:
Analyzing Element Properties
To determine if elements have a particular property, initialize a tracker value before the nested for
loop traversal, and then conditionally check for that tracker while traversing the array:
Reordering Elements
To make alterations to the list, such as reverse the order or shifting elements, the general format requires that a new 2D is created that will then hold the values in the order that they should be rearranged. Each iteration through the initial array will add a value from the initial array to the altered array:
-
Incorrect
Correct
No Answer was selected
Invalid Answer
A 2D double array is declared and initialized to track the terrain of a city park. Each value in the 2D array represents the height of a particular latitude and longitude above sea level. Longitude is represented by the columns in the 2D array and latitude is represented by each row in the 2D array.
The creator of this 2D array would like to look at the height of the city park along the latitude 100.0 - which traversal method would make the most sense in order to do so?
Write the methods
and
sumRow()
returns the sum of row row
in the 2D array called array
.
sumArray()
returns the sum of all of the elements in the 2D array called array
. You should use sumRow()
to implement this method.
In main, print the sum of all the elements in the array.