BinarySearch 0816 List Partitioning with Inequality Relation

Problem statement

https://binarysearch.com/problems/List-Partitioning-with-Inequality-Relation/

Solution

Equal to Leetcode 0915 Partition Array into Disjoint Intervals.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(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