Max Chunks To Make Sorted II LeetCode solution in Python

1
# Runtime: 187 ms (Top 16.67%) | Memory: 14.5 MB (Top 12.03%)
2
class Solution:
3
    def maxChunksToSorted(self, arr: List[int]) -> int:
4
        sortedArr = sorted(arr)
5

6
        posMap = defaultdict(list)
7
        for i in range(len(sortedArr)):
8
            posMap[sortedArr[i]].append(i)  # keep track the right sortedArr[i] position
9

10
        idx = len(arr) - 1
11
        cnt = 0
12
        for i in range(len(arr) - 1, -1, -1):
13
            idx = min(
14
                idx, posMap[arr[i]][-1]
15
            )  # the smallest position need to move arr[i] to correct position
16
            posMap[arr[i]].pop()
17
            if i == idx:
18
                cnt += 1
19
                idx -= 1
20
        return cnt