4.5 Implementing Array Algorithms

4.5 Implementing Array Algorithms

Each coding exercise has its own folder. Open its .java file and press Run to try it. Run Tests checks every graded exercise in this lesson at once.

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 utilize array traversal that you should be familiar with for the AP CSA exam (AP 4.5.A.1):

• Compute a sum or average of array elements
• Determine the minimum or maximum value in an array
• 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
• Determine the number of elements having a particular property
• Access all consecutive pairs of elements
• Determine the presence or absence of duplicate elements
• Shift or rotate elements left or right
• Reverse the order of the elements

Accumulator Pattern for Sum/Average

As we have seen before with loops, 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:

1. Initialize the accumulator variable before the loop.
2. Loop through the values.
3. Update the accumulator variable inside the loop.
4. 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);

Check your understanding: The following program has the correct code to return the average of the first 3 items in the array a, but the code is mixed up. — answer it on CS Awesome: https://runestone.academy/ns/books/published/csawesome2/topic-4-5-array-algorithms.html#parsons_array_avg

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.

Exercise 1

Try the code that computes the average of the elements in the array. Can you add another method to compute the sum of the elements?

Open the 01-enhanced-for-loop-avg folder and edit ArrayWorker.java. Press Run to try it; Run Tests checks it (2 tests).

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] ....)
       ...
}

Check your understanding: The following method has the correct code to return the largest value in an integer array called vals (an instance variable of the current object), but the code is mixed up. — answer it on CS Awesome: https://runestone.academy/ns/books/published/csawesome2/topic-4-5-array-algorithms.html#parsons_for_each_largest

If you want to step through the correct code to see what it does in the Java Visualizer click on the following Java visualizer link.

Exercise 2

The code finds the minimum (smallest element) in an array. Try it in the Java visualizer. Can you change it to find the maximum element instead? Can you also compute the average of the elements?

Open the 02-minmax folder and edit MinMax.java. Press Run to try it; Run Tests checks it (3 tests).

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.

Exercise 3

Run the code. Does it find 7 in the array? Fix the early return error in the code.

Open the 03-early-return-error folder and edit FindError.java. Press Run to try it; Run Tests checks it (2 tests).

Check your understanding: 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;
}

Answer it on CS Awesome: https://runestone.academy/ns/books/published/csawesome2/topic-4-5-array-algorithms.html#mcq_array_error1

Check your understanding: 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 true?

boolean temp = false;
for (int val : array)
{
  temp = ( target == val );
}
return temp;

Answer it on CS Awesome: https://runestone.academy/ns/books/published/csawesome2/topic-4-5-array-algorithms.html#mcq_array_error2

Looping From Back to Front

You don’t have to loop through an array from the front to the back. You can loop by starting at the back of the array and move toward the front during each time through the loop. In the example below, the method getIndexOfLastElementSmallerThanTarget returns the index of the last element in the array that is smaller than the given argument. The return statement inside the loop stops the execution of the loop and the method and returns the index that is found immediately back to the main method. It returns -1 if there is no number in the array that is smaller than the given number.

Exercise 4

What does the code print out? Notice that the array and the target are passed in as arguments to the getIndexOfLastElementSmallerThanTarget method. Trace through it keeping track of the array values and the output. Then run it to see if you’re right. You can also try the code in the Java visualizer. Can you add another method that finds the index of the last element greater than the target instead of smaller than the target and have main print out a test of it? Call this method getIndexOfLastElementGreaterThanTarget and give it 2 arguments and a return value like the method.

Open the 04-arrayFindSmaller folder and edit ArrayFindSmallest.java. Press Run to try it; Run Tests checks it (3 tests).

Check your understanding: Given the following code segment (which is identical to the method above) what will be returned when you execute: getIndexOfLastElementSmallerThanTarget(values,-13);

private int[ ] values = {-20, -15, 2, 8, 16, 33};

public static int getIndexOfLastElementSmallerThanTarget(int[ ] values, int compare)
{
   for (int i = values.length - 1; i >=0; i--)
   {
      if (values[i] < compare)
         return i;
   }
   return -1; // to show none found
}

Answer it on CS Awesome: https://runestone.academy/ns/books/published/csawesome2/topic-4-5-array-algorithms.html#mcq_array_loop1

Check your understanding: Given the following code segment (which is not quite identical to the method above) what will be returned when you execute: getIndexOfLastElementSmallerThanTarget(values, 7);

int[ ] values = {-20, -15, 2, 8, 16, 33};

public static int getIndexOfLastElementSmallerThanTarget(int[] values, int compare)
{
   for (int i = values.length; i >=0; i--)
   {
      if (values[i] < compare)
         return i;
   }
   return -1; // to show none found
}

Answer it on CS Awesome: https://runestone.academy/ns/books/published/csawesome2/topic-4-5-array-algorithms.html#mcq_array_loop2

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++;
    }
}

Check your understanding: 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. — answer it on CS Awesome: https://runestone.academy/ns/books/published/csawesome2/topic-4-5-array-algorithms.html#parsons-even-array

Exercise 5

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 %.

Open the 05-exAllOdd folder and edit Test1.java. Press Run to try it; Run Tests checks it (3 tests).

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;

Exercise 6

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.

Open the 06-sumPairs folder and edit Pairs.java. Press Run to try it; Run Tests checks it (2 tests).

Exercise 7

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.

Open the 07-noDups folder and edit Pairs.java. Press Run to try it; Run Tests checks it (2 tests).

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.

Check your understanding: 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). — answer it on CS Awesome: https://runestone.academy/ns/books/published/csawesome2/topic-4-5-array-algorithms.html#rotateRightParsons

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.

Exercise 8

The code rotates array elements to the left in place without constructing another array. Try it in the Java visualizer. Can you change it to rotate the elements to the right instead? Hint: use a backwards loop.

Open the 08-rotate folder and edit Rotate.java. Press Run to try it; Run Tests checks it (2 tests).

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. The first uses a while loop and the second an indexed for loop. 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.

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

Check your understanding: The following method reverses an array in place using an indexed for loop and a temp variable to swap the first and last items, but the code blocks are mixed up. — answer it on CS Awesome: https://runestone.academy/ns/books/published/csawesome2/topic-4-5-array-algorithms.html#parsons_array_reverse

Check your understanding: The following method reverses an array in place using a while loop and a temp variable to swap the first and last items. — answer it on CS Awesome: https://runestone.academy/ns/books/published/csawesome2/topic-4-5-array-algorithms.html#parsons_array_reverse2

Exercise 9

Create a method reverse that reverses an array in place using a temp variable.

Open the 09-reverseArrayCode folder and edit ReverseTest.java. Press Run to try it; Run Tests checks it (2 tests).

Review and FRQ Practice for Arrays

This lesson ends the section on 1-dimensional arrays. You can now do the following review lessons and FRQs at the end of the unit.

• Arrays Summary
• Arrays Toggle Code Practice
• Arrays Coding Practice
• More Arrays Coding Practice
• Arrays Multiple-Choice Exercises
• Arrays Exam

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! Note that the third FRQ now uses ArrayLists instead of arrays, but these FRQ practice probelms will still help you to practice iterating over a data structure and can be converted to work with ArrayLists.

• Horse Barn A FRQ
• Horse Barn B FRQ
• Self Divisor B FRQ
• Sound A FRQ
• Sound B FRQ
• Number Cube A FRQ
• Number Cube B FRQ