DSA problem
Max Chunks To Make Sorted
You are given an integer array arr of length n that is a permutation of the integers [0, 1, ..., n - 1]. Split arr into some number of contiguous chunks, sort each chunk individually, and concatenate the sorted chunks. Return the largest number of chunks that could form a fully sorted arr after this operation.
Because arr is a permutation of [0, 1, ..., n - 1], a contiguous prefix of length k can be sorted to occupy positions [0, k - 1] if and only if that prefix contains exactly the values {0, 1, ..., k - 1}. Equivalently, the maximum of the prefix is exactly k - 1. So we can split right before index k whenever the running max of arr[0..k-1] equals k - 1.
This produces a wonderfully short algorithm: iterate left-to-right tracking the running maximum, and increment a counter every time the running max equals the current index. The final counter is the answer. This is O(n) time, O(1) space.
There is also a monotonic-stack interpretation: each chunk's representative value is its maximum. As we scan left-to-right, we maintain a stack of chunk maxes. Whenever the new value is less than the top, we merge all chunks back that are greater than the new value (popping and keeping the largest popped max as the merged max). The stack's final size equals the answer. Both views give the same result.
Examples
arr = [4,3,2,1,0]1arr = [1,0,2,3,4]4arr = [0,1,2,3,4]5Constraints
- n == arr.length
- 1 <= n <= 10
- 0 <= arr[i] < n
- All the elements of arr are unique.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.