Aim for FiveComputer Science A

Unit 4 · Topic 4.5

4.5 Implementing Array Algorithms

Most array questions are variations on a short list of standard algorithms: min and max, sum and average, any and all, counting, consecutive pairs, duplicates, shifting, rotating and reversing. Learn the pattern for each and you can adapt it to almost any problem.

Key terms

  • min and max
  • sum and average
  • count
  • consecutive pairs
  • duplicates
  • shift, rotate and reverse

One traversal, one tracking variable

Most of these are a single traversal with the right variable to track the answer. Pick the variable's starting value carefully, because that's where most bugs come from.

  • Min or max: start with data[0] and replace it whenever you see something smaller (or larger).
  • Sum or average: add every element to a running total, then divide by length, casting to double if needed.
  • Count: add 1 to a counter when an element meets the condition.
  • At least one: return true as soon as an element meets the condition, and false after the loop.
  • All: return false as soon as an element fails, and true after the loop.
  • Consecutive pairs: loop i from 0 to length - 2 and compare data[i] with data[i + 1].
  • Duplicates: compare every pair with nested loops, starting the inner index at i + 1 (2.11).

Checking all elements

"All" and "at least one" are mirror images. For "all", one failure is enough to answer false:

public static boolean allPositive(int[] data) { for (int value : data) { if (value <= 0) { return false; } } return true; }

Shifting and rotating

To rotate left by one, save the first element, shift every other element one place left, then put the saved value at the end. Shifting right is the mirror image, but loop from the end backward, or you'll copy the same value into every slot. A shift that doesn't wrap around just fills the empty end with something else, like 0.

Reversing

To reverse in place, swap the first and last elements, then the second and second-to-last, and so on, stopping at the middle. The partner of index i is arr.length - 1 - i. A swap needs a temporary variable, or you'll lose one of the values.

int[] arr = {8, 6, 7, 5, 3}; for (int i = 0; i < arr.length / 2; i++) { int temp = arr[i]; arr[i] = arr[arr.length - 1 - i]; arr[arr.length - 1 - i] = temp; }

This turns 8, 6, 7, 5, 3 into 3, 5, 7, 6, 8. The loop runs arr.length / 2 times, so for odd lengths the middle element stays put. Looping all the way to arr.length would swap everything twice and put it back the way it was.

Worked examples

Try each one yourself first, then open the solution.

  1. Example 1

    Write a method: range of the data

    Write a method range(int[] data) that returns the difference between the largest and smallest values. data has at least one element. One solution:public static int range(int[] data) { int low = data[0]; int high = data[0]; for (int value : data) { if (value < low) { low = value; } if (value > high) { high = value; } } return high - low; }

    Show the solution
    1. Step 1: This combines min and max in one traversal.
    2. Step 2: Start both low and high at data[0], a real value, not 0. With the data -4, -9, -2, -7, a high that started at 0 would never change and give the wrong answer.
    3. Step 3: For -4, -9, -2, -7: low ends at -9 and high at -2, so the range is -2 − (-9) = 7.
    4. Step 4: For a one-element array like {5}, both are 5 and the range is 0.

    Answer: The method above; it returns 7 for {-4, -9, -2, -7} and 0 for {5}.

  2. Example 2

    Rotating left

    What does this code print?int[] arr = {1, 2, 3, 4, 5}; int first = arr[0]; for (int i = 0; i < arr.length - 1; i++) { arr[i] = arr[i + 1]; } arr[arr.length - 1] = first; for (int v : arr) { System.out.print(v + " "); } System.out.println();

    Show the solution
    1. Step 1: Save first = 1.
    2. Step 2: The loop runs for i = 0 to 3 and copies each element from the right: arr[0] = 2, arr[1] = 3, arr[2] = 4, arr[3] = 5. Stopping at length - 1 keeps arr[i + 1] in bounds.
    3. Step 3: Then the saved 1 goes into the last slot.

    Answer: It prints 2 3 4 5 1 .

  3. Example 3

    Consecutive pairs

    This counts the days where the step count went up from the day before. What does it print?int[] steps = {4000, 6500, 6100, 8000}; int increases = 0; for (int i = 0; i < steps.length - 1; i++) { if (steps[i + 1] > steps[i]) { increases++; } } System.out.println(increases);

    Show the solution
    1. Step 1: Pairs are (4000, 6500), (6500, 6100) and (6100, 8000). The loop stops at i = 2 so i + 1 is at most 3.
    2. Step 2: Up, down, up: 2 increases.

    Answer: It prints 2.

Common mistakes

  • Starting a max at 0 or a min at 0. Start with data[0].
  • Looping to i < arr.length while using arr[i + 1], which goes out of bounds on the last pass.
  • Returning true from an "all" check inside the loop after just one element passes.
  • Swapping without a temporary variable, or reversing all the way to the end, which undoes the swaps.

On the exam

  • These same patterns are what free-response Questions 3 and 4 are built on, using an ArrayList or a 2D array instead of a plain array. Name the pattern, then adjust it.

Connected topics

Videos

  • AP Computer Science A - Topic 4.5 - Part 1: Implementing Array Algorithms

    Tim Gallagher Computer ScienceWatch on YouTube (opens in a new tab)

  • AP CSA Unit 4 Array Algorithms (2025-2026)

    PickcodeWatch on YouTube (opens in a new tab)

  • Find The Maximum Number In A Java Array

    Bill BarnumWatch on YouTube (opens in a new tab)

  • AP Computer Science A - Topic 4.5 - Part 2: Implementing Array Algorithms

    Tim Gallagher Computer ScienceWatch on YouTube (opens in a new tab)

  • AP Computer Science A - Topic 4.5 - Part 3: Implementing Array Algorithms

    Tim Gallagher Computer ScienceWatch on YouTube (opens in a new tab)

  • Reversing the Values in an Array (Java Tutorial)

    Bill BarnumWatch on YouTube (opens in a new tab)

Check yourself

4 questions on 4.5 Implementing Array Algorithms. Pick an answer to see if you got it, and why.

Question 1 of 4

The following method is intended to return the largest value in arr./** Precondition: arr.length > 0 */ public static int findMax(int[] arr) { /* missing code */ for (int v : arr) { if (v > max) { max = v; } } return max; }Which of the following can replace /* missing code */ so that the method works for every array that meets the precondition?

Question 2 of 4

The following method is intended to return true if every element of arr is positive and false otherwise.public static boolean allPositive(int[] arr) { /* missing code */ }Which of the following can replace /* missing code */ so that the method works as intended?

Question 3 of 4

Consider the following code segment.int[] a = {3, 5, 5, 2, 8, 9}; int ups = 0; for (int i = 1; i < a.length; i++) { if (a[i] > a[i - 1]) { ups++; } } System.out.println(ups);What is printed as a result of executing the code segment?

Question 4 of 4

Consider the following method.public static boolean hasDuplicate(int[] arr) { for (int i = 0; i < arr.length; i++) { for (int j = i + 1; j < arr.length; j++) { if (arr[i] == arr[j]) { return true; } } } return false; }Which of the following describes why the inner loop starts at i + 1 rather than at 0?

0 of 4 answered