Please enable JavaScript to use CodeHS

Chapter 8

2D Arrays

8.2 Traversing 2D Arrays

As discussed in the previous lesson, individual elements in a 2D array can be accessed using [row][column] indexing:

String[][] cities = {{"New York City","Albany", "Ithaca"},
{"Los Angeles", "San Francisco", "San Jose"},
{"Houston", "Dallas", "San Antonio"}}; 

System.out.println(cities[1][1]);  // prints San Francisco
Plain text

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 2D Array - Nested Iteration

Traversing a 1D array required the use of a for loop to iterate through each element in the array:

int[] nums = {1,2,3,4,5};
for(int index = 0; index < nums.length; index++)
{
   System.out.println(nums[index]);
}
Plain text

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:

int[][] nums = {{1,2,3,4,5},{6,7,8,9,10},{11,12,13,14,15}};
for(int row = 0; row < nums.length; row++)
{
   for(int col = 0; col < nums[row].length; col++)
   {
      System.out.println(nums[row][col]);
   }
}
Plain text

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:

//column-major order
int[][] nums = {{1,2,3,4,5},{6,7,8,9,10},{11,12,13,14,15}};
for(int col = 0; col < nums[0].length; row++)
{
   for(int row = 0; row < nums.length; row++)
   {
      System.out.println(nums[row][col]);
  }
}
Plain text

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.

Enhanced For Loop with 2D Arrays

2D arrays can also be iterated over using an enhanced for loop:

//enhanced for loop
int[][] nums = {{1,2,3,4,5},{6,7,8,9,10},{11,12,13,14,15}};
for(int[] list: nums)
{
   for(int num: list)
   {
      System.out.println(num);
   }
}
Plain text

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.

Linear Search with 2D Arrays

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:

public String search(int[][] array2D, int key)
{
   for(int rowIndex = 0; rowIndex < array2D.length; rowIndex++)
   {
      for(int colIndex = 0; colIndex < array2D[rowIndex].length; colIndex++)
      {
         if(array2D[rowIndex][colIndex] == key) 
         {
            return key + " is located at: " + rowIndex + "," + colIndex;
         }
      }
   }
   return key + "is not in this 2D array.";
}
Plain text

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.

Standard 2D Array Algorithms

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:

int[][] scores = {{2,3,4,5,6},{7,6,5,4,3}}

//Initialize value here
for(int[] row : scores)
{
   for (int i = 0; i < row.length; i++){
   //Perform calculation here

   }
}

//Report results here
Plain text

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:

int[][] scores = {{2,3,4,5,6},{7,6,5,4,3}}

//Initialize tracker variable
for(int[] row : scores)
{
   for (int i = 0; i < row.length; i++){
      //Conditionally check properties
      if(condition){ ... }
   }
}

//Report results here
Plain text

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:

int[][] scores = {{2,3,4,5,6},{7,6,5,4,3}}
int[][] alteredScores;
for(int row = 0; row < scores.length; row++)
{
   for (int col = 0; col < scores[row].length; col++){
      //add values from grade to alteredArray

   }
}

//Report results here
Plain text

Traversing Gradebook

Linear Search 2D Arrays

Row vs. Column Major

Check Your Understanding

  1. 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?

Exercise: Sum Rows in a 2D Array

Write the methods

public static int sumRow(int[][] array, int row)
Plain text

and

public static int sumArray(int[][] array)
Plain text

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.