Traversing 2D Arrays

When traversing/looping through a 1D array, only one loop is required to access all elements within the array. For 2D arrays, we need to loop within the loop, which would be known as a for loop.

Java loop structure:

for (first execution; condition; executed after every loop) {
    // Code that provides an action
}

An example using this structure would be something like:


```Java
for (int i = 0; i < 10; i++) {
    System.out.println(i);
}

0
1
2
3
4
5
6
7
8
9

Since the base is at 0, this code will print: 1 2 3 4 5 6 7 8 9

How can you traverse a 1D array?

Let’s create an array and name it Array1.

int[] Array1 = {1, 2, 3};
for (int i = 0; i < Array1.length; i++) {
    System.out.println(Array1[i]);
}

1
2
3

In this code segment, we set our variable i to 0. Then we write a condition where if i is less than Array1.length, it prints Array1[i]. Then we add 1 to i.

How can you traverse 2D arrays?

Let’s use the same variable for this example, Array1.

This creates an array that contains 2 rows and 3 columns.

int[][] Array1 = {
    {1, 2, 3}, 
    {4, 5, 6}, 
    {7, 8, 9}
};
for (int i = 0; i < Array1.length; i++) {
    // This makes the variable i equal to 0, then the condition would be when i is less than the Array1 length, 
    // then it will loop to the next number, then add 1 to i.
    
    for (int j = 0; j < Array1[i].length; j++) {
        System.out.println(Array1[i][j]);
    }
}


1
2
3
4
5
6
7
8
9

This sets j equal to 0. Then the next statement says while j is less than whatever the array length is within Array1 at Array1[i], it will display the value of Array1[i][j], then it will add 1 to j.

Without the loop, the code will look like this:

System.out.println(Array1[0][0]); // 1
System.out.println(Array1[0][1]); // 2
System.out.println(Array1[0][2]); // 3
System.out.println(Array1[1][0]); // 4
System.out.println(Array1[1][1]); // 5
System.out.println(Array1[1][2]); // 6
System.out.println(Array1[2][0]); // 7
System.out.println(Array1[2][1]); // 8
System.out.println(Array1[2][2]); // 9

This displays how the rows loop through the length of the array.

public class Main {
    public static void main(String[] args) {
        int[][] Array1 = {
            {1, 2, 3},
            {4, 5, 6},
            {7, 8, 9}
        };
        for (int i = 0; i < Array1.length; i++) {
            for (int j = 0; j < Array1[i].length; j++) {
                System.out.println(Array1[i][j] + " (traversing to next row " + i + ")");
            }
        }
    }
}
Main.main(null);

1 (traversing to next row 0)
2 (traversing to next row 0)
3 (traversing to next row 0)
4 (traversing to next row 1)
5 (traversing to next row 1)
6 (traversing to next row 1)
7 (traversing to next row 2)
8 (traversing to next row 2)
9 (traversing to next row 2)

Popcorn Hack

An array called find is shown below. In this popcorn hack, I want you to loop through the numbers until you get to the number that doesn’t belong (55). Then print that number along with which row and column it is located in.

public class Main {
    public static void main(String[] args) {
        int find[][] = {
            {10, 20, 30},
            {40, 55, 60},
            {70, 80, 90},
        };

        // Write your code here
    }
}
Main.main(null);

Column Major Order instead of Row Major Order

  • Definition: Column Major Order involves processing the elements of a 2D array by columns before rows.

  • Switching Loops:
    • Outer Loop: Iterate through columns instead of rows.
    • Inner Loop: Iterate through rows instead of columns.
  • Implementation Changes:
    • Replace Array1[i].length with Array1[0].length to focus on the number of columns.
  • Iteration Process:
    • For each column (indexed by j), process all rows (indexed by i).
    • Print the value at the current column for each row.
    • After processing all rows for the current column, increment the column index j to move to the next column.

  • Example: In an array like {1, 2, 3}, the inner loop runs for the length of the row (number of columns).

  • Overall Effect: By reversing the loop structure, columns are processed before rows, achieving a Column Major Order traversal.
public class Main {
    public static void main(String[] args) {
        int[][] Array1 = {
            {1, 2, 3},
            {4, 5, 6},
            {7, 8, 9}
        };
        for (int j = 0; j < Array1[0].length; j++) {
            System.out.println("Column " + (j + 1));
            for (int i = 0; i < Array1.length; i++) {
                System.out.println(Array1[i][j]);
            }
        }
    }
}
Main.main(null);

This displays each column and what is within each column.

Algorithms

Linear search is a very easy and sequential searching algorithm that allows us to find certain elements within the array or not in the array. This is done by traversing through each element.

Here is an example of a linear search within a 2D array:

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[][] array = {
            {10, 15, 20},
            {25, 30, 35},
            {40, 22, 50}
        };

        int target = 22; // The number we want to search for
        int[] result = linearSearch(array, target);

        if (result[0] != -1) {
            System.out.println("Element found at index: " + Arrays.toString(result));
        } else {
            System.out.println("Element not found.");
        }
    }

    static int[] linearSearch(int[][] arr, int target) {
        for (int i = 0; i < arr.length; i++) { // Loop through rows
            for (int j = 0; j < arr[i].length; j++) { // Loop through columns
                if (arr[i][j] == target) { // Check if the current element matches the target
                    return new int[] {i, j}; // Return the row and column index
                }
            }
        }
        return new int[] {-1, -1}; // Return -1 if the target is not found
    }
}
Main.main(null);

Element found at index: [2, 1]

Checks each element in the array sequentially until the target value is found or the end of the array is reached. Can be implemented on both sorted and unsorted arrays.

Divide the sorted array in half repeatedly to locate the target value. It starts by comparing the target value to the middle element of the array. If the target is equal to the middle element, the search is complete. If the target is less than the middle element, the search continues in the lower half; if greater, it continues in the upper half. This process is repeated until the target is found or the search space is exhausted.

public class Main {
    public static void main(String[] args) {
        int[][] array = {
            {1, 2, 3, 4},
            {5, 6, 7, 8},
            {9, 10, 11, 12},
            {13, 14, 15, 16}
        };
        
        int target = 10;
        int[] result = binarySearch2D(array, target);
        
        if (result[0] != -1) {
            System.out.println("Element found at: Row " + result[0] + ", Column " + result[1]);
        } else {
            System.out.println("Element not found.");
        }
    }
    
    public static int[] binarySearch2D(int[][] array, int target) {
        int rows = array.length;
        if (rows == 0) return new int[] {-1, -1};
        int cols = array[0].length;
        
        int left = 0;
        int right = rows * cols - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int midValue = array[mid / cols][mid % cols];
            
            if (midValue == target) {
                return new int[] {mid / cols, mid % cols}; // Return the row and column index
            }
            if (midValue < target) {
                left = mid + 1; // Move to the right half
            } else {
                right = mid - 1; // Move to the left half
            }
        }
        
        return new int[] {-1, -1}; // Target not found
    }
}
Main.main(null);

Element found at: Row 2, Column 1

Popcorn Hack:

Create your own 2D array and use either binary search or linear search. (maybe both 😏 )

public class Main {
    public static void main(String[] args) {
        int[][] array = {
        }
    }
}
Main.main(null);

Sorting a 2D Array

Sorting a 2D array can be approached in two ways:

Row-wise Sorting: Each row is sorted independently, similar to sorting a 1D array.
Global Sorting: Flatten the 2D array into a 1D array, sort it, and then reshape it back into the 2D form.

public class Main {
    public static void main(String[] args) {
        int[][] array = {
            {9, 3, 1},
            {4, 6, 5},
            {7, 2, 8}
        };

        for (int i = 0; i < array.length; i++) {
            Arrays.sort(array[i]); // Sort each row individually
        }

        // Print the sorted 2D array
        for (int[] row : array) {
            System.out.println(Arrays.toString(row));
        }
    }
}
Main.main(null);


[1, 3, 9]
[4, 5, 6]
[2, 7, 8]

Class Declaration:

  • The code is contained within a public class named Main.

  • Main Method:
    • The main method is the entry point of the program where execution begins.
  • 2D Array Initialization:
    • A 2D array named array is initialized with three rows, each containing three integers.
    • The initial array looks like this: 
      {
    {9, 3, 1},
    {4, 6, 5},
    {7, 2, 8}
}
  • Sorting Each Row:
    • A for loop iterates through each row of the 2D array using the index i.
    • The Arrays.sort(array[i]) method is called for each row:
      • This method sorts the elements of the current row in ascending order.
      • After sorting, the array transforms as follows:
        • First row: {1, 3, 9}
        • Second row: {4, 5, 6}
        • Third row: {2, 7, 8}
  • Printing the Sorted Array:
    • A for-each loop iterates through each row of the sorted array.
    • System.out.println(Arrays.toString(row)) prints each row as a string representation:
      • Each sorted row is displayed on a new line, resulting in the following output: 
        [1, 3, 9]
[4, 5, 6]
[2, 7, 8]
  • Program Execution:
    • The line Main.main(null); invokes the main method, which executes the code above.

Global Sorting:

Questions for Further Discussion

  • What are some scenarios where global sorting might be more beneficial than row-wise or column-wise sorting?
  • How does the complexity of flattening, sorting, and reshaping compare to other data manipulation techniques?

    Steps for Global sorting:

    Flattening the 2D array, sorting it, and then reshaping it.

public class Main {
    public static void main(String[] args) {
        int[][] array = {
            {9, 3, 1},
            {4, 6, 5},
            {7, 2, 8}
        };

        int rows = array.length;
        int cols = array[0].length;
        int[] flatArray = new int[rows * cols];
        
        // Flatten the 2D array into a 1D array
        int index = 0;
        for (int[] row : array) {
            for (int num : row) {
                flatArray[index++] = num;
            }
        }

        // Sort the 1D array
        Arrays.sort(flatArray);

        // Reshape the 1D array back into a 2D array
        index = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                array[i][j] = flatArray[index++];
            }
        }

        // Print the globally sorted 2D array
        for (int[] row : array) {
            System.out.println(Arrays.toString(row));
        }
    }
}
Main.main(null);

[1, 2, 3]
[4, 5, 6]
[7, 8, 9]

Steps for Global Sorting

  1. Initialize the 2D Array:
    • Define the 2D array with specific dimensions and values.
  2. Flatten the Array:
    • Create a new 1D array that can hold all the elements from the 2D array.
    • Use nested loops to copy each element from the 2D array to the 1D array.
  3. Sort the 1D Array:
    • Utilize a sorting method to arrange the elements in the 1D array in the desired order.
  4. Reshape into 2D Array:
    • Reassign the sorted values back into the original 2D array using nested loops.
  5. Print the Sorted 2D Array:
    • Display the final sorted 2D array to visualize the results.

Benefits of Global Sorting

  • Unified Order: Provides a single sorted view of all elements, regardless of their original positions.
  • Simplified Processing: Easier to apply algorithms that require a sorted list of elements.

Popcorn Hack:

Write a code that performs global sorting on your own 2D array.

public class PopcornHack {
    public static void main(String[] args) {
        // Step 1: Create a 2D array
        int[][] array = {
            { /* Fill in your array data here */ },
            { /* More data */ },
            { /* More data */ }
        };

        // Step 2: Define your target number
        int target = /* Choose a number to search for */;

        // Step 3: Call the search method (choose either linear or binary search)
        int[] result = /* Call your chosen search method here */;

        // Step 4: Output the result
        if (result[0] != -1) {
            System.out.println("Element found at: Row " + result[0] + ", Column " + result[1]);
        } else {
            System.out.println("Element not found.");
        }
    }

    // Option 1: Linear Search (Copy and paste the linear search method here)
    // Option 2: Binary Search (Copy and paste the binary search method here)
}

Enhanced For-Each Loop for 2D Arrays

  • 2D arrays are arrays that contain other arrays.
  • You can use a nested enhanced for-each loop to iterate through all the elements in a 2D array:
    • The outer loop iterates over each inner array (or row).
    • The inner loop goes through all the values within that specific inner array.
  • For example, with a 2D array of type String:
    • The variable type for the outer loop should match the type of the inner arrays, which is String[].
    • Ensure that the variable types in the for-each loops align with the types of the elements in the array.
  • Enhanced for-each loops simplify code by eliminating the need for manual index management and square brackets.
  • These loops are most suitable when you do not plan to modify the original values in an array of primitive types:
    • The loop variable (e.g., fruit in the inner loop) will not change the values stored in the array.
  • Here’s an example code segment that demonstrates how to use enhanced for-each loops with a 2D array:
public class Main {
    public static void main(String[] args) {
        // Define a 2D array of strings
        String[][] fruits = {
            {"Apple", "Banana", "Cherry"},
            {"Date", "Fig", "Grape"},
            {"Honeydew", "Kiwi", "Lemon"}
        };

        // Use enhanced for-each loops to iterate through the 2D array
        for (String[] row : fruits) { // Iterate through each inner array (row)
            for (String fruit : row) { // Iterate through each element in the row
                System.out.print(fruit + " "); // Print the fruit name
            }
            System.out.println(); // Print a new line after each row
        }
    }
}
Main.main(null);

Apple Banana Cherry 
Date Fig Grape 
Honeydew Kiwi Lemon

Algorithms involving traversing a 2D Array

In the APCSA AP exam, you may be asked to write an algorithm for a 2D array based on a given scenario. College Board will present a problem, and your task will be to develop an algorithm that addresses it.

Here’s an example from the 2023 College Board APCSA exam:

The question required students to write the countIncreasingCols method. This method counts how many columns in the grid (a 2D array filled with random numbers) are in increasing order.

public class Main {
    public static void main(String[] args) {
        System.out.print("columns increasing = " + countIncreasingCols());
    }
   
}
public int countIncreasingCols() {
    int count = 0;
    int[][] grid = {
        {1, 2, 3,4,5},
        {6, 7, 8,32,10},
        {11, 12, 23,14,15},
        {16, 17, 18,19,5}
    };
    
    for (int j = 0; j < grid[0].length; j++) { // Loop through each column
        boolean isIncreasing = true; 
        if (grid.length > 1) { // Ensure there is more than one row
            for (int i = 1; i < grid.length; i++) { // Loop through each row
                if (grid[i][j] <= grid[i - 1][j]) { // Check if the current element is less than or equal to the previous one
                    isIncreasing = false; // Set isIncreasing to false and exit the loop
                    break; 
                }
            }
    
            if (isIncreasing) { // If the column is increasing, increase the count
                count++;        
            }
        }
        
        else if (grid.length == 1) { // If there is only one row, count it as increasing
            count++;
        }
        
        else { // If there are no rows, exit the loop
            break;
        }
    }
    return count; 
}
Main.main(null);

columns increasing = 2

2D Array Trivia Quiz

Click the button to start the quiz!