Max Chunks To Make Sorted — Solution in Python, Java & C++
Max Chunks To Make Sorted solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Max Chunks To Make Sorted is a medium coding problem on arrays, sorting and greedy, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Sorting, Greedy, Stack, Monotonic Stack
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an array arr that is a permutation of [0, 1, …, n-1].
Split it into the largest possible number of contiguous chunks such that sorting each chunk individually and concatenating them yields the fully sorted array. Return that number of chunks.
Example 1
Input: arr = [4,3,2,1,0]
Output: 1
Explanation: Any split would leave the array unsorted.
Example 2
Input: arr = [1,0,2,3,4]
Output: 4
Example 3
Input: arr = [0,1,2]
Output: 3
Constraints
1 <= arr.length <= 40arr is a permutation of [0, 1, …, arr.length - 1].
Hints for Max Chunks To Make Sorted
Hint 1
A chunk can end at index
ionly if it holds exactly the values0…iin some order.Hint 2
Because the array is a permutation, that happens precisely when the maximum of the prefix equals
i.Hint 3
Sweep once, tracking the running maximum, and count every index where it matches.
How to solve Max Chunks To Make Sorted
A chunk can end at i exactly when the prefix holds the values 0..i, which for a permutation means the running maximum equals i.
Approach
- Sweep with
running = max(running, arr[i]). - Count every
iwhererunning == i.
Why it works
A permutation prefix of length i + 1 with maximum i must contain exactly 0..i, so it sorts into place independently of the rest; cutting at every such point maximises the count.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- For non-permutation inputs the general version compares prefix max with suffix min.
Reference solution
Python
def maxChunksToSorted(arr) -> int:
chunks = 0
running = -1
for i, x in enumerate(arr):
running = max(running, x)
if running == i:
chunks += 1
return chunksJava
public static int maxChunksToSorted(int[] arr) {
int chunks = 0, running = -1;
for (int i = 0; i < arr.length; i++) {
running = Math.max(running, arr[i]);
if (running == i) chunks++;
}
return chunks;
}C++
int maxChunksToSorted(vector<int>& arr) {
int chunks = 0, running = -1;
for (int i = 0; i < (int) arr.size(); i++) {
running = max(running, arr[i]);
if (running == i) chunks++;
}
return chunks;
}JavaScript
var maxChunksToSorted = function(arr) {
let chunks = 0, running = -1;
for (let i = 0; i < arr.length; i++) {
if (arr[i] > running) running = arr[i];
if (running === i) chunks++;
}
return chunks;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms