Problem statement

https://leetcode.com/problems/max-chunks-to-make-sorted-ii/

Solution 1

Let us note, that we need to find all places, where sorted(arr[:i]) == sorted(arr)[:i]: permutation of first i elements should be equal to first i elements in sorted array.

Complexity

It can be written as one line, but time complexity is O(n^2 log n), space complexity is O(n).

Code

class Solution:
    def maxChunksToSorted(self, arr):
        return sum(sorted(arr[:i]) == sorted(arr)[:i] for i in range(len(arr)))

Solution 2

We can improve the previous idea, but now, instead of sorting elements each time, we keep counter of them (numbers can be equal), and keep in dictionary difference of frequencies for each element. Also if some element becomes equal to 0, we delete it from dictionary and we check size of dictionary each step.

Complexity

Time complexity is O(n log n), space complexity is O(n).

Code

class Solution:
    def maxChunksToSorted(self, arr):
        brr, n, d, ans = sorted(arr), len(arr), defaultdict(int), 0

        for i in range(n):
            if len(d) == 0: ans += 1
            d[arr[i]] += 1
            d[brr[i]] -= 1
            if d[arr[i]] == 0: d.pop(arr[i])
            if d[brr[i]] == 0: d.pop(brr[i])

Solution 3

Finally, there is even O(n) time complexity algorithm! We iterate through the array and if we see the point, where all elements to the right bigger or equal than all elements to the left, we have new chunk. It can be efficiently written with accumulate function in python.

Complexity

It is O(n) for time and space.

Code

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