BinarySearch 0651 Partition Lists to Make Sorted List

Problem statement

https://binarysearch.com/problems/Partition-Lists-to-Make-Sorted-List/

Solution

Equal to Leetcode 0768 Max Chunks To Make Sorted II.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, arr):
        left_max = list(accumulate(arr, max))[:-1]
        right_min = list(accumulate(arr[::-1], min))[::-1][1:]
        return sum(i <= j for i,j in zip(left_max, right_min)) + 1