Max Chunks To Make Sorted II
Description
You are given an integer array arr. We split arr into some number of chunks and individually sort each chunk. After concatenating them, the result should equal the sorted array. Return the largest number of chunks we can make.
Examples
arr = [5,4,3,2,1]1Cannot split; whole array is one chunk.
arr = [1,1,1,1]4Since all elements are identical, splitting at any position is valid. Each individual element forms a valid chunk because sorting identical elements produces no change. The maximum number of chunks equals the array length: 4.
arr = [1,4,0,2,3,5]2The array splits into chunks [1,4,0,2,3] and [5]. The first chunk contains elements {0,1,2,3,4} which when sorted gives [0,1,2,3,4], and the second chunk [5] stays [5]. Together they form the fully sorted array. The maximum number of chunks is 2.
Constraints
- •
1 ≤ arr.length ≤ 2000 - •
0 ≤ arr[i] ≤ 10^8
Ready to solve this problem?
Practice solo and sharpen your skills for technical interviews.