Max Chunks To Make Sorted
01 · Problem
You are given an integer array arr of length n that is a permutation of the integers 0 through n - 1 (every value appears exactly once).
Cut arr into one or more contiguous, non-empty pieces ("chunks"). Then sort each chunk on its own and glue the chunks back together in their original order. The cut is valid if the glued result is the fully sorted array [0, 1, ..., n - 1].
Return the largest number of chunks a valid cut can produce. A single chunk (the whole array) is always valid, so the answer is at least 1.
02 · Examples
arr = [4,3,2,1,0]
1
0 is at the last index, so every proper prefix is missing 0 and can't sort into its final position; the whole array must be one chunk.
arr = [1,0,2,3,4]
4
Cut into [1,0], [2], [3], [4]. Sorting [1,0] gives [0,1], and the result is [0,1,2,3,4]. That is 4 chunks.
arr = [0,2,1,4,3]
3
Cut into [0], [2,1], [4,3]. Sorting each gives [0], [1,2], [3,4], which concatenate to the sorted array.
03 · Constraints
- 01n == arr.length
- 021 <= n <= 10
- 030 <= arr[i] < n
- 04All values of arr are distinct (arr is a permutation of 0..n-1)
04 · Optimal complexity
- Time
- O(n)
- Space
- O(1)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.