- Learning Objectives
- Essential Knowledge
- How to declare/initialize 2D arrays
- Accessing and updating the values of a 2D array
- 3) Traversing 2D Arrays
- Row-Major Order vs Column-Major Order
- Popcorn Hack - EXTRA!
Learning Objectives
The objective of this lesson is to…
- Learn about 2D arrays, their use cases, and how to create them.
Essential Knowledge
College Board wants you to know…
- How to declare/initialize 2D arrays.
- How to determine their size.
- How to access and update the values of a 2D array.
- How to traverse/access elements of a 2D array using nested iteration statements.
- How nested iteration statements can be used to traverse 2D arrays in “row-major order” vs “column-major order.”
- How to create algorithms that require the use of 2D array traversals.
How to declare/initialize 2D arrays
// Boiler Plate Code public class Main { public static void main(String[] args) {
*/ (Intialize Array Here) */
// Display Array Code below
for(int i = 0; i < myArray.length; i++) {
for (int j = 0; j < myArray[i].length; j++) {
System.out.print(myArray[i][j] + " ");
}
System.out.println();
}
} }
Main.main(null) 1) All in one
int[][] matrix = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
1) Empty array and manual input with indexes
// Declare a 3x3 empty 2D array
int[][] matrix = new int[3][3];
// Assign values to the 2D array using indexes
matrix[0][0] = 1;
matrix[0][1] = 2;
matrix[0][2] = 3;
matrix[1][0] = 4;
matrix[1][1] = 5;
matrix[1][2] = 6;
matrix[2][0] = 7;
matrix[2][1] = 8;
matrix[2][2] = 9;
3) Nested For-Loop
int value = 1; // Start value
for (int i = 0; i < matrix.length; i++) { // Outer loop for rows
for (int j = 0; j < matrix[i].length; j++) { // Inner loop for columns
matrix[i][j] = value++; // Assign value and increment
}
}
Popcorn Hack 1 (Part 1):
- Intialize a 2D array of the people in your group grouped based on pairs with 3 different methods
- ex Array: [[Anusha, Vibha],[Avanthika, Matthew]]
Accessing and updating the values of a 2D array
In Java, accessing and updating values in a 2D array is done using the row and column indices. The general format is:
- **Accessing a value**: array[row][column]
- **Updating a value**: array[row][column] = newValue;
Popcorn Hack 1 (Part 2)
- Update the values of the array, you made in part 1 to the group members in another group
3) Traversing 2D Arrays
- When we traverse a regular array we use a singular for loop to iterate through each element in the array. However, when we have 2D array we need to use nested for loops to iterate through each element in the array. Below is the difference between the two:
// Regular array traversal
for(int i = 0; i < myArray.length; i++){
System.out.println(myArray[i]);
}
// 2D array traversal
for(int i = 0; i < myArray.length; i++){
for(int j = 0; j < myArray[i].length; j++){
System.out.println(myArray[i][j]);
}
}
public class Main {
public static void main(String[] args){
int[] myArray = {1, 2, 3, 4, 5, 6, 7, 8, 9}; // 1d array of integers
int[][] my2dArray = { // 2d array of integers
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
System.out.println("1D Array\n"); // Print a new line
for (int i = 0; i < myArray.length; i++) { // Loop through the 1d array
System.out.print(myArray[i] + " "); // Print out the element
}
System.out.println("\n\n2D Array\n"); // Print a new line
for (int i = 0; i < my2dArray.length; i++) { // First traversal condition
for (int j = 0; j < my2dArray[i].length; j++) { // Second traversal condition
System.out.print(my2dArray[i][j] + " "); // Print out the element
}
System.out.println(); // Print a new line
}
}
}
Main.main(null)
1D Array
1 2 3 4 5 6 7 8 9
2D Array
1 2 3
4 5 6
7 8 9
Popcorn Hack: Traverse the following array and only print the values divisible by 7
public class Main {
public static void main(String[] args) {
int[][] myArray = {
{1, 2, 11},
{14, 5, 21},
{25, 28, 70}
};
for(int i = 0; i < myArray.length; i++) {
for (int j = 0; j < myArray[i].length; j++) {
if (myArray[i][j] % 7 == 0) {
System.out.print(myArray[i][j] + " ");
} else {
System.out.print(" ");
}
}
System.out.println();
}
}
}
Main.main(null)
14 21
28 70
Row-Major Order vs Column-Major Order
Row-Major-Order:
- The outer loop traverses the rows and the inner loop traverses the columns or the elements within the rows. Here is an example bellow of row-major order traversals:
public class rowMajorOrder {
public static void main(String[] args){
int[][] my2dArray = { // 2d array of integers
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
System.out.println("Row Major Order\n"); // Print a new line
for (int i = 0; i < my2dArray.length; i++) { // First traversal traverses by rows condition
for (int j = 0; j < my2dArray[i].length; j++) { // Iterates through the columns
if (my2dArray[i][j] % 2 == 0) { // If the element is even
} else{
my2dArray[i][j] = 0; // Otherwise set the element to 0
}
System.out.print(my2dArray[i][j] + " "); // Print out the element
}
System.out.println(); // Print a new line
}
}
}
rowMajorOrder.main(null)
Row Major Order
0 2 0
4 0 6
0 8 0
// Variation that only applies to forward row-wise major traversal
public class rowMajorTraversalAlt{
public static void rowMajorOrderAlt(int[][] array){
for (int[] row: array){
for (int element: row){
System.out.print(element + " ");
}
System.out.println();
}
}
}
rowMajorTraversalAlt.rowMajorOrderAlt(new int[][]{
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
});
1 2 3
4 5 6
7 8 9
Column-Major-Order:
- The outer loop will traverse through the columns and the inner loop will traverses through each element in the columns or the rows. Here is an example bellow of column-major order traversals:
public class columnWiseTraversal{
public static void main(String[] args){
int[][] my2dArray = { // 2d array of integers
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
System.out.println("Column Wise Traversal\n"); // Print a new line
for (int j = 0; j < my2dArray[0].length; j++) { // First traversal traverses by columns condition
for (int i = 0; i < my2dArray.length; i++) { // Iterates through the rows
if (my2dArray[j][i] % 2 == 0) { // If the element is even
} else{
my2dArray[j][i] = 0; // Otherwise set the element to 0
}
System.out.print(my2dArray[j][i] + " "); // Print out the element
}
System.out.println(); // Print a new line
}
}
}
columnWiseTraversal.main(null)
// Both row and column wise traversals in our examples do the same thing, but in different orders. However for certain functions one may be easier to use than the other.
Column Wise Traversal
0 2 0
4 0 6
0 8 0
Algoirthms 2D Array Java
Linear search is a simple and sequential searching algorithm. It is used to find whether a particular element is present in the array or not by traversing every element in the array. While searching in the 2D array is exactly the same but here all the cells need to be traversed In this way, any element is searched in a 2D array.
Below is the implementation for linear search in 2D arrays
// Linear Search in 2D arrays
import java.util.Arrays;
public class GFG {
public static void main(String[] args)
{
int arr[][] = { { 3, 12, 9 },
{ 5, 2, 89 },
{ 90, 45, 22 } };
int target = 89;
int ans[] = linearSearch(arr, target);
System.out.println("Element found at index: "
+ Arrays.toString(ans));
}
static int[] linearSearch(int[][] arr, int target)
{
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr[i].length; j++) {
if (arr[i][j] == target) {
return new int[] { i, j };
}
}
}
return new int[] { -1, -1 };
}
}
GFG.main(null);
Element found at index: [1, 2]
Summary: Linear Search involves iterating through all elements in the matrix. Binary Search is applicable when the matrix is sorted. Binary Search treats the 2D matrix as a 1D array by converting the indices. These searching algorithms are fundamental and widely used. Practice applying them to different scenarios to solidify your understanding. Additionally, consider exploring more advanced searching techniques for 2D arrays as you become more proficient.
public class Main {
public static int[] binarySearch(int[][] matrix, int target) {
int rows = matrix.length;
int cols = matrix[0].length;
int left = 0;
int right = rows * cols - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
int midValue = matrix[mid / cols][mid % cols];
if (midValue == target) {
return new int[] {mid / cols, mid % cols};
}
if (midValue < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return new int[] {-1, -1}; // Target not found
}
}
Binary Search in a 2D Array:
Binary search is an efficient method of searching in an array. Binary search works on a sorted array. At each iteration the search space is divided in half, this is the reason why binary search is more efficient than linear search
// Binary Search on sorted 2D array
import java.util.Arrays;
class GFG {
static int[] findAns(int[][] arr, int target)
{
int row = 0;
int col = arr[row].length - 1;
while (row < arr.length && col >= 0) {
if (arr[row][col] == target) {
return new int[] { row, col };
}
// Target lies in further row
if (arr[row][col] < target) {
row++;
}
// Target lies in previous column
else {
col--;
}
}
return new int[] { -1, -1 };
}
// Driver Code
public static void main(String[] args)
{
// Binary search in sorted matrix
int arr[][] = { { 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 9, 10, 11, 12 } };
int[] ans = findAns(arr, 12);
System.out.println("Element found at index: "
+ Arrays.toString(ans));
}
}
GFG.main(null);
Element found at index: [2, 3]
Popcorn Hack - EXTRA!
Create a program that implements binary search on 2D Arrays.
import java.util.Random;
import java.util.Arrays;
public class BinarySearch {
public static void main(String[] args) {
int[][] array = new int [3][3];
Random rand = new Random();
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array[i].length; j++) {
array[i][j] = rand.nextInt(20+1);
System.out.print(array[i][j] + " ");
}
System.out.println();
}
System.out.println();
int target = rand.nextInt(20+1);
int[] answer = binarySearchAlgorithm(array, target);
if (Arrays.equals(answer, new int[] {-1, -1})) {
System.out.println("The number " + target + " was not found in the 2D Array");
} else {
System.out.println("The number " + target + " was found at index " + Arrays.toString(answer));
}
}
public static int[] binarySearchAlgorithm(int[][] arr, int target) {
int rows = arr.length;
int columns = arr[0].length;
int left = 0;
int right = rows * columns - 1;
if(rows == 0) {
return new int[] {-1, -1};
}
while(left <= right) {
int mid = left + (right - left) / 2;
int midvalue = arr[mid / columns][mid % columns];
if (midvalue == target) {
return new int[] {mid / columns, mid % columns};
} else if (midvalue < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return new int[] {-1, -1};
}
}
BinarySearch.main(null);
10 13 2
3 12 18
17 4 19
The number 17 was found at index [2, 0]
Enhanced For-Each Loop for 2D Arrays
Since 2D arrays are really arrays of arrays you can also use a nested enhanced for-each loop to loop through all elements in an array. We loop through each of the inner arrays and loop through all the values in each inner array. Notice the type of the outer loop array variable – it is an array that will hold each row, String[] in the example below for a 2D String array. The type of the variables in the for-each loops must match the type of the array. For-each loops are much simpler since you don’t have to use the indices and the []’s, but you can only use them if you are not going to change the values in an array of primitive types since the variable val below will not change the original array.
String[][] array;
// Nested For-each loops that traverse a 2D String array
for (String[] innerArray : array)
{
for (String val : innerArray)
{
System.out.println(val);
}
}
public class Average
{
public static double getAvg(int[][] a)
{
double total = 0;
for (int[] innerArray : a)
{
for (int val : innerArray)
{
total = total + val;
}
}
return total / (a.length * a[0].length);
}
public static void main(String[] args)
{
int[][] theArray = { {80, 90, 70}, {20, 80, 75}};
System.out.println(getAvg(theArray));
}
}
Average.main(null);
69.16666666666667
4) How to create an algorithm that involves traversing a 2D Array
During the APCSA AP exam, we will be required to write an algorithm for a 2D array that solves a problem discussed in the prompt. Collegeboard will give you a situation, and you will have to write an algorithm based on said situation.
Here’s an example of an algorithm that was needed for the real Collegeboard APCSA exam in 2022:
For this problem, the question asked for the student to write the countIncreasingCols method, which returns the number of columns in grid that are in increasing order. grid is a 2D array with randomly populated numbers.
public int countIncreaseCols() {
int count = 0;
for (int j = 0; j < grid[0].length; j++) { // Iterates through columns
boolean isIncreasing = true;
if (grid[0].length > 1) { // Checks if there is more than one column to prevent out of bounds error
for (int i = 1; i < grid.length; i++) { // Iterates through rows
if (grid[i][j] <= grid[i - 1][j]) { // Checks if the current element is less than or equal to the previous element
isIncreasing = false; // If so set isIncreasing to false and break out of loop
break;
}
}
if (isIncreasing) { // If the column is increasing increment count as if
count++; // the value is not less than or equal to the previous
// element then it must be increasing
}
}
else if (grid[0].length == 1) { // To match the criteria of a single column being increasing
count++;
}
else { // If there are no columns then break out of loop
break;
}
}
return count;
}
Hacks:
1)
Initialize a 5 x 5 2D array that is populated by random values.
// Add the code here:
public class random2DA {
public static void main(String[] args) {
int[][] array = new int[5][5];
Random rand = new Random();
for(int i = 0; i < array.length; i++) {
for (int j = 0; j < array[i].length; j++) {
array[i][j] = rand.nextInt(101);
System.out.print(array[i][j] + " ");
}
System.out.println();
}
}
}
random2DA.main(null);
60 96 57 24 41
66 78 43 34 19
93 3 44 15 14
37 83 22 67 84
79 100 96 1 90
2)
- a) Print the values 47, 51, and 20 by accessing them in the the given two-dimensional array.
- b) Find the values from part a) using row major and column major order and print the values in each respective order.
public class Problem2
{
public static void main(String[] args)
{
int[][] arr = { {47,3,12},{51,74,20} };
System.out.println("Row Major order:");
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr[i].length; j++) {
if (arr[i][j] == 47 || arr[i][j] == 51 || arr[i][j] == 20) {
System.out.print(arr[i][j] + " ");
}
}
}
System.out.println("\nColumn Major order:");
for (int j = 0; j < arr[0].length; j++) {
for (int i = 0; i < arr.length; i++) {
if (arr[i][j] == 47 || arr[i][j] == 51 || arr[i][j] == 20) {
System.out.print(arr[i][j] + " ");
}
}
}
}
}
Problem2.main(null);
Row Major order:
47 51 20
Column Major order:
47 51 20
3)
The following 2d array myArray is populated with integers 1-9. Write an algorithm thath sorts the 2D array by column and returnst the values of the array in increaing order.
The expected output is:
1 4 7
2 5 8
3 6 9
public class Problem3 {
public static void main(String[] args) {
int[][] myArray = { // 2d array of integers
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
int numrows = myArray.length;
int numcols = myArray[0].length;
for (int j = 0; j < numcols; j++) {
for (int i = 0; i < numrows; i++) {
System.out.print(myArray[i][j] + " ");
}
System.out.println();
}
}
}
Problem3.main(null);
1 4 7
2 5 8
3 6 9
4)
Replace the “ADD CODE HERE” below with the code to declare and create a 3 by 3 two-dimensional int array named table. The finished code will print the values 0 to 8.
public class Test1
{
public static void main(String[] args)
{
// ADD CODE HERE //
int[][] table = new int[3][3];
// Should print the values in table
int count = 0;
for (int row = 0; row < table.length; row++)
{
for (int col = 0; col < table.length; col++)
{
table[row][col] = count;
count++;
System.out.print(table[row][col] + " ");
}
System.out.println();
}
}
}
Test1.main(null);
0 1 2
3 4 5
6 7 8
5)
Replace the “ADD CODE HERE” below with the code to declare and initialize a two-dimensional String array called students with the names “Brice, Marvin, Anna” in the first row and “Kamal, Maria, Elissa” in the second. The finished code will print all the names in the array starting with all in the first row followed by all in the second row.
public class Test1
{
public static void main(String[] args)
{
// ADD CODE HERE //
String[][] students = {
{"Brice", "Marvin", "Anna"},
{"Kamal", "Maria", "Elissa"}
};
// Should print the values in students in order
for (int row = 0; row < students.length; row++)
{
for (int col = 0; col < students[0].length; col++)
{
System.out.print(students[row][col] + " ");
}
System.out.println();
}
}
}
Test1.main(null);
Brice Marvin Anna
Kamal Maria Elissa