Introduction
Topic 4.13 applies traversal techniques to implement standard algorithms for 2D arrays. These algorithms extend 1D array patterns to two dimensions, often targeting specific rows, columns, or subsections rather than the entire array.
Understanding these algorithms is critical for the 2D array free-response question (Question 4) on the AP exam. You'll learn to find extremes, compute statistics, check properties, work with consecutive elements, detect duplicates, and manipulate array structure.
Finding Minimum and Maximum
There are standard algorithms that utilize 2D array traversals to determine a minimum or maximum value of all the elements or for a designated row, column, or other subsection.
Maximum of Entire Array
public static int findMax(int[][] arr)
{
int max = arr[0][0];
for (int r = 0; r < arr.length; r++)
{
for (int c = 0; c < arr[0].length; c++)
{
if (arr[r][c] > max)
{
max = arr[r][c];
}
}
}
return max;
}
Maximum in Specific Row
public static int maxInRow(int[][] arr, int row)
{
int max = arr[row][0];
for (int c = 1; c < arr[0].length; c++)
{
if (arr[row][c] > max)
{
max = arr[row][c];
}
}
return max;
}
Maximum in Specific Column
public static int maxInColumn(int[][] arr, int col)
{
int max = arr[0][col];
for (int r = 1; r < arr.length; r++)
{
if (arr[r][col] > max)
{
max = arr[r][col];
}
}
return max;
}
Computing Sum and Average
Standard algorithms compute a sum or average of all the elements or for a designated row, column, or other subsection.
Sum of Entire Array
public static int totalSum(int[][] arr)
{
int sum = 0;
for (int[] row : arr)
{
for (int val : row)
{
sum += val;
}
}
return sum;
}
Average of Specific Row
public static double rowAverage(int[][] arr, int row)
{
int sum = 0;
for (int c = 0; c < arr[0].length; c++)
{
sum += arr[row][c];
}
return (double) sum / arr[0].length;
}
The formula:
Sum of Diagonal
public static int diagonalSum(int[][] arr)
{
int sum = 0;
for (int i = 0; i < arr.length; i++)
{
sum += arr[i][i];
}
return sum;
}
Checking Element Properties
Algorithms determine if at least one element has a particular property, if all elements have a particular property, or count how many elements have a particular property in the entire 2D array or for a designated row, column, or other subsection.
At Least One Element in Array
public static boolean hasNegative(int[][] arr)
{
for (int[] row : arr)
{
for (int val : row)
{
if (val < 0)
{
return true;
}
}
}
return false;
}
All Elements in Column
public static boolean allPositiveInColumn(int[][] arr, int col)
{
for (int r = 0; r < arr.length; r++)
{
if (arr[r][col] <= 0)
{
return false;
}
}
return true;
}
Count in Specific Row
public static int countEvensInRow(int[][] arr, int row)
{
int count = 0;
for (int c = 0; c < arr[0].length; c++)
{
if (arr[row][c] % 2 == 0)
{
count++;
}
}
return count;
}
Accessing Consecutive Pairs
Standard algorithms access all consecutive pairs of elements.
Consecutive Pairs in Row
public static int countRowIncreases(int[][] arr, int row)
{
int count = 0;
for (int c = 0; c < arr[0].length - 1; c++)
{
if (arr[row][c + 1] > arr[row][c])
{
count++;
}
}
return count;
}
Critical: Loop to arr[0].length - 1 to avoid accessing invalid column index.
Consecutive Pairs in Column
public static int countColumnIncreases(int[][] arr, int col)
{
int count = 0;
for (int r = 0; r < arr.length - 1; r++)
{
if (arr[r + 1][col] > arr[r][col])
{
count++;
}
}
return count;
}
Detecting Duplicates
Algorithms determine the presence or absence of duplicate elements in the 2D array or in a designated row, column, or other subsection.
Duplicates in Entire Array
public static boolean hasDuplicates(int[][] arr)
{
for (int r1 = 0; r1 < arr.length; r1++)
{
for (int c1 = 0; c1 < arr[0].length; c1++)
{
for (int r2 = 0; r2 < arr.length; r2++)
{
for (int c2 = 0; c2 < arr[0].length; c2++) // Don't compare element with itself
{
if (r1 != r2 || c1 != c2)
{
if (arr[r1][c1] == arr[r2][c2])
{
return true;
}
}
}
}
}
}
return false;
}
Duplicates in Row
public static boolean hasRowDuplicates(int[][] arr, int row)
{
for (int c1 = 0; c1 < arr[0].length; c1++)
{
for (int c2 = c1 + 1; c2 < arr[0].length; c2++)
{
if (arr[row][c1] == arr[row][c2])
{
return true;
}
}
}
return false;
}
Shifting and Rotating
Algorithms shift or rotate elements in a row left or right or in a column up or down.
Shift Row Left
public static void shiftRowLeft(int[][] arr, int row)
{
int first = arr[row][0];
for (int c = 0; c < arr[0].length - 1; c++)
{
arr[row][c] = arr[row][c + 1];
}
arr[row][arr[0].length - 1] = 0; // Or keep first
}
Rotate Row Right
public static void rotateRowRight(int[][] arr, int row)
{
int last = arr[row][arr[0].length - 1];
for (int c = arr[0].length - 1; c > 0; c--)
{
arr[row][c] = arr[row][c - 1];
}
arr[row][0] = last;
}
Shift Column Down
public static void shiftColumnDown(int[][] arr, int col)
{
int last = arr[arr.length - 1][col];
for (int r = arr.length - 1; r > 0; r--)
{
arr[r][col] = arr[r - 1][col];
}
arr[0][col] = 0; // Or keep last
}
Reversing Elements
Algorithms reverse the order of the elements in a row or column.
Reverse Row
public static void reverseRow(int[][] arr, int row)
{
for (int c = 0; c < arr[0].length / 2; c++)
{
int temp = arr[row][c];
arr[row][c] = arr[row][arr[0].length - 1 - c];
arr[row][arr[0].length - 1 - c] = temp;
}
}
Reverse Column
public static void reverseColumn(int[][] arr, int col)
{
for (int r = 0; r < arr.length / 2; r++)
{
int temp = arr[r][col];
arr[r][col] = arr[arr.length - 1 - r][col];
arr[arr.length - 1 - r][col] = temp;
}
}
Complete Example: Student Grade Analysis
// Each row is a student, each column is a test
int[][] grades = {
{85, 90, 78},
{92, 88, 95},
{76, 82, 88}
};
// Find highest test average
public static int bestStudent(int[][] grades)
{
int bestIndex = 0;
double bestAvg = rowAverage(grades, 0);
for (int r = 1; r < grades.length; r++)
{
double avg = rowAverage(grades, r);
if (avg > bestAvg)
{
bestAvg = avg;
bestIndex = r;
}
}
return bestIndex;
}
// Find hardest test (lowest column average)
public static int hardestTest(int[][] grades)
{
int hardestIndex = 0;
double lowestAvg = columnAverage(grades, 0);
for (int c = 1; c < grades[0].length; c++)
{
double avg = columnAverage(grades, c);
if (avg < lowestAvg)
{
lowestAvg = avg;
hardestIndex = c;
}
}
return hardestIndex;
}
Common Mistakes
Mistake 1: Wrong loop bounds for row/column operations
// WRONG - uses wrong dimension
for (int c = 0; c < arr.length; c++) // Should be arr[0].length
{
sum += arr[row][c];
}
Mistake 2: Comparing element with itself
// WRONG - will always find "duplicate"
if (arr[r][c] == arr[r][c])
{
return true;
}
Mistake 3: Off-by-one with consecutive pairs
// WRONG - accesses invalid index
for (int c = 0; c < arr[0].length; c++)
{
if (arr[row][c] > arr[row][c + 1]) { } // Error when c = length-1
}