10 min read•Last Updated on June 18, 2024
Avanish Gupta
Milo Chang
Avanish Gupta
Milo Chang
Note: In this topic, we will be using arrayB and the graphical representation of 2D arrays from the previous topic. As a reminder, here is arrayB:
int[][] arrayB = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}};
Recall that when traversing a 1D array, you use a loop, usually a for loop or enhanced for loop. This is similar to how we traverse 2D arrays, except in 2D arrays, we need 2 nested for loops, an outer loop traversing through one dimension, and an inner loop traversing through the other. Here is the general form:
for (firstDimension traversal conditions) { for (secondDimension traversal conditions) { System.out.print(item + " "); } } System.out.println();
There are two main directions we can traverse through. The first is row-major traversal, traversing through every element in one row before moving to the next. Conversely, there is column-major traversal, traversing through every element in one column before moving on to the next.
We will focus on traversing in a forward direction (from left-to-right and from top-to-bottom) in this section. In the next, we will go in reverse directions, but this will only require a change in the for loop conditional.
When doing row-wise traversal, the outer loop traverses through the different rows, and the inner loop traverses through the elements in each row. Here is how you write code for this:
public static void rowWiseForward(int[][] array) { for (int i = 0; i < array.length; i++) { for (int j = 0; j < array[0].length; j++) { System.out.print(array[i][j] + " "); } } }
public static void main(str[] args) { rowWiseForward(arrayB); }
1 2 3 4 5 6 7 8 9 10 11 12
We can only use nested enhanced for loops for forward row-wise traversals. Here is the code that creates the same output as above, only this time using enhanced for loops instead of regular for loops:
public static void rowWiseForwardEnhancedForLoops(int[][] array) { for (int[] row: array) { for (int number: row) { System.out.print(number + " "); } } }
Remember that the type of the rows in the 2D array are 1D arrays, and the rows contain elements of a certain type!
When doing column-wise traversal, the outer loop traverses through the different columns, and the inner loop traverses through the elements in each columns. Here is how you write code for this:
public static void columnWiseForward(int[][] array) { for (int i = 0; i < array[0].length; i++) { for (int j = 0; j < array.length; j++) { System.out.print(array[j][i] + " "); } } }
public static void main(str[] args) { columnWiseForward(arrayB); }
1 5 9 2 6 10 3 7 11 4 8 12
We can see that the two traversal algorithms using regular for loops are almost the same. The only significant difference is with the order of the for loop conditionals. However, the loop conditional for traversing through different rows is the same in both cases, and so is the conditional for traversing through different columns. Here are the conditionals for the two different traversal directions:
To traverse through different rows: i < array.length;
To traverse through different columns: i < array[0].length;
We will use this to help us go in reverse next!
Sometimes, we want to traverse across the rows from right to left, or traverse across the columns from bottom to top. This will require a change the for loop headers, as follows:
To traverse through different rows: int i = array.length() - 1; i >= 0; i--
This is initializing i to the last row, and then going up row-by-row to the first row in every loop iteration.
To traverse through different columns: int i = array[0].length - 1; i >= 0; i--
Likewise, this is initializing i to the rightmost column, and then going left column-by-column to the first column in every loop iteration.
To do row-wise traversal, put the row for loop header first, while to do column-wise traversal, put the column for loop header first.
Let's do a challenge. We want to traverse arrayB so that it prints the following:
For example 1, we are doing a row-wise traversal from top to bottom that starts forward, but then alternates the direction every row as shown in this image:
For example 2, we are doing a column-wise traversal from right to left that starts backwards then alternates in direction as is shown in this image:
What's the secret behind this? It's an if statement and modulo. Here is the code with the this part commented:
public static void exampleOne(int[][] array) { for (int i = 0; i < array.length; i++) { if (i % 2 == 0) { // we use an if statement with modulo base 2 to alternate for (int j = 0; j < array[0].length; j++) { System.out.print(array[i][j] + " "); } } else { for (int j = array[0].length - 1; j >= 0; j--) { System.out.print(array[i][j] + " "); } } } }
public static void exampleTwo(int[][] array) { for (int i = array[0].length - 1; i >= 0; i--) { if (i % 2 == 0) { // we use an if statement with modulo base 2 to alternate for (int j = 0; j < array[0].length - 1; j++) { System.out.print(array[j][i] + " "); } } else { for (int j = array.length - 1; j >= 0; j--) { System.out.print(array[j][i] + " "); } } } }
For 2D arrays, we use the slightly modified versions of the algorithms we have been doing with 1D arrays and ArrayLists. All of these algorithms apply the loop traversals we have just discussed! Here, we will have a snippet for each algorithm you are expected to know with each snippet annotated for you.
/** Prints the row and column indices if the element is in the array and -1 if not */ public static boolean searchForElement(int[][] array, int elementToSearch) { flag = false; //sets flag to see if element has been found for (int i = 0; i < array.length; i++) { for (int j = 0; j < array[0].length; j++) { //traverses through the array if (array[i][j] == elementToSearch) { System.out.println("Row " + i); System.out.println("Column " + j); //if element found, print coordinates return true; //element has been found } } } if (!flag) { //if element not found, return false return false; } }
/** Doubles each element of the array */ public static void doubleArray(int[][] array) { for (int i = 0; i < array.length; i++) { for (int j = 0; j < array[0].length; j++) { array[i][j] *= 2; // doubles each individual element } } }
Note that in the above snippet, we used regular for loops instead of enhanced for loops. Here, we cannot use enhanced for loops as follows:
/** Doubles each element of the array */ public static void doubleArray(int[][] array) { for (int[] row: array) { for (int number: row) { number *= 2; // doubles number } } }
This is because Java is pass-by-value. In the first example, we are actually accessing the array itself. However, in the enhanced for loop example, we are making a copy of that array and any changes are affecting the copy, not the actual array.
However, if the array items are objects and we are changing the value of one of the object's instance variables, we can use enhanced for loops as the copy contains references to the actual objects themselves. Here is an example of this:
/** Represents a student */ public class Student { private String name;
/** Sets the name of the Student */ public void setName(String name) { this.name = name; }
/** Other instance variables, methods, and constructors not shown / } // IN ANOTHER CLASS /* Resets names of all student s */ public static void doubleArray(Student[][] array, String defaultName) { for (Student[] row: array) { for (Student student: row) { student.setName(defaultName); // Sets each student's name to a default name } } }
/** Inserts all the values in the array into an ArrayList
*/
public static ArrayList
//Boxes the integer to an Integer object adding it to the ArrayList
intList.add(new Integer(number));
}
} return intList; }
Java has autoboxing, so you could also just do intList.add(number); and Java will automatically convert the integer into an Integer object.
/** Inserts all the values in the array into an array */ public static int[] putIntoArray(int[][] array) { int[] intArray = new int[array.length * array[0].length]; //initialize the array for (int i = 0; i < array.length; i++) { //to the number of items in rect array for (int j = 0; j < array[0].length; j++) {
//i*array[0].length + j is the nth item
intArray[i*array[0].length + j] = array[i][j];
}
} return intArray; }
/** Finds the maximum */ public static int maximum(int[][] array) { int maxValue = array[0][0]; for (int[] row: array) { for (int number: row) { if (number > maxValue) { //if new max value found, replace current maxValue maxValue = number; } } } return maxValue; }
/** Finds the minimum */ public static int minimum(int[][] array) { int minValue = array[0][0]; for (int[] row: array) { for (int number: row) { if (number < minValue) { //if new min value found, replace current minValue minValue = number; } } } return minValue; }
A common mistake is initializing the maxValue and minValue to 0.
/** Sums up all elements in the array */ public static int sum(int[][] array) { int sum = 0; for (int[] row: array) { for (int number: row) { sum += number; //adds every element to sum } } return sum; }
/** Finds the mean/average of the array */ public static int mean(int[][] array) { // find the sum of the array, can be replaced with sum algorithm above
int sum = sum(array); return (double) sum / (array.length * array[0].length); }
/** Finds the mode of an array Prerequisite: The array must have a mode */ public static int mode(int[][] array) { int[] newArray = putIntoArray(array) //places the numbers into a 1D array as above int mostCommon = 0; int mostCommonFrequency = 0; for (int i = 0; i < newArray.length - 1; i++) { //traverse through the new array int currentFrequency = 1; for (int j = i + 1; j < newArray.length; j++) { //traverse through rest of array
// if any element matches current element being checked, add 1 to frequency
if (newArray[j] == newArray[i]) {
currentFrequency++;
}
}
if (currentFrequency > mostCommonFrequency) {
mostCommon = newArray[i]; // replaces current mode if new most common element
mostCommonFrequency = currentFrequency;
}
} return mostCommon; // can also be modified to return the frequency }
/** Determines whether all values are even */ public static boolean isEven(int[][] array) { //Assume all values are positive first for (int[] row: array) { for (int number: row) { if (number % 2 == 1) { //If there is one value that is not positive, return false return false; } } } return true; //No odd numbers were found }
/** Returns all consecutive sequences of length n in the array */ public static void returnAllConsecutiveSequences(int[][] array, int length) { public int[] oneDArray = putIntoArray(array); for (int i = 0; i <= oneDArray.length - length; i++) { for (int j = 0; j < length; j++) { System.out.print(oneDArray[i+j] + " "); //2 loops, one to get the starting number } //the other to go through the sequences System.out.println(); } }
/** Checks to see if there are duplicate elements */ public static boolean duplicates(int[][] array) { int[] newArray = putIntoArray(array) //places the numbers into a 1D array as above for (int i = 0; i < newArray.length - 1; i++) { //traverse through the new array for (int j = i + 1; j < newArray.length; j++) { //traverse through rest of array
// if any element matches current element being checked, return true
if (newArray[j] == newArray[i]) {
return true;
}
}
} return false; // if this point reached, no duplicates found }
/** Returns how many even numbers there are */ public static int evenFrequency(int[][] array) { int numberEven = 0; for (int[] row: array) { for (int number: row) { if (number % 2 == 0) { numberEven++; // increments every time an even integer is found } } } return numberEven; }
2D arrays are data structures that store values in a grid-like format with rows and columns. They allow for the organization and manipulation of data in a two-dimensional manner.
Term 1 of 23
2D arrays are data structures that store values in a grid-like format with rows and columns. They allow for the organization and manipulation of data in a two-dimensional manner.
Term 1 of 23
2D arrays are data structures that store values in a grid-like format with rows and columns. They allow for the organization and manipulation of data in a two-dimensional manner.
Term 1 of 23
ArrayB refers to an individual element within an array or specifically denotes an element at index B within an array.
Array Indexing: Array indexing refers to accessing or retrieving specific elements from an array using their corresponding indices.
Element Assignment/Modification: This term refers to changing or updating the value of an element at a particular index within an array.
Array Length/Size: The length or size of an array represents the total number of elements it contains. It helps determine the range of valid indices for the array.
2D arrays are data structures that store values in a grid-like format with rows and columns. They allow for the organization and manipulation of data in a two-dimensional manner.
Methods: In programming, methods are blocks of code that perform specific tasks. They can be used to manipulate or retrieve data from 2D arrays.
Access: Access refers to the ability to retrieve or modify the values stored in an array. In the context of 2D arrays, it involves accessing specific elements using their row and column indices.
Arrays: Arrays are data structures that store multiple values of the same type. A 2D array is simply an extension of this concept, allowing for storage in a grid-like format instead of just linearly.
A for loop is a control flow statement that allows you to repeatedly execute a block of code for a specified number of times or until certain conditions are met.
While Loop: A while loop repeatedly executes a block of code as long as a given condition remains true.
Loop Variable: The loop variable is a variable that keeps track of the current iteration or count in a loop.
Nested Loop: A nested loop is a loop inside another loop. It allows you to perform more complex repetitive tasks by iterating over multiple sets of data simultaneously.
An enhanced for loop (also known as a foreach loop) is a simplified way to iterate over elements in an array or collection. It automatically handles indexing and provides an easy way to access each element without explicitly using indices.
Array: An array is a data structure that stores multiple values of the same type in contiguous memory locations. Elements in an array can be accessed using their index position.
Iterator: An iterator is an object that allows traversal through elements in a collection one by one. It provides methods like hasNext() and next() to check if there are more elements and retrieve them respectively.
Index: An index is a numerical value that represents the position of an element in an ordered list or data structure. It starts from 0 for the first element and increments by 1 for each subsequent element.
Nested for loops are a way to repeat a set of instructions multiple times within another loop. It allows you to iterate over elements in a multi-dimensional data structure, such as a 2D array.
ArrayIndexOutOfBoundsException: This term refers to an error that occurs when you try to access an element in an array using an index that is outside the valid range. For example, if you have an array with 5 elements and you try to access the element at index 10, this exception will be thrown.
3D Arrays: A 3D array is a multi-dimensional data structure that stores elements in three dimensions. It can be thought of as a cube or a stack of matrices, where each element has three indices instead of two like in a regular 2D array.
Iteration: Iteration refers to the process of repeating a set of instructions multiple times. It is commonly used with loops to perform tasks repeatedly until certain conditions are met.
System.out.print is a Java statement used to display output on the console. It allows you to print text or values directly to the standard output stream.
Standard output stream: The standard output stream refers to the default destination for output in a program. When using System.out.print, it sends the output directly to this stream, which is usually displayed on the console.
Syntax error: A syntax error occurs when there is an error in the structure or format of code that violates programming language rules. For example, forgetting to include closing parentheses after using System.out.print would result in a syntax error.
Escape sequences: Escape sequences are special characters used within strings that have specific meanings in programming languages. They allow you to represent certain characters or control codes that cannot be typed directly into code.
System.out.println is a Java statement used to display output on the console. It prints the specified message or value and adds a new line character at the end.
Variable: A variable is a named storage location in computer memory that holds a value. It can be used to store data that can be accessed and manipulated in a program.
Method: A method is a block of code that performs a specific task. It can take input parameters, perform operations, and return a result.
String: In Java, String refers to a sequence of characters. It is used to represent textual data and is one of the most commonly used data types in programming.
Row-major traversal refers to accessing elements in a multi-dimensional array by iterating through each row first before moving on to the next row. In this traversal order, consecutive elements are stored contiguously in memory along rows.
Multi-Dimensional Array: A multi-dimensional array is an array with more than one dimension (e.g., 2D or 3D). It organizes data into rows and columns (and possibly additional dimensions) to represent complex structures.
Column-Major Traversal: Column-major traversal refers to accessing elements in a multi-dimensional array by iterating through each column first before moving on to the next column. Consecutive elements are stored contiguously along columns.
Indexing: Indexing refers to the process of accessing or referring to a specific element in an array using its position or index. It allows you to retrieve or modify individual elements within the array.
Column-major traversal refers to accessing elements in a multi-dimensional array by iterating through each column first before moving on to the next column. In this traversal order, consecutive elements are stored contiguously in memory along columns.
Multi-Dimensional Array: A multi-dimensional array is an array with more than one dimension (e.g., 2D or 3D). It organizes data into rows and columns (and possibly additional dimensions) to represent complex structures.
Row-Major Traversal: Row-major traversal refers to accessing elements in a multi-dimensional array by iterating through each row first before moving on to the next row. Consecutive elements are stored contiguously along rows.
Indexing: Indexing refers to the process of accessing or referring to a specific element in an array using its position or index. It allows you to retrieve or modify individual elements within the array.
Traversal algorithms are methods used to visit and process all elements in a data structure, such as arrays, linked lists, or trees. They allow you to access each element individually and perform operations on them.
Depth-First Search (DFS): DFS is a traversal algorithm that explores as far as possible along each branch before backtracking. It uses a stack to keep track of visited nodes.
Breadth-First Search (BFS): BFS is a traversal algorithm that explores all the vertices of a graph in breadth-first order, meaning it visits all neighbors before moving on to their neighbors. It uses a queue to maintain the order of exploration.
In-order Traversal: In-order traversal is commonly used for binary trees and visits nodes in ascending order when applied to binary search trees. It follows the pattern left subtree - root - right subtree.
An if statement is a programming construct that allows the execution of a block of code only if a certain condition is true.
else statement: A programming construct that allows the execution of a block of code when the condition in the if statement is false.
boolean expression: A logical expression that evaluates to either true or false.
nested if statements: When an if statement is placed inside another if statement. It allows for more complex decision-making processes.
Autoboxing is the automatic conversion of a primitive data type to its corresponding wrapper class object. For example, when an int is assigned to an Integer object, autoboxing occurs.
Wrapper Class: A wrapper class is a class that encapsulates a primitive data type and provides methods for accessing, manipulating, and converting it. For example, Integer is the wrapper class for int.
Primitive Data Type: A primitive data type represents basic values and includes types like int, double, boolean, etc.
Boxing: Boxing refers to the process of converting a primitive data type to its corresponding wrapper class object. It is another term used interchangeably with autoboxing.
Consecutive sequences refer to sets of numbers where each subsequent number follows directly after its predecessor without any gaps or missing values.
Arithmetic Sequence: A sequence of numbers where the difference between consecutive terms is constant.
Geometric Sequence: A sequence of numbers where each term is obtained by multiplying the previous term by a fixed, non-zero number.
Fibonacci Sequence: A sequence of numbers in which each number is the sum of the two preceding ones.