Maximum and minimum of an array using minimum number of comparisons

The problem, simply

You get a row of numbers. Give back the smallest one and the biggest one.

That part is easy. The twist is the counting: every time you ask "is this one bigger than that one?" costs one check, a comparison. Find both answers with as few checks as you can. The simple way needs about 2n checks. The clever way needs only about 1.5n.

A story to remember it

Picture it

Examples

Way 1: the simple way

Keep two notes: the smallest so far and the biggest so far. Start both at the first number. Then look at every other number and check it against both notes.

1. Set min = max = arr[0].
2. For each next number, check it against min, then check it against max.
3. At the end, the two notes are the answer.

class Solution {
    public int[] findMinMax(int[] arr) {
        int min = arr[0], max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] < min) min = arr[i];   // check 1
            if (arr[i] > max) max = arr[i];   // check 2
        }
        return new int[]{min, max};
    }
}

How long it takes: one walk over the row, O(n), and exactly 2(n - 1) checks. Extra room: two notes, O(1).

You can save a little by writing else if for the max check, because a new minimum can never be a new maximum. That helps on some inputs, but on a row that keeps going up it is still 2(n - 1) checks.

Way 2: the clever way

Take the numbers two at a time.

1. If the count is even, compare the first two. The smaller one is min, the bigger one is max. Start the pairs at index 2.
2. If the count is odd, set min = max = arr[0]. Start the pairs at index 1.
3. For each pair, compare the two numbers with each other first. Then check only the smaller one against min and only the bigger one against max.

Every pair costs 3 checks instead of 4. A number that lost the "who is bigger" fight can never be the maximum, so there is no reason to check it against max.

class Solution {
    public int[] findMinMax(int[] arr) {
        int n = arr.length;
        int min, max, i;
        if (n % 2 == 0) {                    // even: the first pair sets both notes
            if (arr[0] < arr[1]) { min = arr[0]; max = arr[1]; }
            else { min = arr[1]; max = arr[0]; }
            i = 2;
        } else {                             // odd: the first number is both
            min = max = arr[0];
            i = 1;
        }
        for (; i + 1 < n; i += 2) {
            int small = arr[i], big = arr[i + 1];
            if (small > big) { small = arr[i + 1]; big = arr[i]; }  // the pair fight
            if (small < min) min = small;    // only the small one tries for min
            if (big > max) max = big;        // only the big one tries for max
        }
        return new int[]{min, max};
    }
}

How long it takes: still one walk, O(n), but the number of checks drops to 3n/2 - 2 when n is even and 3(n - 1)/2 when n is odd. Extra room: O(1).

Watch out for

• Starting min at 0 or max at 0. With all negative numbers, a max of 0 is wrong. Start from a real number in the array.
• An empty array has no min or max. Ask the interviewer what to return, or throw an error.
• Integer.MAX_VALUE as the starting min works, but it costs an extra check on the first number. Starting from the array is cleaner.

What interviewers ask next

• Can you do better than 3n/2 - 2 checks? No. There are 2n - 2 facts to learn: every number except the min must lose once, and every number except the max must win once. A check between two untouched numbers teaches two facts, but there are only n/2 such checks, and every other check teaches at most one new fact.
• What about splitting the row in half, solving each half, and joining? That divide and conquer way also gives 3n/2 - 2 checks when n is a power of 2, but a few more for other sizes, and it uses O(log n) stack room.
• Find the second smallest number with few checks. Run a knockout tournament for the min (n - 1 checks). The second smallest must have lost directly to the winner, so check only those log n numbers.
• Why does this matter if both ways are O(n)? When a check is costly, like comparing long strings or asking a slow server, cutting a quarter of the checks is real savings.

Remember this

Grown-up words: a check is a comparison, calling kids up two at a time is the pairwise or tournament method, and the best possible count, ceil(3n/2) - 2, is the lower bound for finding both the minimum and the maximum.