4.5 - Implementing Array Algorithms

There’s a set of standard algorithm patterns that show up constantly with arrays:

Finding a minimum or maximum

Computing a sum or average

Checking if at least one element has some property

Checking if all elements have some property

Counting how many elements have some property

Looking at every pair of consecutive elements

Checking for duplicates

Shifting or rotating elements left or right

Reversing the order of elements


int[] nums = {4, 8, 15, 16, 23};

// minimum
int min = nums[0];
for (int n : nums) {
    if (n < min) min = n;
}

// checking if at least one element meets a condition
boolean hasEven = false;
for (int n : nums) {
    if (n % 2 == 0) {
        hasEven = true;
    }
}

// checking if all elements meet a condition
boolean allPositive = true;
for (int n : nums) {
    if (n <= 0) {
        allPositive = false;
    }
}

// counting elements with a property
int countOver10 = 0;
for (int n : nums) {
    if (n > 10) {
        countOver10++;
    }
}

// checking consecutive pairs
for (int i = 0; i < nums.length - 1; i++) {
    System.out.println(nums[i] + " and " + nums[i + 1]);
}

// reversing an array
int[] reversed = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
    reversed[i] = nums[nums.length - 1 - i];
}

Here are the rest of the patterns, written out.

Sum and average: add every element to a running total. For the average, cast to double before dividing, or Java does integer division and chops off the decimal (66 / 5 would give 13).


int[] nums = {4, 8, 15, 16, 23};
int sum = 0;
for (int n : nums) {
    sum += n;
}
double avg = (double) sum / nums.length;
System.out.println(sum); // 66
System.out.println(avg); // 13.2

Maximum: same idea as the minimum. Start with the first element, not 0. If every value were negative, starting at 0 would give an answer that isn’t even in the array.


int[] temps = {-5, -2, -9};
int max = temps[0];
for (int t : temps) {
    if (t > max) {
        max = t;
    }
}
System.out.println(max); // -2

At least one / all, as methods: inside a method, you can return as soon as you know the answer. Only return false after the loop has checked everything. A return false in an else inside the loop would quit after looking at just the first element.


public static boolean hasNegative(int[] arr) {
    for (int n : arr) {
        if (n < 0) {
            return true; // found one, no need to keep looking
        }
    }
    return false; // checked every element, none were negative
}

Consecutive pairs: compare each element with the one after it. Stop at length - 1 so that nums[i + 1] never goes past the end. This one counts how many times the temperature went up from one day to the next:


int[] temps = {70, 72, 71, 75, 78};
int increases = 0;
for (int i = 0; i < temps.length - 1; i++) {
    if (temps[i + 1] > temps[i]) {
        increases++;
    }
}
System.out.println(increases); // 3

Duplicates: compare every element with every element after it, using nested loops. Starting j at i + 1 checks each pair once and never compares an element with itself.


int[] nums = {3, 7, 1, 7, 2};
boolean hasDuplicate = false;
for (int i = 0; i < nums.length; i++) {
    for (int j = i + 1; j < nums.length; j++) {
        if (nums[i] == nums[j]) {
            hasDuplicate = true;
        }
    }
}
System.out.println(hasDuplicate); // true, 7 shows up twice

Shifting and rotating: in a left shift, every element moves one spot left. In a plain shift, the first value is lost and the empty spot at the end gets filled with something like 0. In a rotation, the first value wraps around to the end instead, so save it before the loop overwrites it.


// rotate left
int[] nums = {4, 8, 15, 16, 23};
int first = nums[0];               // save the value that wraps around
for (int i = 0; i < nums.length - 1; i++) {
    nums[i] = nums[i + 1];         // move each value one spot left
}
nums[nums.length - 1] = first;     // nums is now {8, 15, 16, 23, 4}

To rotate right, loop backward. If you went forward, nums[1] would get the 4, then nums[2] would copy that same 4, and you’d end up with {23, 4, 4, 4, 4}.


// rotate right
int[] nums = {4, 8, 15, 16, 23};
int last = nums[nums.length - 1];
for (int i = nums.length - 1; i > 0; i--) {
    nums[i] = nums[i - 1];         // move each value one spot right
}
nums[0] = last;                    // nums is now {23, 4, 8, 15, 16}

Reversing in place: the example above builds a reversed copy. To reverse the original array, swap the first and last elements, then the second and second to last, and so on. Only go halfway (nums.length / 2). If the loop ran all the way through, every pair would get swapped twice and the array would end up right back where it started.


int[] nums = {4, 8, 15, 16, 23};
for (int i = 0; i < nums.length / 2; i++) {
    int temp = nums[i];
    nums[i] = nums[nums.length - 1 - i];
    nums[nums.length - 1 - i] = temp;
}
// nums is now {23, 16, 15, 8, 4}

Back Next