Max Chunks To Make Sorted
Problem
Given a permutation of 0..n-1, partition the array into the maximum number of chunks so that sorting chunks and concatenating gives the sorted array.
arr=[1,0,2,3,4]4def maxChunksToSorted(arr):
ans = 0
mx = 0
for i, x in enumerate(arr):
mx = max(mx, x)
if mx == i:
ans += 1
return ansfunction maxChunksToSorted(arr) {
let ans = 0, mx = 0;
for (let i = 0; i < arr.length; i++) {
mx = Math.max(mx, arr[i]);
if (mx === i) ans++;
}
return ans;
}int maxChunksToSorted(int[] arr) {
int ans = 0, mx = 0;
for (int i = 0; i < arr.length; i++) {
mx = Math.max(mx, arr[i]);
if (mx == i) ans++;
}
return ans;
}int maxChunksToSorted(vector<int>& arr) {
int ans = 0, mx = 0;
for (int i = 0; i < (int)arr.size(); i++) {
mx = max(mx, arr[i]);
if (mx == i) ans++;
}
return ans;
}Explanation
The array is a permutation of 0..n-1, so in the sorted version each index i should hold the value i. The key insight: we can cut a chunk at index i exactly when every value seen so far fits inside positions 0..i.
To detect that, we track the running max mx of the values seen up to i. Whenever mx == i, all values from the start are no larger than i, so nothing from the left needs to move past this point — we can close a chunk.
Each time that condition holds we add one to the answer. We never close more chunks than possible, so this greedy count gives the maximum.
If mx > i, some value belongs further right, so the current chunk must keep growing.
Example: [1, 0, 2, 3, 4]. At i=0, mx=1 > 0 (keep going); at i=1, mx=1 == 1 (first chunk [1,0]). Then 2, 3, 4 each close instantly, giving 4 chunks.