You are given an integer array arr.
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 = [5,4,3,2,1] Output: 1 Explanation: Splitting into two or more chunks will not return the required result. For example, splitting into [5, 4], [3, 2, 1] will result in [4, 5, 1, 2, 3], which isn't sorted.
Example 2:
Input: arr = [2,1,3,4,4] Output: 4 Explanation: We can split into two chunks, such as [2, 1], [3, 4, 4]. However, splitting into [2, 1], [3], [4], [4] is the highest number of chunks possible.
Constraints:
1 <= arr.length <= 20000 <= arr[i] <= 108In #768 Max Chunks To Make Sorted II, the array may contain duplicates and is not guaranteed to be a permutation, which makes the chunk-splitting strategy more challenging than the simpler version of the problem. The key idea is to determine boundaries where splitting the array into independent chunks still results in a globally sorted array after individually sorting each chunk.
A common and efficient strategy uses a monotonic stack. As you iterate through the array, you maintain chunk maximums in a stack. If the current element is smaller than the top of the stack, it means previous chunks cannot remain separate, so they must be merged while preserving the maximum value of the merged chunk. This greedy merging ensures that chunk boundaries remain valid.
Another perspective involves comparing prefix maximums with suffix minimums to detect valid split points. Both approaches rely on understanding when the left portion will remain less than or equal to the right portion after sorting.
The optimal solutions typically run in O(n) time with O(n) auxiliary space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Monotonic Stack (Greedy Chunk Merging) | O(n) | O(n) |
| Prefix Max and Suffix Min Comparison | O(n) | O(n) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
Each k for which some permutation of arr[:k] is equal to sorted(arr)[:k] is where we should cut each chunk.
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, variations of this problem appear in coding interviews at large tech companies. It tests understanding of greedy thinking, stack-based patterns, and array partitioning strategies, which are common interview themes.
A monotonic stack is the most commonly used data structure for this problem. It helps track chunk maximums and efficiently merge chunks when ordering constraints are violated.
The optimal approach commonly uses a monotonic stack to track the maximum value of each chunk. When a smaller element appears, previous chunks are merged to maintain valid sorting boundaries. This greedy strategy ensures the array can be divided into the maximum number of valid chunks.
The second version allows duplicate values and arbitrary numbers instead of a simple permutation. Because of this, simple index-based comparisons no longer work, and more advanced strategies like monotonic stacks or prefix–suffix comparisons are required.