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

Here is the C++ code for O(n) Time and O(1) Space Complexity.

int solution(vector<int> &A) {

        int leftMax = A[0];     //  Max temperature during winter
        int maximum = A[0];     //  Max temperature during the year
        int position = 1;       //  Possible solution

        int n = A.size();

        for(int i = 1; i < n; i++) {
            if (A[i] < leftMax) {
                position = i+1;      // got a new lower value
                leftMax = maximum;
            } else if (A[i] > maximum) {
                maximum = A[i];
            }
        }        
        return position;
    }

The approach mentioned in the question for computing min(temps[i+1], ... temps[n]) is inefficient because many similar comparisons are made for different i values.

Instead, all the "min" values can be obtained by performing a single pass through the array, but by iterating from right to left.

Thus, it would be necessary to perform an initial pass from right to left which would store the minimum reached so far in an auxiliary array. Afterwards, you can use the same loop over i from the current solution, but the inner loop over j would be replaced by simply retrieving the "min" from the auxiliary array just computed.

This solution has O(n) complexity.

Yes, the O(n) solution is possible but with additional memory.

Let's fill the array minR where minR[i] = min(A[i], ..., A[n]).

The values of this array can be computed in O(n). We just iterate through the initial array in reverse order and calculate the minimum value among last array elements:

minR[n-1] = a[n-1]
for i from n-2 downto 0 
    minR[i] = min(minR[i+1], A[i])

Then all you need is to iterate through the array calculating the maximum value among first i array elements and comparing this value with minR[i+1]:

maxL = 0
for i from 0 to n-2
    maxL = max(maxL, A[i])
    if maxL < minR[i+1] then 
        outputResult(i)