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.
This approach uses a monotonic stack to determine when the current number in arr can form a valid chunk. The logic involves maintaining the maximum number in the current chunk and popping elements from the stack until the current number is larger than the stack's top, effectively merging chunks. This ensures the final order is still preserved.
This C solution uses a stack to keep track of the current chunk's maximum elements. As it iterates through the array, it decides whether a new chunk can start or if merging is necessary.
Time Complexity: O(n), because we are iterating through the array once.
Space Complexity: O(n), for the stack used to track the maximum of current chunks.
This approach leverages prefix maximums and suffix minimums to determine the point of split where a new chunk can start. We maintain an array that keeps track of the maximum value up to the current index from the left and the minimum from the right.
This C solution calculates and compares prefix maximums with suffix minimums to decide valid chunk points. If the prefix max up to i is less than or equal to the suffix min starting from i+1, a new chunk can start.
Time Complexity: O(n), due to two linear passes through the array.
Space Complexity: O(n), for maintaining the prefix max and suffix min arrays.
| Approach | Complexity |
|---|---|
| Using Monotonic Stack | Time Complexity: O(n), because we are iterating through the array once. |
| Prefix Maximum and Suffix Minimum Comparison | Time Complexity: O(n), due to two linear passes through the array. |
| 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. |
Max Chunks To Make Array Sorted - 2 | Arrays & Strings | Leetcode 768 Solution in Hindi • Pepcoding • 18,183 views views
Watch 9 more video solutions →Practice Max Chunks To Make Sorted II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor