Unit 8 - 2D Arrays P1
2D Arrays Lesson
- Learning Objectives
- Essential Knowledge
- Warm Up
- The Basics/Recap
- How to declare/initialize 2D arrays
- Accessing and updating the values of a 2D array
- 3) Traversing 2D Arrays
- Lets try!
- Popcorn Hack
- Introducing: Column Major Order, as an alternative to Row 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.
Warm Up
Answer the following questions as a group or individually. Write down your answers in your hacks notebook.
- What are 2D arrays?
2D Arrays are arrays with an extra dimension. They are data structures in Java.
- How are 2D arrays organized?
2D arrays are organized into rows and columns in a matrix format. There are two indices, one for rows and one for columns.
- What are some real-world examples of 2D arrays?
Some real-world examples of 2D arrays can be spreadsheets or maybe image processing.
The Basics/Recap
2D arrays, and higher dimension arrays overall, can be thought of as just an array that’s made up of other arrays or an array of arrays. One way of looking at 2D arrays is by thinking of them as a chess board. They have rows and columns, and every element is identified via row or column number or index.
Below is an illustration of a 2D array:
Warmup (Review)
- For the following three code cells categorize data + organization
- Data Bank: Homogenous Data, Heterogeneous Data, Type of Data, Heterogeneous Dimensions, Non-Square
- Note: Datatypes can be reused
How to declare/initialize 2D arrays
1) Initializing and populating the array in one go:
public class Main {
public static void main(String[] args) {
int[][] intArray = { // 2D array of integers
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
// Loop through the array and print its elements
for (int i = 0; i < intArray.length; i++) { // Iterate over rows
for (int j = 0; j < intArray[i].length; j++) { // Iterate over columns
System.out.print(intArray[i][j] + " "); // Print each element
}
System.out.println(); // Move to the next line after each row
}
}
}
2) Creating an empty 2D array and assigning values individually (by indexes)
public class Main {
public static void main(String[] args) {
String[][] stringArray = new String[2][3]; // 2D array with 2 rows and 3 columns
// Assign values to the array manually
stringArray[0][0] = "Apple";
stringArray[0][1] = "Banana";
stringArray[0][2] = "Cherry";
stringArray[1][0] = "Date";
stringArray[1][1] = "Elderberry";
stringArray[1][2] = "Fig";
// Loop through and print the array's elements
for (int i = 0; i < stringArray.length; i++) { // Iterate over rows
for (int j = 0; j < stringArray[i].length; j++) { // Iterate over columns
System.out.print(stringArray[i][j] + " "); // Print each element
}
System.out.println(); // New line after each row
}
}
}
3) Using a nested loop to populate the array dynamically:
public class Main {
public static void main(String[] args) {
int rows = 4;
int columns = 2;
double[][] doubleArray = new double[rows][columns]; // 2D array of doubles (4 rows, 2 columns)
// Nested loop to populate the array with computed values
for (int i = 0; i < rows; i++) {
for (int j = 0; j < columns; j++) {
doubleArray[i][j] = i * 0.5 + j * 0.1; // Example formula for dynamic values
}
}
// Loop through and print the array
for (int i = 0; i < doubleArray.length; i++) {
for (int j = 0; j < doubleArray[i].length; j++) {
System.out.print(doubleArray[i][j] + " ");
}
System.out.println(); // New line after each row
}
}
}
Popcorn Hack: Create a Mixed Data (Object) 2D array using nested for-loops
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;
public class Main {
public static void main(String[] args) {
// Initialize a 2D array
int[][] array = {
{10, 20, 30},
{40, 50, 60},
{70, 80, 90}
};
// Accessing a value
int value = array[1][2]; // Accessing the element at row 1, column 2
System.out.println("Value at [1][2] before update: " + value);
// Updating a value
array[1][2] = 100; // Updating the value at row 1, column 2
System.out.println("Updated value at [1][2]: " + array[1][2]);
// Print the entire updated array
System.out.println("Updated 2D Array:");
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array[i].length; j++) {
System.out.print(array[i][j] + " ");
}
System.out.println(); // New line after each row
}
}
}
Popcorn Hack: Print all the values on this 2D Array and update the last value to be 12.
public class Main {
public static void main(String[] args) {
int[][] myArray = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
int value = 12;
myArray[2][2] = value;
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)
Failed to start the Kernel.
Error: could not open `KERNEL_INSTALL_DIRECTORY@/ijava-1.3.0.jar'.
View Jupyter <a href='command:jupyter.viewOutput'>log</a> for further details.
3) Traversing 2D Arrays
- When traversing through, or looping through 1D arrays, we only need to use one loop to access every element in the array.
- This is different in 2D arrays, where we need to use a loop inside of a loop, otherwise known as a for loop
- Java for loop structure review: ```java for(first execution; condition; executed after every loop) { //Action }
ex. for(i = 0; i < 5; i++) { System.out.println(i); }
Prints out 0 1 2 3 4
(Remember base 0)
- How can we use these to traverse through 1D arrays?
Lets say we have an array, Array1...
```java
// Set variable i to 0, while i is less than the length of Array1, print the value of Array1[i], add 1 to i
int[] Array1 = {1, 2, 3};
for(int i = 0; i < Array1.length; i++){
System.out.println(myArray[i]);
}
- What about 2D arrays?
// Create an array of integers with 2 rows, 3 columns int[][] Array1 = { {1,2,3}, {4,5,6} }; // Set variable i to 0, while i is less than the length of Array1, proceed to the next for loop, add 1 to i for(int i = 0; i < Array1.length; i++){ // Set variable i1 to 0, while i is less than the length of the array within Array1 at Array1[i], print the value of Array1[i][i1], add 1 to i1 for(int i1 = 0; i1 < Array1[i].length; i1++){ System.out.println(Array1[i][i1]); } }
Put in simpler terms?
For every row, loop through the row x number of times, x being the length of the array, print each individual value. So this code, without the loops, would be:
System.out.println(Array1[0][0])
System.out.println(Array1[0][1])
System.out.println(Array1[0][2])
// Keeping in mind base 0 system, and that Array1 has 3 columns for each row
// Move on to the next row
System.out.println(Array1[1][0])
System.out.println(Array1[1][1])
System.out.println(Array1[1][2])
// Again, keeping in mind that Array1 has 2 rows, and base 0 system, so "1st row" is actually 2nd put in plain english
Lets try!
public class Main {
public static void main(String[] args) {
int[][] Array1 = {
{1,2,3},
{4,5,6}
};
// Set variable i to 0, while i is less than the length of Array1, proceed to the next for loop, add 1 to i
for(int i = 0; i < Array1.length; i++){
System.out.println("Row " + (i+1) + ", or " + i);
// Set variable i1 to 0, while i is less than the length of the array within Array1 at Array1[i], print the value of Array1[i][i1], add 1 to i1
for(int i1 = 0; i1 < Array1[i].length; i1++){
System.out.println(Array1[i][i1]);
}
}
}
}
Main.main(null)
Row 1, or 0
1
2
3
Row 2, or 1
4
5
6
Popcorn Hack
Let’s say you have an array Numbers[][] defined as:
int Numbers[][] = {
{1,2,3},
{4,5,6},
{7,8,9},
};
Loop through it until you reached a certain number of your choice, then print the value and position
public class Main {
public static void main(String[] args) {
int[][] Numbers = {
{1,2,3},
{4,5,6},
{7,8,9}
};
// Write code here
}
}
Main.main(null)
Example output: 9 is at row 3 column 3
What if you want to go column-first?
Introducing: Column Major Order, as an alternative to Row Major Order
Put simply, all you have to do is reverse the order of the loops, and keep the insides intact, and use the length of a row for the number of times to loop instead of the length of a column.
Why/how does this work?
Now instead of looping once for every row by taking the number of elements in the array, which defines how many rows there, we instead loop once for every element in each element in the array, (ex. an array with an element {1, 2, 3} would loop 3 times) which defines how many columns there are. Then, we print out the value from the chosen column, represented by i1, and then increment the row value, i, to finish out the rest of the column. Then, i1, the column value, is incremented, and the value repeats. We reverse the order of the loops so that the column is prioritized, and make the changes accordingly.
public class Main {
public static void main(String[] args) {
int[][] Array1 = {
{1,2,3},
{4,5,6}
};
// Set variable i to 0, while i is less than the length of Array1, proceed to the next for loop, add 1 to i
for(int i1 = 0; i1 < Array1[0].length; i1++){
System.out.println("Column " + (i1+1));
for(int i = 0; i < Array1.length; i++){
System.out.println(Array1[i][i1]);
}
}
}
}
Main.main(null)
Column 1
1
4
Column 2
2
5
Column 3
3
6
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