4.5 Implementing Array Algorithms

What you need to know

• Named algorithms: find min/max; compute sum/average; count elements meeting a condition; determine if any/all elements satisfy a condition; find the mode (most frequent); check for duplicates; reverse the array; shift or rotate elements; check whether an array is sorted; find consecutive pairs.
• Any/all: "any" loops and returns true at the first match, false after the loop. "All" returns false at the first failure, true after.
• Reverse in place: swap arr[i] with arr[arr.length - 1 - i] for i from 0 to length/2.
• Shift left by one: arr[i] = arr[i + 1] for i from 0 to length − 2, then handle the last element. Direction of the loop matters to avoid overwriting.
• Consecutive elements: compare arr[i] and arr[i + 1] with the loop ending at length - 1 (not length).
• Duplicates: nested loop comparing each pair (i, j with j > i).

Worked example

// are all elements positive?
public static boolean allPositive(int[] a)
{
    for (int x : a)
    {
        if (x <= 0) return false;
    }
    return true;
}

// count adjacent equal pairs
int pairs = 0;
for (int i = 0; i < a.length - 1; i++)
{
    if (a[i] == a[i + 1]) pairs++;
}

// reverse in place
for (int i = 0; i < a.length / 2; i++)
{
    int tmp = a[i];
    a[i] = a[a.length - 1 - i];
    a[a.length - 1 - i] = tmp;
}

Going deeper

The nuance, edge cases, and connections that turn a 3 into a 5.

• The CED's named array algorithms: min/max, sum/average, count with property, any/all with property, mode (most frequent), duplicates present?, reverse, shift elements left/right, rotate, is-sorted?, consecutive pairs with property. Each has a canonical shape.
• Any: loop, return true at first match, return false after. All: loop, return false at first failure, return true after. The two returns are opposites of each other. "None" is !any.
• Mode: for each element, count how many times it appears (nested loop or a count array if values are in a known range); track the element with the highest count.
• Duplicates: nested loops i, j with j > i; if arr[i] == arr[j], duplicate found. Or sort first and check neighbors.
• Reverse in place: swap positions i and length−1−i for i from 0 to length/2 (exclusive). Going to length would swap everything back.
• Shift left by one: for (i = 0; i < length - 1; i++) arr[i] = arr[i + 1]; then set the last element (to 0, or to the saved first element for a rotation). Shift right: loop backward from length−1 down to 1: arr[i] = arr[i - 1]. Direction matters: going forward while shifting right overwrites before copying.
• Is sorted: for i from 0 to length−2, if arr[i] > arr[i + 1], return false. Return true after.
• Consecutive pairs: any comparison of arr[i] with arr[i + 1] loops i to length - 2 (i.e., i < length - 1).
• Building a new array: when the result size differs from the input, first count how many elements qualify, then create an array of that size, then fill it with a separate index.

Mistakes that cost points

• Any/all with an else-return inside the loop. Exits on the first element. Only one return in the loop.
• Reversing with a full-length loop. Swaps everything twice. Stop at length/2.
• Shifting right with a forward loop. Copies the first element into every position. Go backward.
• Neighbor comparison to length. arr[i + 1] throws on the last i. Stop at length − 1.

Practice questions

Written in the style of the real exam. Try each one before revealing the answer.

public static int count(int[] a)
{
    int c = 0;
    for (int i = 1; i < a.length; i++)
    {
        if (a[i] == a[i - 1]) c++;
    }
    return c;
}

public static boolean hasNeg(int[] arr)
{
    for (int x : arr)
    {
        if (x < 0) return true;
        else return false;
    }
    return false;
}