AP Computer Science A · Unit 4 lecture · Part 4 of 14 · 12 min

4.5 Implementing array algorithmsThe array algorithm toolbox

Mr. Thompkins
Here's good news: the exam reuses a small set of patterns over and over. Sum, average, min and max, count, any and all, neighbors, duplicates, reverse, shift and rotate. Learn each one once, and you'll recognize it in any disguise.

Sum, average, minimum and maximum

1public static double average(int[] nums)2{3    int sum = 0;4    for (int n : nums)5    {6        sum += n;7    }8    return (double) sum / nums.length;19}1011public static int coldest(int[] temps)12{13    int low = temps[0];214    for (int i = 1; i < temps.length; i++)315    {16        if (temps[i] < low)17        {18            low = temps[i];19        }20    }21    return low;22}23// in main24int[] temps = {4, -2, 7, -6, 1};25System.out.println(average(temps) + " " + coldest(temps));
  1. line 8 Cast before dividing, or 4 / 5 would be 0
  2. line 13 Start with a real element, never 0
  3. line 14 temps[0] is already counted, so start at 1
output › 0.8 -6
Two of the most common methods on the exam.
?Wait, why the (double) in the average?
sum and nums.length are both ints, so sum / nums.length would be integer division: 4 / 5 is 0. Casting sum to double first makes the division keep its decimals: 4.0 / 5 is 0.8. The cast must happen before the division, not after.

For a minimum or maximum, start with a real element, usually arr[0], and compare the rest against it. Starting with 0 is the classic trap: if every temperature is below freezing, a maximum that starts at 0 reports 0, a value that isn't even in the array. If you'd rather start with a value no element can beat, use Integer.MIN_VALUE for a maximum or Integer.MAX_VALUE for a minimum.

Count, any and all

To count, keep a counter that starts at 0 and add 1 whenever an element meets the condition. To check whether at least one element meets it, return true as soon as you find one, and return false only after the loop. To check whether all elements meet it, flip that: return false as soon as one fails, and true only after the loop.

?Wait, what does % do again?
% gives the remainder after integer division. 7 % 2 is 1 and 8 % 2 is 0, so v % 2 == 0 means v is even and v % 2 != 0 means it's odd. It's the standard way to test divisibility.
1public static boolean allEven(int[] a)2{3    for (int v : a)4    {5        if (v % 2 != 0)6        {7            return false;18        }9    }10    return true;211}1213public static boolean hasRepeat(String[] w)14{15    for (int i = 0; i < w.length; i++)16    {317        for (int j = i + 1; j < w.length; j++)18        {419            if (w[i].equals(w[j]))20            {21                return true;22            }23        }24    }25    return false;26}
  1. line 7 One odd value settles it: return right away
  2. line 10 true only after every value passed
  3. line 16 j starts after i, so each pair is checked once
  4. line 18 Strings: compare with equals, not ==
output › allEven({2, 8, 4}) is true; hasRepeat({"oak", "elm", "fir", "elm"}) is true
An "all" check and a duplicate check. Both can stop early.
Pause and think
What goes wrong if allEven's loop body were: if (v % 2 != 0) { return false; } else { return true; }?
I thought about it. Show me
It would decide after the first element. Whatever a[0] is, the method returns right away, so allEven({2, 7}) would return true without ever looking at the 7. The return true belongs after the loop, when every element has passed.

Neighbors: consecutive pairs

Some questions are about pairs of neighbors: how many times does the value go up, are any two neighbors equal, what's the biggest jump? Use an index loop and compare a[i] with a[i + 1]. Because a[i + 1] must exist, the loop stops at length - 1.

1public static int rises(int[] h)2{3    int count = 0;4    for (int i = 0; i < h.length - 1; i++)15    {6        if (h[i + 1] > h[i])27        {8            count++;9        }10    }11    return count;12}13// rises(new int[] {3, 5, 5, 8, 2, 9}) returns 3
  1. line 4 Stop one early, because the body looks at i + 1
  2. line 6 Compare each element with the next one
output › 3
Counting rises: 3 to 5, 5 to 8 and 2 to 9.

Reverse, shift and rotate

To reverse an array in place, swap the first and last elements, then the second and second to last, and so on toward the middle. A swap always takes three lines and a temporary variable, because the moment you write a[i] = a[j], the old a[i] is gone unless you saved it.

1public static void reverse(int[] a)2{3    for (int i = 0; i < a.length / 2; i++)14    {5        int temp = a[i];26        a[i] = a[a.length - 1 - i];27        a[a.length - 1 - i] = temp;28    }9}
  1. line 3 Only half the length: each swap fixes two spots
  2. line 5-7 The three-line swap, using temp
output › {1, 2, 3, 4, 5} becomes {5, 4, 3, 2, 1}
Reverse by swapping pairs from the outside in.
1021324354i = 0: swap a[0] and a[4]i = 1: swap a[1] and a[3]the middle element stays put5 / 2 is 2 passes
Two swaps reverse five elements. The middle one never moves.

To shift or rotate, every element moves one spot. Rotating right moves each element one index higher and wraps the last element around to index 0. Save the last element first, then shift, going backward so that each value is copied before it gets covered.

1public static void rotateRight(int[] a)2{3    int last = a[a.length - 1];14    for (int i = a.length - 1; i > 0; i--)25    {26        a[i] = a[i - 1];27    }8    a[0] = last;9}
  1. line 3 Save the value that would be overwritten
  2. line 4-6 Go backward so every value moves before it is covered
output › {10, 20, 30, 40} becomes {40, 10, 20, 30}
Rotating right by one.
Pause and think
What would rotateRight produce on {10, 20, 30, 40} if the loop went forward, for (int i = 1; i < a.length; i++)?
I thought about it. Show me
{40, 10, 10, 10}. a[1] = a[0] copies 10 into index 1, then a[2] = a[1] copies that same 10 again, and so on. Each copy overwrites the value the next step needed. Going backward avoids that.
Write the method
Write isSorted(int[] a), which returns true when every element is less than or equal to the one after it, and false otherwise. An array with zero or one element counts as sorted.
1public static boolean isSorted(int[] a)2{3    for (int i = 0; i < a.length - 1; i++)14    {5        if (a[i] > a[i + 1])26        {7            return false;28        }9    }10    return true;311}
  1. line 3 Pairs: stop at length - 1
  2. line 5-7 One pair out of order is enough to say false
  3. line 10 Only after every pair passes
output › {2, 4, 4, 9}: true; {2, 5, 3}: false; {7}: true
  1. It's a neighbors question, so use an index loop over pairs: for (int i = 0; i < a.length - 1; i++).
    Why?
    The body will look at a[i + 1], so i must stop one early.
  2. It's an "all pairs" question, so look for one pair that breaks the rule: if (a[i] > a[i + 1]) { return false; }
    Why?
    Equal neighbors are allowed, so the problem is only a strictly bigger value before a smaller one.
  3. After the loop, every pair passed: return true;
  4. Check the edge cases: for {7} or an empty array, the loop body never runs and the method returns true, as required.

Answer: isSorted loops i from 0 to a.length - 2, returns false as soon as a[i] > a[i + 1], and returns true after the loop.

Stuck? Get a hint
  1. Is this question about single elements or about neighbors?
  2. Which single pair would prove the array is not sorted?
  3. Where does return true go, inside the loop or after it?
Check yourself
What is printed?
int[] t = {-4, -9, -2, -7};
int best = 0;
for (int v : t)
{
    if (v > best)
    {
        best = v;
    }
}
System.out.println(best);
  1. A0
  2. B-2
  3. C-9
  4. D-4
Show the answer

A. best starts at 0, and no element is greater than 0, so best never changes and the code prints 0. This is the max trap itself: the intended answer was -2, which you get by starting best at t[0].

Exam tip from Mr. T

Multiple-choice questions love these algorithms with one small change: <= for <, a loop that starts at 1, a return inside an else. Trace with a tiny array of three or four values that hits the edge, and you'll find the change fast.

  • Average: sum, then cast before dividing. Min and max: start at arr[0] (or Integer.MIN_VALUE / MAX_VALUE), never 0.
  • Any: return true when found, false after the loop. All: return false when one fails, true after the loop.
  • Neighbors: compare a[i] with a[i + 1] and stop at length - 1. Duplicates: nested loop with j starting at i + 1.
  • Swap with a temp variable. Reverse swaps pairs up to length / 2. Rotate right saves the last element and shifts backward.