Python Solution - Monotonic queue O(N)
I see a lot of solutions that are using one of these two approaches\n1. Using prefix arrays (O(N))\n2. Using a sorted set (O(NlogN))\nI think there is a simpler
I see a lot of solutions that are using one of these two approaches\n1. Using prefix arrays (O(N))\n2. Using a sorted set (O(NlogN))\nI think there is a simpler approach, that can be solved with a monotonic queue(without any sorting)\nWe could store the entire array as sorted intervals. If we find any number that is lesser than any of these intervals, we would need to merge the intervals into one go. \nSimilar question - https://leetcode.com/problems/merge-intervals/\nHere is a run through\nExample\n[1,2,5,2,3,6,3]\ni = 0 S = [[1,1]]\ni = 1 S = [[1,1], [2,2]]\ni = 2 S = [[1,1], [2,2], [5,5]]\ni = 3 S = [[1,1], [2,2], [2, 5]]\ni = 4 S = [[1,1], [2,2], [2, 5]]\ni = 5 S = [[1,1], [2,2], [2, 5], [6,6]]\ni = 6 S = [[1,1], [2,2], [2, 6]]\n\n```\nclass Solution:\n    def maxChunksToSorted(self, arr: List[int]) -> int:\n        S = []\n        for a in arr:\n            min_i, max_i = a, a\n            while S and a < S[-1][1]:\n                start, end = S.pop()\n                min_i, max_i = min(start, min_i), max(end, max_i)\n            S.append([min_i, max_i])\n        return len(S)\n```
['Python', 'Python3']