Max Chunks To Make Sorted II — Problem & Solution
Max Chunks To Make Sorted II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Max Chunks To Make Sorted II is a hard coding problem on arrays, greedy and stack, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Arrays, 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
Split the integer array arr into contiguous chunks, sort each chunk on its own, and put the chunks back together in their original order. The split is valid if the result equals arr sorted in non-decreasing order.
Values may repeat. Return the largest number of chunks a valid split can have.
Example 1
Input: arr = [3,2,4,4,6,5]
Output: 4
Explanation: `[3,2] [4] [4] [6,5]` sorts to `[2,3,4,4,5,6]`.
Example 2
Input: arr = [5,1,1,8,2]
Output: 1
Explanation: The final 2 must move in front of the 5, so everything is one chunk.
Example 3
Input: arr = [1,1,0,0,1]
Output: 2
Explanation: `[1,1,0,0] [1]`.
Constraints
1 <= arr.length <= 20000 <= arr[i] <= 10^8
Hints for Max Chunks To Make Sorted II
Hint 1
A cut after position
iis allowed exactly when everything to its left is<=everything to its right.Hint 2
Represent each chunk by its maximum and keep the chunks on a stack. What happens when a value smaller than some chunk maxima arrives?
Hint 3
If the new value
xis smaller than the top chunk's maximum, it must join that chunk — and every earlier chunk whose maximum is greater thanx. Pop them all and push back the largest maximum.
How to solve Max Chunks To Make Sorted II
Maintain the current best partition of the prefix as a stack of chunk maxima (non-decreasing from bottom to top). A new value either starts a chunk of its own or forces the chunks with larger maxima to fuse with it.
Approach
- For each
xinarr: if the stack is empty orx >= top, pushx— it can be a chunk on its own. - Otherwise remember
mx = top(the largest maximum so far), pop it, and keep popping while the new top is> x. - Push
mxback: the fused chunk's maximum. - The answer is the stack size.
Why it works
A value x must end up before every value greater than it, so it cannot be separated from any earlier chunk whose maximum exceeds x; those chunks are contiguous at the top of the stack because the maxima are non-decreasing. Chunks whose maximum is <= x can stay separate, since x (and everything in its chunk so far) is not smaller than anything in them. Merging only what is forced keeps the number of chunks as large as possible.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Duplicates break the 'Max Chunks I' trick of comparing with indices — compare values instead.
- Pop only while the top is strictly greater than
x; equal maxima can stay apart. - Push back the largest popped maximum, not
x.
Reference solution
Python
from typing import List
def maxChunksToSorted(arr: List[int]) -> int:
st = []
for x in arr:
if not st or x >= st[-1]:
st.append(x)
else:
mx = st.pop()
while st and st[-1] > x:
st.pop()
st.append(mx)
return len(st)Java
public static int maxChunksToSorted(int[] arr) {
int[] st = new int[arr.length];
int top = 0;
for (int x : arr) {
if (top == 0 || x >= st[top - 1]) {
st[top++] = x;
} else {
int mx = st[--top];
while (top > 0 && st[top - 1] > x) top--;
st[top++] = mx;
}
}
return top;
}C++
int maxChunksToSorted(vector<int>& arr) {
vector<int> st;
for (int x : arr) {
if (st.empty() || x >= st.back()) {
st.push_back(x);
} else {
int mx = st.back();
st.pop_back();
while (!st.empty() && st.back() > x) st.pop_back();
st.push_back(mx);
}
}
return st.size();
}JavaScript
var maxChunksToSorted = function(arr) {
var st = [];
for (var i = 0; i < arr.length; i++) {
var x = arr[i];
if (st.length === 0 || x >= st[st.length - 1]) {
st.push(x);
} else {
var mx = st.pop();
while (st.length > 0 && st[st.length - 1] > x) st.pop();
st.push(mx);
}
}
return st.length;
};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 · Greedy Algorithms