Implementing Array Algorithms

Hello there! I'm Saavi, and I'm excited to walk you through some of the most useful tools in your programming toolkit: standard array algorithms.

Think of an array like a long street of houses, and each house has an address (its index) and something inside (its value). An "array traversal" is like taking a walk down that street, starting at house 0 and visiting each one in order until the end. The algorithms we'll learn today are just different tasks you can perform on that walk.

Let's get started.

Finding a Minimum or Maximum Value

This is the "king of the hill" algorithm. To find the highest score in a list, you'd start by assuming the very first score is the highest. Then, you walk through the rest of the list. If you find a score that's higher than your current "king," you replace it. By the time you reach the end, you're left with the true highest score.

int[] scores = {88, 92, 75, 100, 95};

// Assume the first element is the max
int maxScore = scores[0];

// Start loop at the SECOND element (index 1)
for (int i = 1; i < scores.length; i++) {

[[fig:max_score_trace]]

  if (scores[i] > maxScore) {
    maxScore = scores[i]; // New king of the hill!
  }
}

// After the loop, maxScore will be 100

Computing a Sum or Average

This is like being a cashier at a grocery store. You start with your register at $0.00 (an "accumulator" variable) and add the price of each item one by one.

To find a sum, you initialize a variable (e.g., sum) to 0. Then, you loop through the array and add each element to sum.

double[] prices = {12.50, 4.25, 23.00};
double sum = 0.0;

for (int i = 0; i < prices.length; i++) {

[[fig:sum_average_trace]]

  sum = sum + prices[i]; // or sum += prices[i];
}

// To get the average, just divide by the number of items.
// But watch out for integer division if your numbers are ints!
double average = sum / prices.length;

Checking for Properties

Sometimes you don't need a number, but a true or false answer.

1. Does at least one element have a property? (e.g., "Does any player have a perfect score?") You can loop through and if you find one, you can stop and return true immediately. If you get all the way to the end without finding one, you can return false.

// Check if any score is 100
boolean foundPerfectScore = false;
for (int score : scores) { // Using an enhanced for-loop
  if (score == 100) {
    foundPerfectScore = true;
    break; // Found it! No need to keep looking.
  }
}

2. Do all elements have a property? (e.g., "Did every student pass the test?") This is the opposite. You assume the answer is true and look for a reason to say false. If you find even one element that doesn't have the property, you can stop and return false.

// Check if all scores are passing (>= 60)
boolean allPassed = true;
for (int score : scores) {
  if (score < 60) {
    allPassed = false;
    break; // Found a failing score, so not all passed.
  }
}

Counting Elements with a Property

This is a blend of summing and checking a property. You create a counter variable, initialize it to 0, and loop through the array. If an element meets your criteria, you increment the counter.

// Count how many scores are A's (>= 90)
int numAs = 0;
for (int score : scores) {
  if (score >= 90) {
    numAs++;
  }
}

Accessing Consecutive Pairs

What if you want to find the biggest jump in temperature between two consecutive days? You need to compare temps[0] with temps[1], then temps[1] with temps[2], and so on.

The key here is that your loop must stop one element early to avoid falling off the end of the array! If you try to access temps[i+1] when i is the last index, you'll get an ArrayIndexOutOfBoundsException.

int[] temps = {72, 75, 68, 79, 82};
// Loop stops at temps.length - 1
for (int i = 0; i < temps.length - 1; i++) {
  int temp1 = temps[i];
  int temp2 = temps[i+1];
  System.out.println("Comparing " + temp1 + " and " + temp2);
}

Finding Duplicates

A common way to check for duplicates is with a nested loop. The outer loop picks an element, and the inner loop checks all the subsequent elements to see if they match.

String[] names = {"Maya", "Carlos", "Priya", "Maya"};
boolean hasDuplicates = false;

for (int i = 0; i < names.length; i++) {
  for (int j = i + 1; j < names.length; j++) {
    if (names[i].equals(names[j])) { // Use .equals() for objects!
      hasDuplicates = true;
      break; // Found a duplicate, can stop inner loop
    }
  }
  if (hasDuplicates) {
    break; // Can stop outer loop too
  }
}

Shifting, Rotating, and Reversing

These algorithms actually change the array.

Shifting: To shift all elements left, you can copy arr[1] into arr[0], arr[2] into arr[1], and so on. You usually need to save the first element beforehand if you want to "rotate" it to the end.

// Rotate all elements one spot to the left
int[] nums = {10, 20, 30, 40};
int first = nums[0]; // Save the first element

for (int i = 0; i < nums.length - 1; i++) {
  nums[i] = nums[i+1]; // Shift left
}

nums[nums.length - 1] = first; // Put the first element at the end
// nums is now {20, 30, 40, 10}

Reversing: The most efficient way to reverse an array in place is to use two "pointers" or indices. One starts at the beginning (start) and one at the end (end). You swap their elements, then move the pointers toward the middle (start++, end--) until they meet.

int[] data = {1, 2, 3, 4, 5};
int start = 0;
int end = data.length - 1;

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

  // Move pointers
  start++;
  end--;
}
// data is now {5, 4, 3, 2, 1}

These patterns are your building blocks. Once you master them, you can combine them to solve almost any array problem the AP exam throws at you.

Let's put these patterns into practice with a couple of examples.

public double averageSalePrice(double[] prices) {
  // ... your code here ...
}

public double averageSalePrice(double[] prices) {
  double sum = 0.0;
  int count = 0;

  for (int i = 0; i < prices.length; i++) {
    if (prices[i] > 0) {
      sum += prices[i];
      count++;
    }
  }

  // This is a critical check!
  if (count == 0) {
    return 0.0; // Or handle as an error, but 0.0 is a safe return.
  }

  return sum / count;
}

public void shiftRight(int[] nums) {
  // Handle edge case of empty or single-element array
  if (nums.length < 2) {
    return;
  }

  // 1. Save the last element
  int last = nums[nums.length - 1];

  // 2. Shift everything from right to left
  for (int i = nums.length - 2; i >= 0; i--) {
    nums[i + 1] = nums[i];
  }

  // 3. Place the saved element at the front
  nums[0] = last;
}

Ready to try on your own? Here are a couple of challenges. Don't worry about writing the full class, just focus on the logic inside the method.

Problem 1: isSorted

Write a boolean method isSorted that takes an array of integers and returns true if the array is sorted in ascending (non-decreasing) order, and false otherwise. For example, {10, 20, 20, 30} is sorted, but {10, 30, 20} is not.

• Hint
  This involves checking consecutive pairs. You're looking for any place where array[i] is greater than array[i+1]. If you find even one, you know the answer is false.
• Hint
  What should your loop bounds be?

Problem 2: countDuplicates

Write a method countDuplicates that takes an array of String objects and returns the number of strings that appear more than once. For example, in {"A", "B", "A", "C", "B", "A"}, the strings "A" and "B" are duplicates, so the method should return 2.

• Hint
  This is a tough one! A nested loop is a good place to start. But how do you avoid counting the same duplicate string multiple times?
• Hint
  Consider sorting the array first. How might that make counting duplicates easier? (This is a more advanced approach, but great practice!)