Max Chunks To Make Sorted
Question: Given an array arr
that is a permutation of [0, 1, ..., arr.length - 1],
we split the array into some number of "chunks" (partitions), and individually sort each chunk. After concatenating them, the result equals the sorted array.
What is the most number of chunks we could have made?
Example:
Input: arr = [4,3,2,1,0]
Output: 1
Explanation: If we split into two or more chunks, we cannot sort the array. For example, if we split to [4,3] and [2,1,0], this will result in [3,4,0,1,2] which is not sorted.
Input: arr = [1,0,2,3,4]
Output: 4
Explanation: If we split into two chunks, [1,0] and [2,3,4], we can sort the array. But we can also sort into four chunks, [1,0], [2], [3], and [4] and result in a sorted array.
A simple idea to solve this is to continuously keep track of the max value, starting from the beginning up until the current index. When the max value is the same as the current index, we can increment the number of chunks needed by 1.
A simplified form of this solution is as follows:
We’re done!