title: Finding array partition where max(left) < min(right) - possible in O(N) time?
body: <p>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.</p>
  
  <p>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.</p>
  
  <p>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:</p>
  
  <pre><code>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 &lt; minSummerTemp
              return i + 1
  </code></pre>