6.4. Array Algorithms (FRQs)¶
In this lesson, you will study common algorithms using arrays and loops and practice FRQ (Free Response Question) problems.
Here are some common algorithms that you should be familiar with for the AP CSA exam:
Determine the minimum or maximum value in an array
Compute a sum, average, or mode of array elements
Search for a particular element in the array
Determine if at least one element has a particular property
Determine if all elements have a particular property
Access all consecutive pairs of elements
Determine the presence or absence of duplicate elements
Determine the number of elements meeting specific criteria
Shift or rotate elements left or right
Reverse the order of the elements
6.4.1. Accumulator Pattern for Sum/Average¶
The accumulator pattern is an algorithm that iterates through a set of values using a loop and updates an accumulator variable with those values, for example to compute a sum or average of a set of values. The accumulator pattern has 4 steps:
Initialize the accumulator variable before the loop.
Loop through the values.
Update the accumulator variable inside the loop.
Print or use the accumulated value when the loop is done.
With arrays, the accumulator pattern is used to compute the sum or average of the elements in the array. The sum is the total of all the elements in the array, and the average is the sum divided by the number of elements in the array.
For example,
int[] values = {6, 2, 1, 7, 12, 5};
double sum = 0;
for (int val : values)
{
sum += val;
}
double average = sum / values.length;
System.out.println("Average is " + average);
Here is an object-oriented example that has the array as a private instance variable in the class and provides public methods sum and average that use enhanced for loops. You can use the Java visualizer or the Code Lens button to step through this code.
Try the code below that computes the average of the elements in the array. Can you add another method to compute the sum of the elements?
6.4.2. Min, Max, Search Algorithms¶
In the last lesson, you wrote a spell check algorithm which searched for a word in an array of dictionary words. Searching for the minimum or maximum follows a similar pattern of a loop with an if statement inside it. The pattern to follow is an enhanced for loop or an indexed for loop, with an embedded if statement. Remember that enhanced for loops cannot be used to modify primitive values in an array or to return an index.
for (int value : array)
{
if (value ....)
...
}
for(int i=0; i < array.length; i++)
{
if (array[i] ....)
...
}
The code below finds the minimum (smallest element) in an array. Try it in the Java visualizer with the CodeLens button. Can you change it to find the maximum element instead? Can you also compute the average of the elements?
When searching for an element or a minimum or maximum, it is important not to leave the loop early before finding the correct value and not to replace the value with subsequent ones.
Run the following code. Does it find 7 in the array? Click on Code Lens to trace through the code to see why not. Fix the early return error in the following code.
- Whenever the first element in array is not equal to target.
- Yes, the loop returns as soon as checking the first element, whether it is equal to target or not. It needs to check the whole array before returning false. The else statement should not be included.
- Whenever array contains any element which equals target.
- This would be true if the else statement was not there, but it returns false right away after just checking the first element instead of going through all of the elements to makes sure none of them are equal to target.
- Always
- If the first element is equal to the target, it will return true.
- Never
- It will return false with the else statement if the first element is not equal to the target.
6-4-4: Given that array
is an array of integers and target
is an integer value, which of the following best describes the conditions under which the following code segment will return false?
public boolean find(int[] array, int target)
{
for (int val : array)
{
if (val == target)
{
return true;
}
else
{
return false;
}
}
return false;
}
6.4.3. Test Property¶
Often we loop through an array to see if elements have a particular property, for example all the elements are even or at least one is negative. On the AP exam, this property is often given as a boolean method to use in the if statement to:
Determine if at least one element has a particular property
Determine if all elements have a particular property
Determine the number of elements having a particular property
Here are some patterns. Note that determining if all have a certain property means that we need to check all elements before returning true, so we often have to check for the negation of the property to return false.
// see if at least one has the property
for (int val : values)
{
if (isProperty(val))
{
return true;
}
}
return false;
// see if all have the property
for (int val : values)
{
if (!isProperty(val))
{
return false;
}
}
return true;
// count the number of elements with the property
int count = 0;
for (int val : values)
{
if (isProperty(val))
{
count++;
}
}
The following program segment should count the number of elements in the array that are even using an enhanced for each loop. But, the blocks have been mixed up. Drag the blocks from the left and put them in the correct order on the right. Click the Check button to check your solution.
Write the method allOdd to return true if all the values in the array are odd. First write the helper function isEven to return true or false for one value, using %.
6.4.4. Pairs and Duplicates in Array¶
Here is a pattern to check for duplicates in an array by accessing a pair of elements next to each other, array[i]
and array[i+1]
. Note that we need to use an indexed for loop to get access to the next element.
// check for duplicates next to each other
for (int i = 0; i < values.length - 1; i++)
{
if (values[i] == values[i + 1])
{
return true;
}
}
return false;
If we want to check for duplicates anywhere in the array, we need to use a nested loop to compare all pairs of elements in the array.
// check for duplicates anywhere in the array
for (int i = 0; i < values.length; i++)
{
for (int j = i + 1; j < values.length; j++)
{
if (values[i] == values[j])
{
return true;
}
}
}
return false;
Create a method sumPairs10(nums)
returns true
if there are at least two items in the array nums
that are adjacent (next to each other) that add up to 10, otherwise return false
.
Create a method noDups(nums)
returns true
if there are no repeated (duplicate) items in the array nums
. It should return false if it does find a repeated element using nested loops.
6.4.5. Rotating Array Elements¶
Rotating an array means shifting all the elements in the array to the right or left by one position. For example, if the array is {6, 2, 5, 3}, rotating it to the right would give {3, 6, 2, 5}. To rotate an array, we need to copy the last element to the first position and then copy all the other elements to the next position. We can use a temporary variable to store the last element before overwriting it. If you do not want to change the original array, you can return a new array by copying in the rotated elements.
The following program segment is a method that should return an integer array that is rotated to the right – so {6, 2, 5, 3} returns {3, 6, 2, 5} (the parameter). Note that the method return type is int[] which means it will return an int array. But, the blocks have been mixed up and include one extra block that is not needed in a correct solution. Drag the blocks from the left and put them in the correct order on the right. Click the Check button to check your solution.
We can also rotate in place without constructing another array. We can copy the last element to the first position and then copy all the other elements to the next position. We need to use an indexed loop to access the elements at different indices. When you pass an array to a method, you’re actually passing a reference to the array’s memory location. This means that any changes made to the array within the method will affect the original array.
The code below rotates array elements to the left in place without constructing another array. Try it in the Java visualizer with the CodeLens button. Can you change it to rotate the elements to the right instead? Hint: use a backwards loop.
6.4.6. Reversing an Array¶
Reversing an array is similar to rotating it. We can copy the first element to the last position, the second element to the second-to-last position, and so on. We can use a temporary variable to store the value of the element we are overwriting. We usually need an indexed loop to access the elements at different indices unless we use a temporary array to store the reversed elements. Note that arrays are passed as references to methods, so any changes made to the array within the method will affect the original array.
The following programs show how you can reverse an array in place by swapping elements. You can use a while loop or an indexed for loop to do this to swap items from the start and the end of the array. To swap two elements, you need to use a temp variable to store the value of the element you are overwriting. Imagine that you have a glass of milk and a glass of orange juice. How would you swap the contents of the two glasses without making a huge mess? You would need a third glass to hold the contents of one of the glasses while you pour the contents of the other glass into it. Then you can pour the contents of the third glass into the other glass. This is the same idea behind swapping elements in an array.

Figure 1: Swapping elements in an array¶
// Swapping 2 elements at index i and j
int temp = array[i]; // pour milk into temp cup
array[i] = array[j]; // pour orange juice into milk glass
array[j] = temp; // pour milk from temp into oj glass
The following method reverses an array in place using a while loop and a temp variable to swap the first and last items. But, the blocks have been mixed up and include two extra blocks that are not needed in a correct solution. Drag the blocks from the left and put them in the correct order on the right. Click the Check button to check your solution.
Create a method reverse
that reverses an array in place using a temp variable.
6.4.7. FRQ Practice¶
We encourage you to work in pairs or groups to tackle the following challenging FRQ problems and take them one step at a time. These will get easier with practice!