01 / 21
3 7 1 9 4

Implementing
Array Algorithms

Master the essential patterns for traversing, searching, and manipulating arrays in Java: the building blocks of every AP CSA solution.

AP Computer Science A

What Is an Array?

An array is a fixed-size, ordered collection of elements, all of the same type. Each element is stored at a numbered position called an index, starting at 0 and ending at length - 1.

12 5 23 8 17 [0] [1] [2] [3] [4] int[] arr = {12, 5, 23, 8, 17};

Why Array Algorithms Matter

Nearly every data-processing task reduces to a pattern on arrays. On the AP exam, you will be expected to write, trace, and debug algorithms that traverse, modify, and analyze arrays.

Traversal
Visit every element once using a loop: the foundation of all other patterns.
Accumulation
Combine elements into a single result: sum, product, count, or string.
Search
Locate a target value by checking elements one-by-one (linear search).

The Traversal Pattern

A traversal visits every element of an array exactly once. In Java, the two standard forms are the indexed for loop and the enhanced for loop.

// Indexed for loop for (int i = 0; i < arr.length; i++) { System.out.println(arr[i]); } // Enhanced for loop for (int val : arr) { System.out.println(val); }

Core Rule: Bounds & Access

0 1 2 3 4 Valid: 0 to length - 1 [-1] [5] arr.length = 5

The Accumulation Pattern

An accumulator variable is initialized before the loop and updated inside it. This pattern computes a sum, product, count, or builds a string.

// Find the sum of all elements int sum = 0; for (int val : arr) { sum += val; } // Count elements greater than 10 int count = 0; for (int val : arr) { if (val > 10) count++; }

for Loop vs Enhanced for

Indexed for Enhanced for
Syntax for(int i=0; ...) for(int v : arr)
Access index? Yes No
Modify elements? Yes No (copy only)
Traverse subset? Yes (change bounds) No (full pass)
Readability Moderate Cleaner

How to Apply an Array Algorithm

1
Identify the goal: Are you computing a value (sum, min, max), searching for something, or transforming the array?
2
Choose the loop: Need the index? Use for(int i...). Read-only? Use enhanced for.
3
Initialize accumulators before the loop. Sum → 0, product → 1, min/max → first element.
4
Write the body: Update accumulators or check conditions inside the loop.
5
Check edge cases: Empty arrays, single-element arrays, and off-by-one bounds.

Example 1: Finding the Maximum

3 7 42 15 9 [0] [1] [2] [3] [4] ★ max
int max = arr[0]; // start with first element for (int i = 1; i < arr.length; i++) { if (arr[i] > max) { max = arr[i]; } }

Example 2: Linear Search

8 3 14 21 6 11 scanning... Found at [3]
public static int linearSearch(int[] arr, int target) { for (int i = 0; i < arr.length; i++) { if (arr[i] == target) { return i; // found } } return -1; // not found }

Example 3: Right Shift & Insert

To insert a value at index \( k \), shift all elements from index \( k \) onward one position to the right, then place the new value.

Before: 5 12 8 3 _ shift right After: 5 99 12 8 3 inserted 99
// Right shift from index k, then insert value for (int i = arr.length - 1; i > k; i--) { arr[i] = arr[i - 1]; } arr[k] = newValue;

Example 4: Reversing an Array

Original A B C D E swap Reversed E D C B A
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; }

Example 5: Counting Duplicates

Comparing every pair of elements requires a nested loop. The inner loop starts at \( i + 1 \) to avoid counting each pair twice.

int dupes = 0; for (int i = 0; i < arr.length; i++) { for (int j = i + 1; j < arr.length; j++) { if (arr[i] == arr[j]) { dupes++; } } }

Example 6: Left Shift (Remove at Index)

To remove the element at index \( k \), shift all elements after it one position to the left, then handle the last slot.

// Left shift: remove element at index k for (int i = k; i < arr.length - 1; i++) { arr[i] = arr[i + 1]; } arr[arr.length - 1] = 0; // or a sentinel

Common Mistakes

✕ Off-by-One
Using <= instead of < with arr.length, causing an ArrayIndexOutOfBoundsException.
✕ Wrong Initializer
Setting max = 0 instead of arr[0]. Fails when all values are negative.
✕ Modifying in Enhanced For
Assigning val = newVal in an enhanced for loop changes the copy, not the array element.
✕ Wrong Shift Direction
Shifting left by iterating backward (or right by iterating forward) overwrites elements before they are moved.

Algorithm Summary

Algorithm Pattern Key Detail
Sum / Average Accumulate Init to 0
Min / Max Accumulate Init to arr[0]
Linear Search Search Return -1 if not found
Count matches Accumulate + filter if inside loop
Reverse Two-pointer swap Loop to length/2
Right Shift Backward iteration Start at end
Left Shift Forward iteration Start at removal index

Question 1 of 5

What is the output of the following code?

int[] a = {4, 9, 2, 7};
int s = 0;
for (int v : a) { s += v; }
System.out.println(s);

Question 2 of 5

Which loop correctly finds the minimum value in an int[] named data?

Question 3 of 5

Given int[] arr = {1, 2, 3, 4, 5}, what is arr[arr.length - 1]?

Question 4 of 5

You want to double every element in an array. Which approach works?

Question 5 of 5

After running this code, what does arr contain?

int[] arr = {10, 20, 30, 40};
for(int i = 0; i < arr.length / 2; i++) {
  int t = arr[i];
  arr[i] = arr[arr.length-1-i];
  arr[arr.length-1-i] = t;
}