Statement
Given an integer array arr of length n that contains a permutation of the values from 0 to n−1, split arr into the maximum number of contiguous chunks.
After splitting, sort each chunk individually and then concatenate the sorted chunks in their original order. Return the largest possible number of chunks such that the final concatenated array is fully sorted in nondecreasing order.
Constraints:
Examples
Sample Example 1
Input: arr = [1, 0, 2, 3, 4]-List[int]
Output: 4-int
Explanation: Splitting into chunks [1,0] | [2] | [3] | [4] and sorting each gives [0,1] | [2] | [3] | [4], whose concatenation [0,1,2,3,4] is sorted. You can’t make more than 4 chunks because the first two elements are “crossed” and must stay together.
Sample Example 2
Input: arr = [4, 3, 2, 1, 0]-List[int]
Output: 1-int
Explanation: Any split into multiple chunks fails because early chunks would contain large values that belong at the end. The only valid option is one chunk, [4,3,2,1,0], which sorts to [0,1,2,3,4].
Sample Example 3
Input: arr = [0, 1, 2, 3, 4]-List[int]
Output: 5-int
Explanation: The array is already sorted, so every element can be its own chunk: [0] | [1] | [2] | [3] | [4]. Sorting each chunk changes nothing, and the concatenation stays sorted.
Sample Example 4
Input: arr = [2, 0, 1, 3, 4]-List[int]
Output: 3-int
Explanation: Splitting into chunks [2,0,1] | [3] | [4] and sorting gives [0,1,2] | [3] | [4], whose concatenation is sorted. You cannot split the first three elements further (e.g., [2] | [0,1]) because sorting would produce [2,0,1,...], which is not sorted.
Sample Example 5
Input: arr = [1, 2, 0, 3]-List[int]
Output: 2-int
Explanation: Splitting into chunks [1,2,0] | [3] and sorting gives [0,1,2] | [3], i.e., [0,1,2,3], which is sorted. No 3-chunk split works because 0 must be grouped with 1 and 2 to move ahead of them after sorting.
Understand the problem
Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem: