Watch 10 video solutions for Max Chunks To Make Sorted II, a hard level problem involving Array, Stack, Greedy. This walkthrough by Pepcoding has 18,183 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] <= 108Problem Overview: Given an integer array (with possible duplicates), split it into the maximum number of chunks so that sorting each chunk individually and concatenating them results in the entire array being sorted. The challenge is identifying valid split points where the left part never needs elements from the right part to maintain global order.
Approach 1: Prefix Maximum and Suffix Minimum Comparison (O(n) time, O(n) space)
This approach precomputes ordering constraints from both directions. Build a prefixMax array where prefixMax[i] stores the maximum value from index 0..i. Build a suffixMin array where suffixMin[i] stores the minimum value from index i..n-1. A valid chunk boundary exists at index i if prefixMax[i] <= suffixMin[i+1]. That condition guarantees every element in the left chunk is less than or equal to every element in the right chunk, so sorting them independently preserves global order. Iterate once to compute prefix and suffix arrays, then scan again to count valid split points. This method is easy to reason about and works well when clarity matters more than memory usage. It relies heavily on concepts from Array processing and Sorting order properties.
Approach 2: Monotonic Stack (O(n) time, O(n) space)
The optimal interview solution uses a Monotonic Stack to dynamically maintain chunk boundaries. Traverse the array while keeping a stack where each element represents the maximum value of a chunk. If the current value is greater than or equal to the top of the stack, it can safely start a new chunk, so push it onto the stack. When the current value is smaller than the stack top, it violates the ordering of previous chunks. Pop stack elements until the stack top is less than or equal to the current value, merging those chunks into one larger chunk. Track the maximum value from the popped elements and push it back to represent the merged chunk. The stack size at the end equals the number of valid chunks. This greedy merging ensures earlier chunks expand whenever later elements would otherwise break global ordering.
Recommended for interviews: The monotonic stack approach is typically what interviewers expect for Hard-level array partitioning problems. It shows you recognize ordering violations and can merge segments efficiently in a single pass. The prefix–suffix method demonstrates strong reasoning about global ordering constraints and is often easier to implement quickly. Showing awareness of both approaches signals solid understanding of Greedy techniques and boundary detection patterns.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Prefix Max & Suffix Min | O(n) | O(n) | When you want a straightforward method that clearly identifies chunk boundaries using precomputed ordering information. |
| Monotonic Stack | O(n) | O(n) | Preferred in interviews and optimal single-pass solution when handling ordering violations dynamically. |