- Learning Objectives
- Essential Knowledge
- Warm Up
- The Basics/Recap
- How to declare/initialize 2D arrays
- Accessing and updating the values of a 2D array
- Traversing 2D Arrays
- Lets try!
- Popcorn Hack
- Introducing: Column Major Order, as an alternative to Row Major Order
- 1. Introduction to Searching in 2D Arrays
- Explanation:
- Popcorn Hack 1: Custom 2D Search Challenge
- Explanation:
- Popcorn Hack - 2
- Mathematical Analysis of a 2D Array
- Popcorn Hack
- Alternate Resources
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
Declaring, Initializing
How to declare/initialize 2D arrays
public class Main {
public static void main(String[] args) {
// Initialize a 2D Array (example)
int[][] myArray = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
// 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 2 3
4 5 6
7 8 9
1) All in one
int[][] matrix = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
2) 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
}
}
public class Main {
public static void main(String[] args) {
String[][] matrix = {
[[Anusha, Vibha],[Avanthika, Matthew]]
};
// 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)
| [[Anusha, Vibha],[Avanthika, Matthew]]
illegal start of expression
| [[Anusha, Vibha],[Avanthika, Matthew]]
not a statement
| [[Anusha, Vibha],[Avanthika, Matthew]]
';' expected
| [[Anusha, Vibha],[Avanthika, Matthew]]
not a statement
| [[Anusha, Vibha],[Avanthika, Matthew]]
';' expected
| [[Anusha, Vibha],[Avanthika, Matthew]]
not a statement
| [[Anusha, Vibha],[Avanthika, Matthew]]
';' expected
| [[Anusha, Vibha],[Avanthika, Matthew]]
not a statement
| [[Anusha, Vibha],[Avanthika, Matthew]]
';' expected
| for(int i = 0; i < myArray.length; i++) {
illegal start of type
| for(int i = 0; i < myArray.length; i++) {
> expected
| for(int i = 0; i < myArray.length; i++) {
<identifier> expected
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]]
public class Main {
public static void main(String[] args) {
String[][] group1 = {
{"Anusha", "Vibha"},
{"Avanthika", "Matthew"},
};
displayArray(group1);
}
public static void displayArray(String[][] 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();
}
}
}
Main.main(null);
Anusha Vibha
Avanthika Matthew
Accesing, Updating
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
public class Main { public static void main(String[] args) { // Initial Group String[][] group1 = { {“Anusha”, “Vibha”}, {“Avanthika”, “Matthew”} };
// Update to New Group
group1[0][0] = "Alice";
group1[0][1] = "Bob";
group1[1][0] = "Charlie";
group1[1][1] = "David";
// Display updated array
displayArray(group1);
}
public static void displayArray(String[][] 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();
}
} }
Main.main(null);
Traversing
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}
};
int target = 9;
boolean found = false;
for (int i = 0; i < Numbers.length; i++) {
for (int j = 0; j < Numbers[i].length; j++) {
if (Numbers[i][j] == target) {
System.out.println(target + " is at row " + (i + 1) + " column " + (j + 1));
found = true;
break;
}
}
if (found) {
break; // Exit the outer loop once the number is found
}
}
}
}
Main.main(null);
9 is at row 3 column 3
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
Algorithms
1. Introduction to Searching in 2D Arrays
Key Concepts:
Linear Search: Sequentially checks every element.
Binary Search: Cuts the search space in half each time, but only works on sorted arrays.
{ { 3, 12, 9 },
{ 5, 2, 89 },
{ 90, 45, 22 } }
-
In the code, you use two nested loops to go through each row [i] and then each column [j] of the 2D array.
-
You start with arr[0][0] (which is 3), then move to arr[0][1] (which is 12), and so on.
-
Linear search checks every element, so it can be slow if you have a huge dataset. It takes O(n*m) time, where n is the number of rows, and m is the number of columns.
-
Why Use It? It works with any array, whether it’s sorted or not.
public class GFG {
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) {
System.out.println("Element found");
return new int[] { i, j };
}
}
}
return new int[] { -1, -1 };
}
public static void main(String[] args) {
System.out.println("First Line");
int arr[][] = {
{ 3, 12, 9 },
{ 5, 2, 89 },
{ 90, 45, 22 }
};
int target = 89;
int[] result = linearSearch(arr, target);
if (result[0] != -1) {
System.out.println("Element found at row " + result[0] + ", column " + result[1]);
} else {
System.out.println("Element not found");
}
}
}
GFG.main(null);
First Line
Element found
Element found at row 1, column 2
Explanation:
- The algorithm goes row by row and column by column until it finds the target value.
- If the value is found, it returns the index of that element.
Popcorn Hack 1: Custom 2D Search Challenge
Question:
You are given a sorted 5x5 2D array, where each row is sorted in ascending order. Write a function to perform binary search to find a target number in this 2D array. Your function should return both the index of the found element (row and column).
Requirements:
Implement a binary search function for the 2D array.
Function should display the row and column
The output should display whether the element was found.
public class Main {
static int[] binarySearch2D(int[][] arr, int target) {
int rows = arr.length;
int cols = arr[0].length;
int left = 0, right = rows * cols - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
int midValue = arr[mid / cols][mid % cols];
if (midValue == target) {
System.out.println("Element found");
return new int[] { mid / cols, mid % cols }; // Return row and column
}
if (midValue < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return new int[] { -1, -1 }; // Element not found
}
public static void main(String[] args) {
int[][] arr = {
{1, 3, 5, 7, 9},
{10, 12, 14, 16, 18},
{20, 22, 24, 26, 28},
{30, 32, 34, 36, 38},
{40, 42, 44, 46, 48}
};
int target = 44;
int[] result = binarySearch2D(arr, target);
if (result[0] != -1) {
System.out.println("Element found at row " + result[0] + ", column " + result[1]);
} else {
System.out.println("Element not found");
}
}
}
Main.main(null);
Element found
Element found at row 4, column 2
Binary Search in a 2D Array:
-
Sorted Array Requirement: Binary search only works on arrays that are sorted in ascending order. If the array is not sorted, the binary search algorithm will not function correctly.
-
Dividing the Search Space: The algorithm calculates the middle index of the current search range and compares the middle element to the target value:
{ 2, 5, 8, 12, 15, 23, 37, 45, 67 }
- If the middle element is equal to the target, the search is complete.
- If the middle element is less than the target, it discards the left half of the array (including the middle element) and continues searching in the right half.
- If the middle element is greater than the target, it discards the right half of the array and continues searching in the left half.
Applying Binary Search to a 2D Array:
When dealing with a 2D array, we can treat the array as a flattened 1D array.
Think of a 2D array as a long list, you can imagine the 2D array as one single row of values.
Finding the position of an element:
-
If you have an element located at (i, j), you can find its position in the long list using this formula:
- Position = (i * number of columns) + j
Converting back from a position to (i, j):
-
If you know the position in the long list and want to find out which row and column it corresponds to, use these formulas:
-
Row = Position / number of columns
-
Column = Position % number of columns
-
public class Main {
public static void main(String[] args) {
// Creating a 2D matrix using sorted array values
int[][] matrix = {
{2, 5, 8},
{12, 15, 23},
{37, 45, 67}
};
int target = 5; // Change this to test with other values like 12, 23, etc.
// Perform binary search and get the result
int[] result = binarySearch(matrix, target);
// Check the result and print appropriate message
if (result[0] != -1) {
System.out.println("Target " + target + " found at position: Row " + result[0] + ", Column " + result[1]);
} else {
System.out.println("Target " + target + " not found in the matrix.");
}
}
public static int[] binarySearch(int[][] matrix, int target) {
// Get the number of rows and columns
int rows = matrix.length;
int cols = matrix[0].length;
// Initialize left and right pointers for the search range
int left = 0;
int right = rows * cols - 1;
// Loop until the search range is valid
while (left <= right) {
// Calculate the middle index
int mid = left + (right - left) / 2;
// Convert the 1D index back to 2D row and column
int midValue = matrix[mid / cols][mid % cols];
// Check if the middle value is the target
if (midValue == target) {
return new int[] {mid / cols, mid % cols}; // Return the found position
}
// Adjust the search range based on the comparison
if (midValue < target) {
left = mid + 1; // Search in the right half
} else {
right = mid - 1; // Search in the left half
}
}
// Return -1 for both row and column if not found
return new int[] {-1, -1};
}
}
// To execute the main method, use:
Main.main(null);
Explanation:
Main Method
- Initialize a sorted 2D array (matrix) and define a target value to search for
- Call binarySearch(matrix, target) to find the target’s position.
- Output the result:
- If found, print the row and column.
- If not found, indicate the target is absent.
Binary Search Method
- Parameters: Takes a 2D array and a target value.
- Setup:
- Get the number of rows and columns.
- Initialize left (0) and right (last index).
- Search Loop:
- While left <= right:
- Calculate mid index.
- Convert mid to 2D indices.
- Check midValue against target:
- If equal, return indices
- If less, adjust left
- If greater, adjust right
- While left <= right:
Return {-1, -1} if the target isn’t found.
Popcorn Hack - 2
Create a program that performs binary search on a sorted 2D array to find a specified target number. Your function should return the position of the target if found, or indicate that the target is not present in the array.
public class Main {
static int[] binarySearch2D(int[][] arr, int target) {
int rows = arr.length;
int cols = arr[0].length;
int left = 0, right = rows * cols - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
int midValue = arr[mid / cols][mid % cols]; // Convert 1D mid index to 2D
if (midValue == target) {
return new int[] { mid / cols, mid % cols }; // Return row and column if found
}
if (midValue < target) {
left = mid + 1; // Search the right half
} else {
right = mid - 1; // Search the left half
}
}
return new int[] { -1, -1 }; // Return -1, -1 if the element is not found
}
public static void main(String[] args) {
// Sample sorted 2D array
int[][] arr = {
{1, 3, 5, 7, 9},
{10, 12, 14, 16, 18},
{20, 22, 24, 26, 28},
{30, 32, 34, 36, 38},
{40, 42, 44, 46, 48}
};
int target = 34; // Target number to search
int[] result = binarySearch2D(arr, target);
// Display result
if (result[0] != -1) {
System.out.println("Target " + target + " found at row " + result[0] + ", column " + result[1]);
} else {
System.out.println("Target " + target + " not found in the array.");
}
}
}
Main.main(null);
Target 34 found at row 3, column 2
Mathematical Analysis of a 2D Array
There are 3 types of standard algorithms that can be applied upon 2D arrays that are commonly tested by Collegeboard:
-
Mathematical Analysis: Algorithms that involve performing mathematical operations or calculations on 2D arrays, such as finding sums, averages, or other statistical measures. Examples include calculating the sum of all elements in a matrix or finding the determinant of a matrix.
-
Analyzing Element Properties: Algorithms that focus on examining and manipulating the properties of individual elements within a 2D array. This might involve checking for specific conditions, such as how many elements are prime, identifying the number of even/odd numbers, or surveying for any other properties.
-
Reordering Elements: Algorithms that involve changing the order of elements within a 2D array based on certain criteria. This could include sorting rows or columns, rotating the matrix, or rearranging elements to achieve a desired configuration. Examples include sorting the rows of a matrix in ascending order or rotating the matrix 90 degrees clockwise.
Mathematical Analysis
/// Define the class named MatrixSum
public class MatrixSum {
// Entry point of the program
public static void main(String[] args) {
// Initialize a 2D array (matrix) with predefined values
// The matrix here is a 3x3 array with integers from 1 to 9
int[][] matrix = {
{1, 2, 3}, // First row of the matrix
{4, 5, 6}, // Second row of the matrix
{7, 8, 9} // Third row of the matrix
};
// Call the calculateSum method with the matrix as an argument
// This method will return the sum of all elements in the matrix
int sum = calculateSum(matrix);
// Print the sum of all elements in the matrix to the console
// The output will be: "Sum of all elements: 45"
System.out.println("Sum of all elements: " + sum);
// Call the test method to execute the tests
testMatrixSum();
}
// Method to calculate the sum of all elements in a 2D matrix
// This method takes a 2D integer array (matrix) as input and returns an integer (the sum)
public static int calculateSum(int[][] matrix) {
// Initialize a variable to hold the sum of the matrix elements
int sum = 0;
// Iterate over each row in the matrix
// 'row' represents each 1D array (row) in the 2D array (matrix)
for (int[] row : matrix) {
// Iterate over each element in the current row
// 'element' represents each integer value in the row
for (int element : row) {
// Add the current element to the sum
sum += element;
}
}
// Return the final sum after all elements have been added
return sum;
}
// Test method to execute the calculations and print results
public static void testMatrixSum() {
// Test 1: Matrix with all positive integers
int[][] matrix1 = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
System.out.println("Sum of all elements in matrix 1: " + calculateSum(matrix1));
}
}
MatrixSum.testMatrixSum();
Analysis of Properties of a 2D array
public class PrimeNumberCounter {
/**
* Checks if a number is prime.
*
* @param num The number to check.
* @return true if the number is prime, false otherwise.
*/
public static boolean isPrime(int num) {
// Numbers less than or equal to 1 are not prime numbers
if (num <= 1) return false;
// 2 and 3 are prime numbers
if (num <= 3) return true;
// Eliminate even numbers greater than 2 and multiples of 3
if (num % 2 == 0 || num % 3 == 0) return false;
// Check for factors from 5 up to the square root of num
// Increment by 6 to check numbers of the form 6k ± 1
for (int i = 5; i * i <= num; i += 6) {
// Check divisibility by i and i + 2
if (num % i == 0 || num % (i + 2) == 0) return false;
}
// If no factors were found, num is prime
return true;
}
/**
* Counts the number of prime numbers in a 2D array.
*
* @param array The 2D array of integers to check.
* @return The count of prime numbers in the array.
*/
public static int countPrimes(int[][] array) {
int primeCount = 0; // Initialize count of prime numbers
// Iterate over each row in the 2D array
for (int[] row : array) {
// Iterate over each element in the row
for (int num : row) {
// Check if the current number is prime
if (isPrime(num)) {
primeCount++; // Increment count if prime
}
}
}
// Return the total count of prime numbers
return primeCount;
}
}
// Test the PrimeNumberCounter class
public class TestPrimeNumberCounter {
public static void main(String[] args) {
// Define a 2D array of integers for testing
int[][] testArray = {
{2, 4, 7, 8},
{11, 13, 17, 19},
{23, 24, 25, 29},
{31, 32, 37, 41}
};
// Count the number of prime numbers in the test array
int primeCount = PrimeNumberCounter.countPrimes(testArray);
// Print the result
System.out.println("Number of prime numbers: " + primeCount);
}
}
TestPrimeNumberCounter.main(null);
Reordering Elements
public class MatrixRotation {
public static void main(String[] args) {
// Initialize a 3x3 matrix
int[][] matrix = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
// Rotate the matrix 90 degrees clockwise
int[][] rotated = rotateMatrix90Degrees(matrix);
// Print the rotated matrix
printMatrix(rotated);
}
/**
* Rotates the given square matrix 90 degrees clockwise.
*
* @param matrix The matrix to be rotated
* @return The rotated matrix
*/
public static int[][] rotateMatrix90Degrees(int[][] matrix) {
int n = matrix.length; // Get the size of the matrix
int[][] rotated = new int[n][n]; // Initialize a new matrix for the rotated result
// Perform the rotation
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
// Map the element from the original matrix to the rotated matrix
rotated[j][n - 1 - i] = matrix[i][j];
}
}
return rotated; // Return the rotated matrix
}
/**
* Prints the given matrix to the console.
*
* @param matrix The matrix to be printed
*/
public static void printMatrix(int[][] matrix) {
// Loop through each row of the matrix
for (int[] row : matrix) {
// Loop through each element in the row
for (int element : row) {
// Print the element followed by a space
System.out.print(element + " ");
}
// Print a newline after each row
System.out.println();
}
}
}
MatrixRotation.main(null);
Popcorn Hack
Write a program in Java that allows you to find the number of elements in an array that are less than a certain input k.
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// Sample array
int[] arr = {1, 5, 3, 8, 12, 7, 4, 10, 14, 6};
// Get user input for k
System.out.print("Enter a number k: ");
int k = scanner.nextInt();
int count = countLessThanK(arr, k);
// Display the result
System.out.println("Number of elements less than " + k + ": " + count);
scanner.close();
}
// Function to count elements less than k
static int countLessThanK(int[] arr, int k) {
int count = 0;
for (int num : arr) {
if (num < k) {
count++;
}
}
return count;
}
}
Main.main(null);
Enter a number k: Number of elements less than 5: 3
Alternate Resources
Past CSA FRQs on Algorithms Applied to 2D Arrays
-
2014 FRQ - Problem 3: This problem involves working with a 2D array containing names and the number of absences of students. The 2D array has to be traversed and searched for all elements that satisfy a certain property.
-
2015 FRQ - Problem 1: This problem requires basic summation of entries in the 2D array and proceeds to require a more mathematically advanced algorithm in part (c).
-
2017 FRQ - Problem 4: This FRQ begins with a traversal of a 2D array to find the position of a certain integer and then proceeds to a problem of finding the number of possible subarrays within that grid.
Homework Hack
CB 2021 FRQ Question 4a
public class ArrayResizer
{
/** Returns true if and only if every value in row r of array2D is non-zero.
* Precondition: r is a valid row index in array2D.
* Postcondition: array2D is unchanged.
*/
public static boolean isNonZeroRow(int[][] array2D, int r)
{ /* to be implemented in part (a) */ }
/** Returns the number of rows in array2D that contain all non-zero values.
* Postcondition: array2D is unchanged.
*/
public static int numNonZeroRows(int[][] array2D)
{ /* implementation not shown */ }
/** Returns a new, possibly smaller, two-dimensional array that contains only rows
* from array2D with no zeros, as described in part (b).
* Precondition: array2D contains at least one column and at least one row with no zeros.
* Postcondition: array2D is unchanged.
*/
public static int[][] resize(int[][] array2D)
{ /* to be implemented in part (b) */ }
}
| { /* to be implemented in part (a) */ }
missing return statement
| { /* implementation not shown */ }
missing return statement
| { /* to be implemented in part (b) */ }
missing return statement
public static boolean isNonZeroRow(int[][] array2D, int r) {
for (int i = 0; i < array2D[r].length; i++) {
if (array2D[r][i] == 0) {
return false;
}
}
return true;
}
/*extra check to ensure everything is right by printing the test arrays */
int[][] arr = {{2, 1, 0},
{1, 3, 2},
{0, 0, 0},
{4, 5, 6}};
System.out.println(ArrayResizer.isNonZeroRow(arr, 0));
System.out.println(ArrayResizer.isNonZeroRow(arr, 1));
System.out.println(ArrayResizer.isNonZeroRow(arr, 2));
System.out.println(ArrayResizer.isNonZeroRow(arr, 3));
false
true
false
true