4.5 Implementing array algorithmsThe array algorithm toolbox
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));
- line 8 Cast before dividing, or 4 / 5 would be 0
- line 13 Start with a real element, never 0
- line 14 temps[0] is already counted, so start at 1
?Wait, why the (double) in the average?
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?
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}
- line 7 One odd value settles it: return right away
- line 10 true only after every value passed
- line 16 j starts after i, so each pair is checked once
- line 18 Strings: compare with equals, not ==
I thought about it. Show me
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
- line 4 Stop one early, because the body looks at i + 1
- line 6 Compare each element with the next one
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}
- line 3 Only half the length: each swap fixes two spots
- line 5-7 The three-line swap, using temp
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}
- line 3 Save the value that would be overwritten
- line 4-6 Go backward so every value moves before it is covered
I thought about it. Show me
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}
- line 3 Pairs: stop at length - 1
- line 5-7 One pair out of order is enough to say false
- line 10 Only after every pair passes
- 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. - 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. - After the loop, every pair passed: return true;
- 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
- Is this question about single elements or about neighbors?
- Which single pair would prove the array is not sorted?
- Where does return true go, inside the loop or after it?
int[] t = {-4, -9, -2, -7};
int best = 0;
for (int v : t)
{
if (v > best)
{
best = v;
}
}
System.out.println(best);- A0
- B-2
- C-9
- 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].

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.