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] < narr are unique.Max Chunks To Make Sorted asks you to divide an array into the maximum number of chunks such that sorting each chunk individually and concatenating them results in a fully sorted array.
A key observation is that the array is a permutation of numbers from 0 to n-1. Using a greedy approach, you track the running maximum value while iterating through the array. Whenever the current index equals the maximum value seen so far, a valid chunk boundary is formed because all elements needed for that portion of the sorted array have already appeared.
Another conceptual way to reason about chunk boundaries is by maintaining order constraints similar to a monotonic stack, ensuring elements in earlier chunks never violate the sorted order of later chunks.
The greedy scan works in a single pass, making it highly efficient for interviews. It requires only constant extra space and linear time, making it the most optimal and commonly discussed approach.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Greedy with running maximum | O(n) | O(1) |
| Monotonic stack reasoning | O(n) | O(n) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
The first chunk can be found as the smallest k for which A[:k+1] == [0, 1, 2, ...k]; then we repeat this process.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this problem or its variations are common in technical interviews. It tests understanding of greedy strategies, array traversal, and reasoning about ordering constraints, which are common themes in FAANG-level interviews.
The problem can be solved without any complex data structure using a greedy scan and a running maximum. However, a monotonic stack can also be used conceptually to manage chunk boundaries and maintain order constraints.
The optimal approach uses a greedy strategy. By tracking the maximum value seen so far while iterating through the array, you can form a chunk whenever the current index matches that maximum value. This ensures all elements required for that segment are already present.
Because the array is a permutation of numbers from 0 to n-1, the correct position of each number is known. When the maximum value seen so far equals the current index, it means all values for that segment are present, so a chunk can safely end there.