Max Chunks To Make Sorted
MedPrompt
You are given an integer array arr of length n that represents a permutation of the integers in the range [0, n - 1].
We split arr into some number of chunks (i.e., partitions), and individually sort each chunk. After concatenating them, the result should equal the sorted array.
Return the largest number of chunks we can make to sort the array.
Example 1:
Input: arr = [4,3,2,1,0]
Output: 1
Explanation:
Splitting into two or more chunks will not return the required result.
For example, splitting into [4, 3], [2, 1, 0] will result in [3, 4, 0, 1, 2], which isn't sorted.Example 2:
Input: arr = [1,0,2,3,4]
Output: 4
Explanation:
We can split into two chunks, such as [1, 0], [2, 3, 4].
However, splitting into [1, 0], [2], [3], [4] is the highest number of chunks possible.
Constraints:
n == arr.length1 <= n <= 100 <= arr[i] < n- All the elements of
arrare unique.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach iterates through the array to find the end of each chunk. We greedily try to make each chunk as small as possible to maximize the total number of chunks. Starting from the beginning of the current segment, we expand the potential chunk one element at a time. At each step, we check if the current subarray forms a "valid" chunk. A chunk is valid if the set of its elements corresponds exactly to the set of its indices in the final sorted array.
Algorithm
- Initialize
chunks = 0and the starting index of the current segmenti = 0. - Loop while
i < n:- Initialize
current_sum = 0andexpected_sum = 0. - Start an inner loop with
jfromiton-1.- Add
arr[j]tocurrent_sum. - Add
jtoexpected_sum. - If
current_sumequalsexpected_sum, a valid chunk boundary is found atj.- Increment
chunks. - Update
itoj + 1to start searching for the next chunk. - Break the inner loop.
- Increment
- Add
- Initialize
- Return
chunks.
Walkthrough
We can define a chunk starting at index i. We then search for the smallest ending index j >= i such that the subarray arr[i...j] is a permutation of the numbers {i, i+1, ..., j}. To check this condition efficiently, we can use the property that since all numbers are unique, if the sum of elements in arr[i...j] is equal to the sum of numbers from i to j, the condition is met. The algorithm proceeds as follows:
- Start with the first chunk at index
i = 0. - Iterate
jfromiton-1. In this inner loop, maintain the sum of elements inarr[i...j](current_sum) and the sum of indices fromitoj(expected_sum). - When
current_sum == expected_sum, we have found the smallest possible valid chunkarr[i...j]. - We increment our chunk count, and start searching for the next chunk from index
j + 1. - We repeat this process until the entire array is partitioned.
class Solution { public int maxChunksToSorted(int[] arr) { int n = arr.length; int chunks = 0; int i = 0; while (i < n) { long currentSum = 0; long expectedSum = 0; for (int j = i; j < n; j++) { currentSum += arr[j]; expectedSum += j; if (currentSum == expectedSum) { chunks++; i = j + 1; break; } } } return chunks; }}Complexity
Time
O(n^2). The outer `while` loop and the inner `for` loop result in a nested iteration over the array elements. In the worst case (e.g., `arr = [n-1, n-2, ..., 0]`), the inner loop runs `n` times for the first and only chunk.
Space
O(1). We only use a few variables to store sums and counters, regardless of the input size.
Trade-offs
Pros
Conceptually straightforward greedy approach.
Doesn't require complex data structures.
Cons
Inefficient due to the nested loop structure, leading to a quadratic time complexity.
Solutions
Solution
class Solution {public int maxChunksToSorted(int[] arr) { int ans = 0, mx = 0; for (int i = 0; i < arr.length; ++i) { mx = Math.max(mx, arr[i]); if (i == mx) { ++ans; } } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.