Max Chunks To Make Sorted II
Problem
Given an array with possible duplicates, split it into the maximum number of chunks such that sorting each chunk individually and concatenating yields the sorted array.
arr=[5,4,3,2,1]1def maxChunksToSorted(arr):
stack = []
for x in arr:
if not stack or x >= stack[-1]:
stack.append(x)
else:
top = stack.pop()
while stack and stack[-1] > x:
stack.pop()
stack.append(top)
return len(stack)function maxChunksToSorted(arr) {
const stack = [];
for (const x of arr) {
if (!stack.length || x >= stack[stack.length-1]) stack.push(x);
else {
const top = stack.pop();
while (stack.length && stack[stack.length-1] > x) stack.pop();
stack.push(top);
}
}
return stack.length;
}int maxChunksToSorted(int[] arr) {
Deque<Integer> stack = new ArrayDeque<>();
for (int x : arr) {
if (stack.isEmpty() || x >= stack.peek()) stack.push(x);
else {
int top = stack.pop();
while (!stack.isEmpty() && stack.peek() > x) stack.pop();
stack.push(top);
}
}
return stack.size();
}int maxChunksToSorted(vector<int>& arr) {
stack<int> st;
for (int x : arr) {
if (st.empty() || x >= st.top()) st.push(x);
else {
int top = st.top(); st.pop();
while (!st.empty() && st.top() > x) st.pop();
st.push(top);
}
}
return st.size();
}Explanation
A chunk can become its own piece only if everything inside it is smaller-or-equal to everything that comes after it. The clever way to track this is with a monotonic stack where each entry is the maximum value of one chunk.
We walk the array left to right. If the new value x is at least as big as the top of the stack, it can safely start a brand new chunk, so we just push it. If x is smaller than the top, then x must be swallowed into earlier chunks: those chunks can no longer be split apart from it.
When x is smaller, we pop the current top (remembering it as top), then keep popping every chunk-max that is still bigger than x. We merge them all into one chunk and push back top, the largest max among the merged chunks. The number of separate chunks at the end is just len(stack).
Example: arr=[5,4,3,2,1]. Push 5. Then 4<5 so merge into one chunk with max 5. Then 3, 2, 1 each keep merging into that same chunk. The stack ends with a single value, so the answer is 1.
It works because a value smaller than an earlier max proves those positions cannot be sorted independently, and keeping only the running chunk-max on the stack is enough to decide every future merge in one pass.