Arrays and 2D Arrays
Arrays
Arrays are 10-15% of the exam, so it is very important to understand the basics of arrays. Collegeboard will typically test you on:
- Representing multiple items as array objects
- Traversing an array by accessing the elements using iteration statements
- Standard algorithms that utilize array traversals to perform functions
Array Basics
An array can contain primitives (int, char, etc) and object references of a class. Primitive data types have their actual values stored in contiguous memory location.
Important things to note are that:
- Arrays are fixed in size
- Arrays can be used as a static field, local variable, or method parameter
//BASIC ARRAY CONCEPTS
//Declare an array and then allocate memory
int myArray[];
myArray = new int[4];
//Declare while directly assign values
int[] myArray1 = new int[]{ 1, 6, 7, 9};
//Initialize element
myArray[0] = 2;
//Create an array of objects
Object[] arr = new Object[5];
Traversing an Array
Common ways to traverse an array include for loops and enhanced for loops:
- A for loop allows you to access the index, and manipulations can be done by changing the incrementer (ie. i+=2 instead of i++)
- An enhanced for loop is simpler but you CANNOT access the index, only the value
//Basic for loop to print elements of array
int[] arr1 = {0, 6, 8, 2};
// Looping through array by incrementing value of i
//'i' is an index of array 'arr1'
for (int i = 0; i < arr1.length; i++) {
// Print array element present at index i
System.out.println(i + " " + arr1[i]);
}
// NOTE: You may also use an enhanced for loop
for(int value: arr1){
System.out.println(value);
}
void setArray(int[] arr, int n) {
// your code here
for (int i = 0; i < arr.length; i++) {
arr[i] = n;
}
}
int[] array = new int[10];
setArray(array, 10);
for (int i = 0; i<array.length; i++) {
System.out.println(array[i]);
}
// Should print all 10s when working properly
Developing Algorithms Using Arrays
Arrays are an essential part in developing algorithms. It is important to understand how to traverse an array and the structure of an array to accomplish this.
There are lots of algorithms you can create,and CollegeBoard goes over a lot of good examples of this. They go over this in the 6.4 unit videos.
//Example finding the max in an array.
//Finds the maximum in an array
public static int maximum(int[] array) {
//variable that holds value of max value
int maxValue = array[0];
//for each number in the array..
for (int number: array) {
//checks if current index is greater than maxValue
if (number > maxValue) {
//if new max value found, replace current maxValue
maxValue = number;
}
}
return maxValue;
}
//tester array
int[] test = {3, 5, 7, 2, 10};
//returns 10
maximum(test);
Generally, when you are coding algorithms using arrays you will probably use some traversal element. The key thing to think about is what you want to do for each element, because once you have a repeatable action you can just put it in a for loop. You also want to consider which elements you actually want to look at beacuse in some causes you may want to skip some elements.
//Example finding the max in an array.
//Finds the maximum in an array
public static int average(int[] array) {
// put your code here
int sum = 0;
for (int num : array) {
sum += num;
}
return sum/array.length;
}
//tester array
int[] test = {3, 5, 7, 2, 10};
//returns 10
System.out.println(average(test));
2-D Arrays
2-D arrays are 7.5-10% of the exam, so they are also very important to know for the AP exam. Many concepts of 2-D arrays rely on a solid understanding of arrays.
A 2-D array is an array of arrays, and store data similar to a row and column fashion.
Length is determined by the number of rows in the array, which is also the number of arrays in the 2-D array.
Columns is based on the size of each row of an array and can be determined based on the number of elements in the first row.
//create a new 2-d array (default to all 0s)
int[][] twoDArray = new int[3][3];
//access the value at row 2 column 1
twoDArray[1][0];
//get value at the end of a 2-d array
// (twoDArray.length - 1) gets how many arrays (rows)
// (twoDArray[0].length - 1) gets how many elements in first array (columns)
twoDArray[twoDArray.length - 1][twoDArray[0].length - 1];
The 2D array is useful to represent a matrix as well, which then can be accessed by the rows and columns. This is a good way to visualize a 2d array. Here, I will show an example of how a "grid" looks like + initialization
// GRID of our array
// 4 5 6
// 7 8 9
// 1 2 3
// Initializing our array
int[][] twoDArray = {
{4,5,6},
{7,8,9},
{1,2,3}
}
//Prints the 2-d array
public static void print2D(int mat[][])
{
// For each row of the array (goes one array at a time)
for (int row = 0; row < twoDArray1.length; row++) {
//Goes through each element of the array
for (int column = 0; column < twoDArray1[row].length; column++)
System.out.print(mat[row][column] + " ");
// runs for every row (not every element)
System.out.println();
}
}
int twoDArray1[][] = { { 1, 2, 3 },
{ 4, 6, 7 },
{ 8, 9, 10} };
print2D(twoDArray1);
When traversing 2-D arrays it is important to note wether the code is in row-major or column-major order. This basically indicates what the outer for loop of the method is traversing.
If the outer loop is going by column, its in column major order. If the outer loop is going by row, its in row-major order.
The code example above is in row-major order
When you are traversing, again make sure to consider the pros/cons of for vs enhanced for loop (for loop allows you to mess with index). This can be useful to again think about which elements you actually want to take actions on. Furthermore, you may also consider actions that you only want to do for every row, or every column. This could be opposed to every element, in which case you would put it in the outer for loop (see the System.out.println() in above code)
public static void main(String[] args){
int[][] arrayOne = new int[5][7];
for (int row = 0; row < arrayOne.length; row++){
for (int col = 0; col < arrayOne[row].length; col++){
arrayOne[row][col] = row+col - 1;
}
}
System.out.println(arrayOne[4][6]);
}
public static int averageDiagonal (int[][] array2D) {
// your code here
int sum = 0;
int count = 0;
for (int i = 0; i < arr.length; i++) {
sum += arr[i][count];
count++;
}
return sum/arr.length;
}
int[][] arr = {
{1,2,3,4,5,6},
{7,8,9,10,11,12},
{0,1,2,3,4,5},
{10,11,12,13,14,15},
{15,16,17,18,19,20}
};
System.out.println(averageDiagonal(arr));
public static int[] getColumn(int[][] arr2D, int c) {
int[] column = new int[arr2D.length];
for (int row = 0; row < arr2D.length; row++) {
column[row] = arr2D[row][c];
}
return column;
}
public static boolean isLatin(int[][] square) {
if (containsDuplicates(square[0])) {
return false;
}
for (int i = 1; i < square.length; i++) {
if (!hasAllValues(square[0], square[i])) {
return false;
}
}
for (int i = 0; i < square.length; i++) {
if (!hasAllValues(square[0], getColumn(square, i))) {
return false;
}
}
return true;
}
public static Position findPosition(int num, int[][] intArr) {
for (int i = 0; i < intArr.length; i++) {
for (int j = 0; j < intArr[0].length; j++) {
if (num == intArr[i][j]) {
return new Position(i, j);
}
}
}
return null;
}
public static Position[][] getSuccessorArray(int[][] intArr) {
Position[][] positionArray = new Position[intArr.length][intArr[0].length];
for (int i = 0; i < intArr.length; i++) {
for (int j = 0; j < intArr[0].length; j++) {
positionArray[i][j] = findPosition(intArr[i][j] + 1, intArr);
}
}
return positionArray;
}
public static int totalLetters(List<String> wordList) {
int length = 0;
for (String word : wordList) {
length += word.length();
}
return length;
}
public static int basicGapWidth(List<String> wordList, int formattedLen) {
return (formattedLen - totalLetters(wordList)) / (wordList.size() - 1);
}
public static String format(List<String> wordList, int formattedLen) {
int leftover = leftoverSpaces(wordList, formattedLen);
String text = "";
for (int i = 0; i < wordList.length - 1; i++) {
text += wordList.get(i);
for (int j = 0; j < basicGapWidth(wordList, formattedLen); j++) {
text += " ";
}
if (leftover > 0) {
text += " ";
leftover--;
}
}
text += wordList.get(wordList.size() - 1);
return text;
}