 |
Intro | Declaring, Initializing | Accessing, Updating | Traversing | Algorithms |
Unit 8 - 2D Arrays Algorithms & Hacks
2D Arrays Lesson
Algorithms 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);
19 6 6
2 19 6
5 1 14
The number 9 was not found in the 2D Array
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.
public class Main {
public static void main(String[] args) {
int[][] numbers = {
{10, 3, 5},
{8, 2, 6},
{1, 9, 4}
};
Scanner scanner = new Scanner(System.in);
System.out.print("Enter a value for k: ");
int k = scanner.nextInt();
int count = 0;
for (int i = 0; i < numbers.length; i++) {
for (int j = 0; j < numbers[i].length; j++) {
if (numbers[i][j] < k) {
count++;
}
}
}
System.out.println("Number of elements less than " + k + ": " + 0 );
}
}
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 ArrayChecker {
public static boolean isNonZeroRow(int[][] array2D, int r) {
if (r < 0 || r >= array2D.length) {
throw new IllegalArgumentException("Row index out of bounds");
}
for (int element : array2D[r]) {
if (element == 0) {
return false;
}
}
return true;
}
public static void main(String[] args) {
int[][] arr = {
{2, 1, 0},
{1, 3, 2},
{0, 0, 0},
{4, 5, 6}
};
System.out.println(isNonZeroRow(arr, 1));
System.out.println(isNonZeroRow(arr, 0));
}
}