Max Chunks To Make Sorted
Understanding the Problem
We have a permutation of [0, 1, 2, ..., n-1] and we want to split it into as many contiguous chunks as possible. Each chunk gets sorted independently, and after concatenating the sorted chunks, the entire array should be fully sorted (i.e., [0, 1, 2, ..., n-1]).
A chunk ending at index i is valid only if all elements in indices 0 through i are exactly the set {0, 1, ..., i}. No element in that chunk needs to go beyond index i, and no element beyond index i needs to come into this chunk.
Since the array is a permutation of [0, n-1], the sorted array is [0, 1, 2, ..., n-1], meaning each value v belongs at index v. A chunk boundary works at index i if and only if the maximum value seen so far equals i. If the max seen so far is bigger than i, some element still needs to be placed further right, so we cannot cut here.
Key Constraints:
1 <= n <= 10→ The input is tiny, so even O(n!) brute force would run in time (10! = 3.6 million). The structure of the problem still admits an O(n) solution, so that is what we build toward.0 <= arr[i] < n, all elements unique → The array is a permutation of[0, n-1]. This is the structural property the solutions depend on. Every value tells us exactly where it belongs in the sorted result, and the sorted result is always[0, 1, 2, ..., n-1].
Approach 1: Brute Force (Sort Prefix)
Intuition
For each possible prefix ending at index i, check whether sorting the prefix arr[0..i] gives [0, 1, ..., i]. If it does, we can close a chunk here, because everything in this prefix ends up in its correct position after sorting, independent of what comes after.
Since the array has at most 10 elements, copying and sorting a prefix at every index costs nothing in practice.
Algorithm
- Iterate through each index
ifrom 0 to n-1. - For each index, copy the subarray
arr[0..i]and sort it. - Check if the sorted copy equals
[0, 1, ..., i]. - If it matches, increment the chunk count.
- Return the total chunk count.
Visualization and Code
Loading animation...
- Time Complexity: O(n^2 log n). For each of the n indices, we copy and sort a prefix of up to n elements (O(n log n) per sort). With n at most 10, this is negligible.
- Space Complexity: O(n). We create a prefix array of up to n elements at each step.
The repeated sorting is the expensive part. We can check whether the prefix contains exactly {0, 1, ..., i} with a single arithmetic property instead.
Approach 2: Sum Check
Intuition
If the prefix arr[0..i] contains exactly the values {0, 1, ..., i}, then its sum equals 0 + 1 + ... + i = i * (i + 1) / 2. We can maintain a running sum and compare it against that expected value at each index.
The reason the sum alone is enough comes from the permutation structure. For a general array, two different sets of values can share a sum, so a sum match would not prove the set. Here the prefix at index i always holds exactly i+1 distinct values, all drawn from [0, n-1]. The only way i+1 distinct values from that range can add up to i*(i+1)/2 is if they are exactly {0, 1, ..., i}: swapping any value in {0, ..., i} for one outside it raises the sum, so no other combination reaches the target.
Algorithm
- Initialize
runningSum = 0andchunks = 0. - Iterate through each index
ifrom 0 to n-1. - Add
arr[i]torunningSum. - Compute the expected sum:
expectedSum = i * (i + 1) / 2. - If
runningSum == expectedSum, incrementchunks. - Return
chunks.
Visualization and Code
Loading animation...
- Time Complexity: O(n). Single pass through the array, constant work at each index.
- Space Complexity: O(1). Two integer variables hold the running sum and the chunk count.
The sum-based approach is optimal in time and space, but its correctness depends on the arithmetic identity above. The next approach reaches the same boundaries with a condition that is easier to reason about: the running maximum.
Approach 3: Running Maximum (Optimal)
Intuition
Since the sorted array is [0, 1, 2, ..., n-1], value v must end up at index v. A chunk ending at index i is valid when every element in the chunk sorts into its correct position without crossing the boundary.
If the maximum value in the prefix arr[0..i] is i, then no element in the prefix needs to go beyond index i, since the largest value is i and it belongs at index i. Because the array is a permutation, a max of i also forces the prefix to contain every value from 0 to i: there are i+1 distinct values, all in range [0, i], so they are exactly {0, 1, ..., i}.
The rule reduces to tracking the running maximum. Whenever max == i, index i is a valid chunk boundary.
The rule rests on two facts about permutations of [0, n-1]:
First, if the maximum value in arr[0..i] is i, the prefix holds i+1 distinct values in range [0, i], so they are exactly {0, 1, ..., i}. No value outside this set could fit (it would exceed i, contradicting the max), and none could be missing (there are exactly i+1 slots for i+1 distinct values in range [0, i]).
Second, if the max exceeds i, some value in the prefix belongs at an index beyond i, so the chunk cannot close yet. The boundary must extend until the index catches up with the max.
Algorithm
- Initialize
maxSoFar = 0andchunks = 0. - Iterate through each index
ifrom 0 to n-1. - Update
maxSoFar = max(maxSoFar, arr[i]). - If
maxSoFar == i, incrementchunks. - Return
chunks.
Visualization and Code
Loading animation...
- Time Complexity: O(n). Single pass through the array. At each index, we do O(1) work (one comparison, one max update).
- Space Complexity: O(1). Two integer variables hold the running maximum and the chunk count.