Watch 10 video solutions for Max Chunks To Make Sorted, a medium level problem involving Array, Stack, Greedy. This walkthrough by Pepcoding has 21,653 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.Problem Overview: You receive a permutation of the numbers 0..n-1. The goal is to split the array into the maximum number of chunks such that sorting each chunk individually and concatenating them results in the fully sorted array. The challenge is identifying boundaries where a chunk can safely end without breaking the global order.
Approach 1: Greedy with Max Tracking (O(n) time, O(1) space)
The optimal observation: in a valid chunk ending at index i, every element inside that chunk must be less than or equal to i after sorting. While scanning the array, track the maximum value seen so far. If the running maximum equals the current index, then all elements from the current chunk belong within the range 0..i. That means sorting this segment will place every value exactly where it should be in the final sorted array. Increment the chunk count and continue scanning. This greedy rule works because the input is a permutation with no duplicates. The approach performs a single pass through the array and uses constant extra memory. This technique is closely related to greedy boundary detection used in greedy algorithms and can be viewed as a simplified version of a monotonic stack boundary strategy.
Approach 2: Sort and Compare (O(n log n) time, O(n) space)
A more intuitive method compares prefixes of the original array with a sorted version. First create a sorted copy of the array. Iterate through both arrays while maintaining running prefix information. When the elements in the original prefix contain exactly the same values as the sorted prefix, a valid chunk boundary exists. In practice, this is implemented by tracking cumulative properties or verifying equality conditions between prefixes. Once both prefixes match, increment the chunk count and start a new segment. The approach relies on sorting to establish the correct order and then identifies safe split points. Although easier to reason about, the sorting step increases the runtime to O(n log n) and requires additional memory for the copied array.
Recommended for interviews: The greedy max-tracking solution is what interviewers typically expect. It demonstrates recognition of the permutation property and the key invariant: when the maximum value seen so far equals the current index, a chunk boundary is guaranteed. The sort-and-compare method still shows correct reasoning and works as a stepping stone, but the O(n) greedy approach highlights stronger algorithmic insight and efficient use of array traversal.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy with Max Tracking | O(n) | O(1) | Best solution for permutation arrays when you need maximum chunks efficiently |
| Sort and Compare | O(n log n) | O(n) | Good for understanding the problem conceptually or when deriving the greedy insight |