Problem statement

https://leetcode.com/problems/partition-array-into-disjoint-intervals/

Solution

Let us look more carefully at the phrase: every element in left is less than or equal to every element in right. Actually it means that maximum of the left part is less or equal than minimum of the right part. So, let us calculate the following arrays:

  1. t1 is accumulate maximum, starting from the left side.
  2. t2 is accumulate minimum, starting from the right side.
  3. Iterate throught these two arrays and find the first i, where t1[i-1] <= t2[i]: it will mean that we found exaclty the correct place.

Complexity

Time complexity is O(n), space complexity is O(n) as well.

Code

class Solution:
    def partitionDisjoint(self, A):
        t1 = list(accumulate(A, max)) 
        t2 = list(accumulate(A[::-1], min))[::-1]
        for i in range(1, len(A)):
            if t1[i-1] <= t2[i]: return i