Implementing 2D Array Algorithms

You've learned how to create and traverse 2D arrays. Now, let's put them to work. An algorithm is just a set of steps to solve a problem. For 2D arrays, most algorithms involve a nested loop to visit every element, but what you do inside that loop is what matters.

Let's use a great analogy: a 2D array is like a digital spreadsheet. The rows and columns are just like in Excel. The algorithms we'll write are like creating our own SUM(), MAX(), or COUNTIF() functions.

Aggregations: Sum, Average, Min & Max

These algorithms "boil down" the entire grid (or a part of it) into a single number. They all follow a similar pattern:

1. 1
   Initialize

   a variable to hold your result.
2. 2
   Traverse

   the array (or the specific row/column) with nested loops.
3. 3
   Update

   your variable at each element.
4. 4
   Return

   the final result after the loops finish.

Finding a Sum or Average

Let's say we have a 2D array of integers representing weekly sales for different products at a farmer's market in Dallas.

int[][] weeklySales = {
  {150, 200, 160, 210}, // Product A
  {120, 130, 140, 125}, // Product B
  {180, 190, 220, 240}  // Product C
};

To find the total sales of all products, we sum every element.

public static int getTotalSales(int[][] sales) {
  int total = 0; // 1. Initialize
  for (int r = 0; r < sales.length; r++) {
    for (int c = 0; c < sales[0].length; c++) {
      total += sales[r][c]; // 3. Update
    }
  }
  return total; // 4. Return
}

To find the average, you'd do the same thing, but at the end, divide by the total number of elements: sales.length * sales[0].length.

What if you only want the sum for a specific row (e.g., total sales for Product B, which is row 1)? You just use a single loop for that row's columns.

public static int getRowSum(int[][] sales, int row) {
  int rowTotal = 0;
  // Note: We only loop through the columns of the specified row
  for (int c = 0; c < sales[row].length; c++) {
    rowTotal += sales[row][c];
  }
  return rowTotal;
}

Finding the Minimum or Maximum

This is almost identical, but the update step is a comparison. To find the highest sale amount in the whole grid:

public static int getMaximumSale(int[][] sales) {
  // 1. Initialize with the VERY FIRST element.
  int maxVal = sales[0][0];
  for (int r = 0; r < sales.length; r++) {
    for (int c = 0; c < sales[0].length; c++) {
      // 3. Update if we find a bigger value
      if (sales[r][c] > maxVal) {
        maxVal = sales[r][c];
      }
    }
  }
  return maxVal; // 4. Return
}

Property Checks: Counting and Searching

These algorithms check elements against a certain condition.

• Count how many elements have a property.
• Determine if at least one element has a property.
• Determine if all elements have a property.

Let's imagine a boolean[][] grid representing a tic-tac-toe board, where true means 'X' is in that spot.

Counting Elements with a Property

How many 'X's are on the board? This is just like finding a sum, but we add 1 instead of the element's value.

public static int countXs(boolean[][] board) {
  int count = 0;
  for (int r = 0; r < board.length; r++) {
    for (int c = 0; c < board[0].length; c++) {
      if (board[r][c] == true) { // The property check
        count++;
      }
    }
  }
  return count;
}

Finding "At Least One"

Does the board have at least one 'X'? You can stop searching as soon as you find one.

public static boolean hasAtLeastOneX(boolean[][] board) {
  for (int r = 0; r < board.length; r++) {
    for (int c = 0; c < board[0].length; c++) {
      if (board[r][c] == true) {
        return true; // Found one! Exit immediately.
      }
    }
  }
  // If we get here, the loops finished without finding any.
  return false;
}

Determining if "All" Have a Property

This one is tricky. The logic is inverted. You assume the property is true for all elements, and you search for a single counterexample that proves you wrong.

Let's say we have an array of test scores and want to see if every student in a particular class (row) passed (scored >= 60).

public static boolean allPassedInRow(int[][] scores, int row) {
  for (int c = 0; c < scores[row].length; c++) {
    if (scores[row][c] < 60) {
      // Found a failing score. We can immediately say they didn't ALL pass.
      return false;
    }
  }
  // If the loop completes without finding any failing scores, then they all passed.
  return true;
}

Positional and Structural Algorithms

These algorithms care about the position of elements relative to each other.

Accessing Consecutive Pairs

To check for adjacent identical numbers in a row, you compare grid[r][c] with grid[r][c+1]. The key is to stop your column loop one step early to avoid an ArrayIndexOutOfBoundsException.

// Check for any adjacent duplicates in a single row
for (int c = 0; c < grid[row].length - 1; c++) { // Notice the "- 1"
  if (grid[row][c] == grid[row][c+1]) {
    System.out.println("Found a pair!");
  }
}

Finding Duplicates

To find if there are any duplicate values in the entire 2D array, a common (though not the most efficient) approach is to use nested loops to compare every element to every other element. This is a bit more complex, often involving four nested loops. The AP exam is more likely to ask you to find duplicates within a single row or column.

Shifting and Rotating

This is a classic AP problem. Let's shift a row to the left. The element at index 0 is lost, grid[r][1] moves to grid[r][0], grid[r][2] moves to grid[r][1], and so on.

public static void shiftRowLeft(int[] row) {
  // To rotate, you'd save this value first: int first = row[0];
  for (int c = 0; c < row.length - 1; c++) {
    row[c] = row[c + 1];
  }
  // The last element can be set to 0 or some other default.
  // If rotating, you'd set it to the saved 'first' value.
  row[row.length - 1] = 0;
}

To use this on a 2D array, you'd pass myGrid[someRow] to this method.

Reversing a Row or Column

To reverse a row, you swap the first and last elements, then the second and second-to-last, and so on, until you meet in the middle. This is often called the "two-pointer" technique.

public static void reverseRow(int[] row) {
  int start = 0;
  int end = row.length - 1;

  while (start < end) {
    // Swap the elements
    int temp = row[start];
    row[start] = row[end];
    row[end] = temp;

    // Move the pointers
    start++;
    end--;
  }
}

These standard algorithms are your toolkit. The AP exam will test you by asking you to implement them directly or to combine them to solve a slightly new problem. Practice them until the patterns feel second nature.

Let's walk through a few problems to see these algorithms in action. The key is to break down the problem and identify which pattern to use.

int[][] gradebook = {
  {90, 95, 88, 92},  // Student 0: Priya
  {75, 80, 78, 85},  // Student 1: Carlos
  {100, 98, 95, 99}  // Student 2: Aaliyah
};
int finalExamCol = 3;

public int getHighestInColumn(int[][] grades, int col) {
  // Handle empty array case to be robust
  if (grades.length == 0) return -1; // Or throw an exception

  int maxScore = grades[0][col]; // Initialize with the first row's value in that col
  for (int r = 1; r < grades.length; r++) {
    if (grades[r][col] > maxScore) {
      maxScore = grades[r][col];
    }
  }
  return maxScore;
}

public void shiftRowRight(String[] row) {
  // Start from the second-to-last element and go down to the first.
  for (int i = row.length - 1; i > 0; i--) {
    row[i] = row[i - 1]; // Copy the element from the left into the current spot.
  }
  // Now, clear the first seat.
  row[0] = "empty";
}

Ready to try a couple on your own? Don't worry about writing a full program, just focus on the logic for the method itself.

Problem 1: The Vending Machine

You're given a 2D integer array inventory where each cell represents the quantity of a snack in a vending machine in Seattle. Write a method isAnythingSoldOut(int[][] inventory) that returns true if any snack has a quantity of 0, and false otherwise.

Hint: This is an "at least one" algorithm. What does that mean for your loops? Can you stop early?

Problem 2: Reversing a Column

You're given a 2D array gameBoard. Write a method reverseColumn(String[][] gameBoard, int col) that reverses the order of the elements in a specified column. For example, the element at the top of the column should swap with the element at the bottom, and so on.

Hint: This is very similar to reversing a 1D array. Use the two-pointer technique (a top index starting at 0, a bottom index starting at the last row). What will your while loop condition be? Remember to use a temporary variable for swapping.