Finding array partition where max(left) < min(right) - possible in O(N) time?

Question

I've just tried a coding challenge to write a function that returns the length of the shortest possible left partition of an array of numbers, all of whose elements are less than all of the elements in the corresponding right partition.

The scenario given was finding the divide between "winter" and "summer" given a variable number of monthly temperature readings, with the rule that all winter temperatures are lower than all summer temperatures. We can assume that there is at least one correct partition, and the goal is to get the shortest winter.

Is it possible to do this in O(N) time, i.e. the processing time increases linearly with the number of temperature readings? The fastest solution I can come up with has to find the minimum summer temperature (lowest number in the right partition) for every maximum winter temperature considered:

function shortestWinterLength temps
    maxWinterTemp = -Infinity

    for i from 0 til temps.length
        minSummerTemp = Infinity

        for j from i + 1 til temps.length
            minSummerTemp = Math.min minSummerTemp, temps[j]

        maxWinterTemp = Math.max maxWinterTemp, temps[i]

        if maxWinterTemp < minSummerTemp
            return i + 1

Answer 1

Here I'm sharing my two solutions (in Java) for this Codility problem of "Winter Summer". I used the second one and scored 100%:

/**
 * Time Complexity: O(n) Space Complexity: O(n)
 * <p>
 * This version uses an auxiliary array to calculate all the possible summer mins.It is good enough but it is not so memory-efficient and that might be crucial as the size of the input size increases, so I went ahead and tried an in-place solution, which is the one I am exhibiting as "the" solution at {@link
 * #shortestWinterLengthOnePass(int[])} (see below)
 */
private static int shortestWinterLengthAuxArray(int[] temperatures) {
    int n = temperatures.length;

    if (n <= 1) {
        return n;
    }
    int[] summerMin = calculateAllPossibleMinimums(temperatures);

    int winterMax = Integer.MIN_VALUE;
    for (int i = 0; i < n - 1; i++) {
        winterMax = Math.max(temperatures[i], winterMax);

        if (winterMax < summerMin[i + 1]) {
            return i + 1;
        }
    }
    return n;
}

/**
 * Dynamic Programming: calculate all possible minimums from every position, in order to avoid double iterations on
 * the main algorithm, avoiding a time complexity of O(n^2).
 *
 * @param temperatures the array of temperatures to scan
 *
 * @return an array that, on its "i" position, will hold the minimums from temperatures[i]...temperatures[n-1]
 */
private static int[] calculateAllPossibleMinimums(int[] temperatures) {
    int n = temperatures.length;
    int[] summerMin = new int[n]; // auxiliary array. position "i" will hold the minimums from i...n-1
    summerMin[n - 1] = temperatures[n - 1];

    for (int i = n - 2; i >= 0; i--) {
        summerMin[i] = Math.min(temperatures[i], summerMin[i + 1]);
    }
    return summerMin;
}

And now, my preferred solution:

/**
 * This is my second stab at the problem, that iterates the input array only once. It has:
 * <p>
 * Time Complexity: O(n) Space Complexity: O(1)
 */
private static int shortestWinterLengthOnePass(int[] temperatures) {
    int n = temperatures.length;

    if (n == 0) {
        return 0;
    }
    int winterHighest = temperatures[0];
    int currentOverallHighest = temperatures[0];
    int winterLength = n;

    // Establish the max temperature in the winter partition so that winterHighest < "the lowest of summer"
    for (int i = 0; i < n; i++) {
        int current = temperatures[i];

        if (current <= winterHighest) {
            // found something lower than our current highest, it must be included in the "winter" (left) partition
            winterHighest = currentOverallHighest;
            winterLength = i + 1;   // keep track of the (last) position where the above realization happened
        } else if (current > currentOverallHighest) {
            currentOverallHighest = current;
        }
    }
    return winterLength;
}