Find the maximum and minimum element in an array

The problem, simply

You get an array of numbers. Give back the smallest one and the biggest one.

Every way must look at every number, so every way is O(n). The interview question hiding inside is: how few comparisons can you use? The plain way uses about 2n. The pair trick uses about 1.5n.

A story to remember it

Picture it

Examples

Way 1: the simple way

Walk once, checking each number against both cards.

1. min = max = arr[0].
2. For each other number: if it is bigger than max, it is the new max. If it is smaller than min, it is the new min.

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

How long it takes: O(n), with 2(n - 1) comparisons in the worst case. Extra room: O(1).

Way 2: the clever way

Take the numbers two at a time.

1. If the count is even, compare the first two: the smaller is min, the bigger is max. Start the pairs at index 2. If the count is odd, min = max = arr[0] and start the pairs at index 1.
2. For each pair (x, y): compare x with y (1 comparison). Compare the smaller with min and the bigger with max (2 comparisons).

class Solution {
    public int[] minMax(int[] arr) {
        int n = arr.length, min, max, i;
        if (n % 2 == 0) {                         // even: the first pair sets both
            min = Math.min(arr[0], arr[1]);
            max = Math.max(arr[0], arr[1]);
            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) { int t = small; small = big; big = t; } // 1 comparison
            if (small < min) min = small;          // the smaller only checks min
            if (big > max) max = big;              // the bigger only checks max
        }
        return new int[] { min, max };
    }
}

How long it takes: still O(n), but with about 3n / 2 - 2 comparisons instead of 2n - 2. Extra room: O(1). It has been proven that no method can do it with fewer comparisons.

Another way: a tournament

Split the array in half, find the min and max of each half, then combine with 2 comparisons. A piece of 2 numbers costs 1 comparison. This also gives about 3n / 2 - 2 comparisons, and it is a neat divide and conquer warm up.

class Solution {
    public int[] minMax(int[] arr) {
        return solve(arr, 0, arr.length - 1);
    }

    private int[] solve(int[] a, int lo, int hi) {
        if (lo == hi) return new int[] { a[lo], a[lo] };            // one number
        if (hi == lo + 1) {                                         // two numbers, 1 comparison
            return a[lo] < a[hi] ? new int[] { a[lo], a[hi] } : new int[] { a[hi], a[lo] };
        }
        int mid = lo + (hi - lo) / 2;
        int[] left = solve(a, lo, mid), right = solve(a, mid + 1, hi);
        return new int[] { Math.min(left[0], right[0]), Math.max(left[1], right[1]) };
    }
}

It takes O(n) time and O(log n) extra room for the waiting calls.

Watch out for

• An empty array has no min or max. Throw an error or return a special value, but do not read arr[0].
• In the pair loop, stop at i + 1 < n, so a leftover single number is never read past the end.
• Starting min at 0 is a classic bug: an all positive array then reports min 0.

What interviewers ask next

• What is the least possible number of comparisons? ceil(3n / 2) - 2. Every number except the final min must lose a "smaller" contest, and every number except the final max must lose a "bigger" contest. A comparison between two fresh numbers can create one loss of each kind, any other comparison creates at most one.
• Find the largest and the second largest with few comparisons? Run a knockout tournament: n - 1 comparisons find the max, and the second largest is among the log n numbers that lost directly to the max.
• Min and max of a rotated sorted array? Binary search for the rotation point in O(log n).
• Min of every window of size k? Use a deque that keeps candidates in increasing order: O(n) for all windows.

Remember this

Grown-up words: the cards are running minimum and maximum, the pair trick is pairwise comparison, and the tournament is a divide and conquer recursion whose comparison count meets the lower bound ceil(3n/2) - 2.