Max Chunks To Make Sorted - Solution & Explanation
Problem Statement
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] < n- All the elements of
arrare unique.
Approach Overview
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 1: Approach 1: Greedy with Max Tracking
In this approach, we iterate over the array using a pointer. We track the maximum element we've seen at each point. Every time the maximum element seen so far equals the current index, it signifies that a chunk can end here. The chunk defined between the previous chunk's end and the current index can be sorted alone to align with the sorted array.
We declare variables to track the maximum value encountered and the count of chunks. As we iterate, if we reach a point where the maximum value is equal to the index, it represents the end of a chunk, and we increment the count.
Complexity
Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(1), as we only use constant extra space.
Approach 2: Approach 2: Sort and Compare
This approach involves first sorting the original array and using a sorted version to compare and identify zero-sum ranges. By keeping a cumulative sum difference between the original array and the sorted array, chunks can be identified at points where this cumulative sum is zero, indicating matching segments that can form a chunk.
We copy and sort the array. By comparing cumulative sums of the original and sorted arrays, each zero-sum segment signifies a chunk.
Complexity
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) for the sorted array copy.
Approach 3: Greedy + One Pass
Since arr is a permutation of [0,..,n-1], if the maximum value mx among the numbers traversed so far is equal to the current index i, it means a split can be made, and the answer is incremented.
Time complexity is O(n), and space complexity is O(1). Where n is the length of the array arr.
Approach 4: Monotonic Stack
The solution of method one has certain limitations. If there are duplicate elements in the array, the correct answer cannot be obtained.
According to the problem, we can find that from left to right, each chunk has a maximum value, and these maximum values are monotonically increasing. We can use a stack to store these maximum values of the chunks. The size of the final stack is the maximum number of chunks that can be sorted.
This solution can not only solve this problem but also solve the problem 768. Max Chunks To Make Sorted II. You can try it yourself.
Time complexity is O(n), and space complexity is O(n). Where n is the length of the array arr.
Code
Python
Java
C++
Go
TypeScript
JavaScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Greedy with Max Tracking | Time Complexity: O(n), where n is the length of the array. |
| Approach 2: Sort and Compare | Time Complexity: O(n log n) due to sorting. |
| Greedy + One Pass | — |
| Monotonic Stack | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Max Chunks To Make Sorted - Leetcode 769 - Python • NeetCodeIO • 10,450 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Max Chunks To Make Sorted easy or hard?
Max Chunks To Make Sorted Python/Java solution
How to solve Max Chunks To Make Sorted in O(n)?
What is the best approach for Max Chunks To Make Sorted?
Is Max Chunks To Make Sorted asked at Google/Amazon/Meta?
What data structure is used in Max Chunks To Make Sorted?
What is the time complexity of Max Chunks To Make Sorted?
Ready to solve this problem?
Practice Max Chunks To Make Sorted with our built-in code editor and test cases.
Practice on FleetCode