4.5 Implementing Array Algorithms

1. Minimum and maximum

There are standard algorithms that use array traversals, and the first ones find a minimum or maximum value 4.5.A.1. The plan: start with the first element as the “best so far”, then compare every other element and replace the best when a new one beats it.

public static int findMax(int[] arr)
{
    int max = arr[0];
    for (int i = 1; i < arr.length; i++)
    {
        if (arr[i] > max)
        {
            max = arr[i];
        }
    }
    return max;
}

int[] depths = {-12, -4, -30, -7};
System.out.println(findMax(depths));

Output:

-4

Watch out: if max started at 0, this call would return 0, a value that is not even in the array. For a minimum, flip the comparison to <. To find the index of the max instead of the value, store maxIndex = 0 and compare arr[i] > arr[maxIndex].

2. Sum, average and count

To compute a sum, start at 0 and add every element. The average is the sum divided by the number of elements 4.5.A.1. To determine the number of elements having a particular property, start a counter at 0 and add 1 each time an element passes the test 4.5.A.1.

int[] goals = {2, 0, 3, 1, 4, 0, 1};

int sum = 0;
int count = 0;
for (int g : goals)
{
    sum += g;
    if (g >= 2)          // the property: 2 or more goals
    {
        count++;
    }
}
double average = (double) sum / goals.length;

System.out.println("Sum: " + sum);
System.out.println("Average: " + average);
System.out.println("Games with 2+ goals: " + count);
System.out.println("Integer division: " + sum / goals.length);

Output:

Sum: 11
Average: 1.5714285714285714
Games with 2+ goals: 3
Integer division: 1

Watch out: sum / goals.length with two int values is integer division. Cast one side to double first.

3. At least one, and all

To determine if at least one element has a property, return true as soon as you find one; only after checking every element can you return false 4.5.A.1. To determine if all elements have a property, return false as soon as one fails; only after the loop can you return true 4.5.A.1.

public static boolean anyFreezing(double[] temps)
{
    for (double t : temps)
    {
        if (t < 0)
        {
            return true;        // one is enough
        }
    }
    return false;               // checked them all, none found
}

public static boolean allPassing(int[] scores)
{
    for (int s : scores)
    {
        if (s < 60)
        {
            return false;       // one failure is enough
        }
    }
    return true;                // checked them all, none failed
}

double[] week = {3.5, 1.0, -2.0, 4.5};
int[] quiz = {75, 88, 59, 91};
System.out.println(anyFreezing(week));
System.out.println(allPassing(quiz));

Output:

true
false

Watch out: this version of allPassing is wrong, because it returns on the very first element:

public static boolean allPassingBroken(int[] scores)
{
    for (int s : scores)
    {
        if (s >= 60)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    return true;
}

int[] quiz = {75, 88, 59, 91};
System.out.println(allPassingBroken(quiz));

Output:

true

It looked only at 75 and stopped. The correct answer is false, because 59 fails.

4. Consecutive pairs and duplicates

To access all consecutive pairs of elements, look at arr[i] and arr[i + 1] 4.5.A.1. Because arr[i + 1] must be a valid index, the loop stops one early: i < arr.length - 1.

int[] steps = {4000, 6500, 6200, 9000, 12000};

for (int i = 0; i < steps.length - 1; i++)
{
    int change = steps[i + 1] - steps[i];
    System.out.println("Day " + i + " to day " + (i + 1) + ": " + change);
}

Output:

Day 0 to day 1: 2500
Day 1 to day 2: -300
Day 2 to day 3: 2800
Day 3 to day 4: 3000

With i < steps.length, the last pass would read steps[5] and throw an ArrayIndexOutOfBoundsException.

To determine the presence or absence of duplicate elements, compare each element with every element after it 4.5.A.1. The inner loop starts at i + 1, so no element is compared with itself and no pair is checked twice.

public static boolean hasDuplicate(String[] names)
{
    for (int i = 0; i < names.length; i++)
    {
        for (int j = i + 1; j < names.length; j++)
        {
            if (names[i].equals(names[j]))
            {
                return true;
            }
        }
    }
    return false;
}

String[] signUps = {"Ada", "Ben", "Cleo", "Ben"};
String[] team = {"Ada", "Ben", "Cleo"};
System.out.println(hasDuplicate(signUps));
System.out.println(hasDuplicate(team));

Output:

true
false

Watch out: if the inner loop started at j = 0, every name would be compared with itself and the method would always return true. Use equals, not ==, to compare String objects.

5. Shift and rotate

To shift elements left, every element moves to the index one lower and the first value is lost. To rotate left, you save that first value and put it in the empty last spot 4.5.A.1.

int[] queue = {10, 20, 30, 40, 50};

int first = queue[0];                       // save the value that falls off
for (int i = 0; i < queue.length - 1; i++)
{
    queue[i] = queue[i + 1];                // move each element one place left
}
queue[queue.length - 1] = first;            // rotate: wrap it around

for (int q : queue)
{
    System.out.print(q + " ");
}
System.out.println();

Output:

20 30 40 50 10 

index	0	1	2	3	4
before	10	20	30	40	50
after shift left (last spot not set yet)	20	30	40	50	50
after rotate left	20	30	40	50	10

A plain shift left stops after the loop; the last spot usually gets a filler value such as 0.

To shift or rotate right, the loop must run backward, from the end toward index 1. Otherwise each value overwrites the next one before it is moved.

int[] queue = {10, 20, 30, 40, 50};

int last = queue[queue.length - 1];
for (int i = queue.length - 1; i > 0; i--)
{
    queue[i] = queue[i - 1];
}
queue[0] = last;

for (int q : queue)
{
    System.out.print(q + " ");
}
System.out.println();

Output:

50 10 20 30 40 

Watch out: a forward loop for a right shift copies the first value everywhere:

int[] queue = {10, 20, 30, 40, 50};
for (int i = 1; i < queue.length; i++)
{
    queue[i] = queue[i - 1];
}
for (int q : queue)
{
    System.out.print(q + " ");
}
System.out.println();

Output:

10 10 10 10 10 

6. Reverse

To reverse the order of the elements in place, swap the first and last, then the second and second-to-last, and so on until the middle 4.5.A.1. The mirror of index i is arr.length - 1 - i. A swap needs a temporary variable.

String[] podium = {"gold", "silver", "bronze", "fourth", "fifth"};

for (int i = 0; i < podium.length / 2; i++)
{
    String temp = podium[i];
    podium[i] = podium[podium.length - 1 - i];
    podium[podium.length - 1 - i] = temp;
}
for (String p : podium)
{
    System.out.print(p + " ");
}
System.out.println();

Output:

fifth fourth bronze silver gold 

index	0	1	2	3	4
before	“gold”	“silver”	“bronze”	“fourth”	“fifth”
after i = 0 (swap 0 and 4)	“fifth”	“silver”	“bronze”	“fourth”	“gold”
after i = 1 (swap 1 and 3)	“fifth”	“fourth”	“bronze”	“silver”	“gold”

The loop stops when i reaches 5 / 2, which is 2; the middle element stays put. If the loop ran to podium.length, it would swap every pair a second time and put the array back in its original order.

A second way is to build a new array, filling it from the back of the original:

int[] laps = {61, 59, 64, 58};
int[] reversed = new int[laps.length];
for (int i = 0; i < laps.length; i++)
{
    reversed[laps.length - 1 - i] = laps[i];
}
for (int lap : reversed)
{
    System.out.print(lap + " ");
}
System.out.println();

Output:

58 64 59 61