BinarySearch 0563 Split List

Problem statement

https://binarysearch.com/problems/Split-List/

Solution

Find cumulative max of prefixes and cumulative min of suffixes.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, nums):
        lft = list(accumulate(nums, max))
        rgh = list(accumulate(nums[::-1], min))[::-1]
        n = len(nums)
        for i in range(n - 1):
            if lft[i] < rgh[i + 1]: return True
        return False