Max Chunks To Make Sorted II solution and explanation
Google
9 more videos on this problem
Max Chunks To Make Array Sorted - 2 | Arrays & Strings | Leetcode 768 Solution in HindiPepcoding · 20:47 · 18K views
768. Max Chunks To Make Sorted II (Leetcode Hard)Programming Live with Larry · 10:32 · 3K views
【每日一题】768. Max Chunks To Make Sorted II, 5/18/2020Huifeng Guan · 30:26 · 1K views
LeetCode Hard 768. Max Chunks To Make Sorted IIGot Up Late · 17:46 · 806 views
Max Chunks to Make Sorted II Leetcode 768Next Door Professor · 14:59 · 457 views
Leetcode 0768. Max Chunks To Make Sorted IIFearless Learner · 7:29 · 378 views
768 max chunks to make sorted IIJimmy Wang · 1:02 · 81 views
문제풀이실패] LeetCode #768 Max Chunks To Make Sorted II (#8)LeetCode 푸는 개발자 매직리 · 41:26 · 38 views
No Sound Leetcode 768: Max Chunks To Make Sorted IIExtremeProgrammer · 1:03 · 21 views
LeetCode 768: Max Chunks To Make Sorted IIAlitaCode · 27:53 · 7 views
The problem
You are given an integer array arr.
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 = [5,4,3,2,1] Output: 1 Explanation: Splitting into two or more chunks will not return the required result. For example, splitting into [5, 4], [3, 2, 1] will result in [4, 5, 1, 2, 3], which isn't sorted.
Example 2:
Input: arr = [2,1,3,4,4] Output: 4 Explanation: We can split into two chunks, such as [2, 1], [3, 4, 4]. However, splitting into [2, 1], [3], [4], [4] is the highest number of chunks possible.
Constraints:
1 <= arr.length <= 20000 <= arr[i] <= 108
Approach overview
Problem Overview: Given an integer array (with possible duplicates), split it into the maximum number of chunks so that sorting each chunk individually and concatenating them results in the entire array being sorted. The challenge is identifying valid split points where the left part never needs elements from the right part to maintain global order.
Approach 1: Prefix Maximum and Suffix Minimum Comparison (O(n) time, O(n) space)
This approach precomputes ordering constraints from both directions. Build a prefixMax array where prefixMax[i] stores the maximum value from index 0..i. Build a suffixMin array where suffixMin[i] stores the minimum value from index i..n-1. A valid chunk boundary exists at index i if prefixMax[i] <= suffixMin[i+1]. That condition guarantees every element in the left chunk is less than or equal to every element in the right chunk, so sorting them independently preserves global order. Iterate once to compute prefix and suffix arrays, then scan again to count valid split points. This method is easy to reason about and works well when clarity matters more than memory usage. It relies heavily on concepts from Array processing and Sorting order properties.
Approach 2: Monotonic Stack (O(n) time, O(n) space)
The optimal interview solution uses a Monotonic Stack to dynamically maintain chunk boundaries. Traverse the array while keeping a stack where each element represents the maximum value of a chunk. If the current value is greater than or equal to the top of the stack, it can safely start a new chunk, so push it onto the stack. When the current value is smaller than the stack top, it violates the ordering of previous chunks. Pop stack elements until the stack top is less than or equal to the current value, merging those chunks into one larger chunk. Track the maximum value from the popped elements and push it back to represent the merged chunk. The stack size at the end equals the number of valid chunks. This greedy merging ensures earlier chunks expand whenever later elements would otherwise break global ordering.
Recommended for interviews: The monotonic stack approach is typically what interviewers expect for Hard-level array partitioning problems. It shows you recognize ordering violations and can merge segments efficiently in a single pass. The prefix–suffix method demonstrates strong reasoning about global ordering constraints and is often easier to implement quickly. Showing awareness of both approaches signals solid understanding of Greedy techniques and boundary detection patterns.
Approach 1: Using Monotonic Stack
This approach uses a monotonic stack to determine when the current number in arr can form a valid chunk. The logic involves maintaining the maximum number in the current chunk and popping elements from the stack until the current number is larger than the stack's top, effectively merging chunks. This ensures the final order is still preserved.
def maxChunksToSorted(arr):
stack = []
for num in arr:
if not stack or num >= stack[-1]:
stack.append(num)
else:
max_val = stack.pop()
while stack and stack[-1] > num:
stack.pop()
stack.append(max_val)
return len(stack)
print(maxChunksToSorted([2, 1, 3, 4, 4]))import java.util.Stack;
public class Solution {
public int maxChunksToSorted(int[] arr) {
Stack<Integer> stack = new Stack<>();
for (int num : arr) {
if (stack.isEmpty() || num >= stack.peek()) {
stack.push(num);
} else {
int maxVal = stack.pop();
while (!stack.isEmpty() && stack.peek() > num) {
stack.pop();
}
stack.push(maxVal);
}
}
return stack.size();
}
public static void main(String[] args) {
int[] arr = {2, 1, 3, 4, 4};
Solution solution = new Solution();
System.out.println(solution.maxChunksToSorted(arr));
}
}#include <vector>
#include <stack>
#include <iostream>
using namespace std;
int maxChunksToSorted(vector<int>& arr) {
stack<int> s;
for (int num : arr) {
if (s.empty() || num >= s.top()) {
s.push(num);
} else {
int maxVal = s.top();
s.pop();
while (!s.empty() && s.top() > num) {
s.pop();
}
s.push(maxVal);
}
}
return s.size();
}
int main() {
vector<int> arr = {2, 1, 3, 4, 4};
cout << maxChunksToSorted(arr) << endl;
return 0;
}function maxChunksToSorted(arr) {
const stack = [];
for (let num of arr) {
if (!stack.length || num >= stack[stack.length - 1]) {
stack.push(num);
} else {
let maxVal = stack.pop();
while (stack.length && stack[stack.length - 1] > num) {
stack.pop();
}
stack.push(maxVal);
}
}
return stack.length;
}
console.log(maxChunksToSorted([2, 1, 3, 4, 4]));#include <stdio.h>
#include <stdlib.h>
int maxChunksToSorted(int* arr, int arrSize) {
int stack[arrSize];
int top = -1;
for (int i = 0; i < arrSize; i++) {
if (top == -1 || arr[i] >= stack[top]) {
stack[++top] = arr[i];
} else {
int maxInChunk = stack[top--];
while (top != -1 && stack[top] > arr[i]) {
top--;
}
stack[++top] = maxInChunk;
}
}
return top + 1;
}
int main() {
int arr[] = {2, 1, 3, 4, 4};
int arrSize = sizeof(arr) / sizeof(arr[0]);
printf("%d\n", maxChunksToSorted(arr, arrSize));
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public int MaxChunksToSorted(int[] arr) {
Stack<int> stack = new Stack<int>();
foreach (int num in arr) {
if (stack.Count == 0 || num >= stack.Peek()) {
stack.Push(num);
} else {
int maxVal = stack.Pop();
while (stack.Count > 0 && stack.Peek() > num) {
stack.Pop();
}
stack.Push(maxVal);
}
}
return stack.Count;
}
static void Main() {
int[] arr = {2, 1, 3, 4, 4};
Solution solution = new Solution();
Console.WriteLine(solution.MaxChunksToSorted(arr));
}
}This Python solution utilizes a stack to check and validate chunks by monitoring the maximum element's integrity, then merging as needed.
Time Complexity: O(n).
Space Complexity: O(n), using stack.
Approach 2: Prefix Maximum and Suffix Minimum Comparison
This approach leverages prefix maximums and suffix minimums to determine the point of split where a new chunk can start. We maintain an array that keeps track of the maximum value up to the current index from the left and the minimum from the right.
def maxChunksToSorted(arr):
n = len(arr)
leftMax = [0] * n
rightMin = [float('inf')] * (n + 1)
leftMax[0] = arr[0]
for i in range(1, n):
leftMax[i] = max(arr[i], leftMax[i - 1])
for i in range(n - 1, -1, -1):
rightMin[i] = min(arr[i], rightMin[i + 1])
count = 0
for i in range(n):
if leftMax[i] <= rightMin[i + 1]:
count += 1
return count
print(maxChunksToSorted([2, 1, 3, 4, 4]))import java.util.Arrays;
public class Solution {
public int maxChunksToSorted(int[] arr) {
int n = arr.length;
int[] leftMax = new int[n];
int[] rightMin = new int[n + 1];
leftMax[0] = arr[0];
for (int i = 1; i < n; i++) {
leftMax[i] = Math.max(arr[i], leftMax[i - 1]);
}
Arrays.fill(rightMin, Integer.MAX_VALUE);
for (int i = n - 1; i >= 0; i--) {
rightMin[i] = Math.min(arr[i], rightMin[i + 1]);
}
int count = 0;
for (int i = 0; i < n; i++) {
if (leftMax[i] <= rightMin[i + 1]) {
count++;
}
}
return count;
}
public static void main(String[] args) {
int[] arr = {2, 1, 3, 4, 4};
Solution solution = new Solution();
System.out.println(solution.maxChunksToSorted(arr));
}
}#include <vector>
#include <iostream>
#include <climits>
using namespace std;
int maxChunksToSorted(vector<int>& arr) {
int n = arr.size();
vector<int> leftMax(n);
vector<int> rightMin(n + 1, INT_MAX);
leftMax[0] = arr[0];
for (int i = 1; i < n; i++) {
leftMax[i] = max(arr[i], leftMax[i - 1]);
}
for (int i = n - 1; i >= 0; i--) {
rightMin[i] = min(arr[i], rightMin[i + 1]);
}
int count = 0;
for (int i = 0; i < n; i++) {
if (leftMax[i] <= rightMin[i + 1]) {
count++;
}
}
return count;
}
int main() {
vector<int> arr = {2, 1, 3, 4, 4};
cout << maxChunksToSorted(arr) << endl;
return 0;
}function maxChunksToSorted(arr) {
const n = arr.length;
const leftMax = new Array(n);
const rightMin = new Array(n + 1).fill(Infinity);
leftMax[0] = arr[0];
for (let i = 1; i < n; i++) {
leftMax[i] = Math.max(arr[i], leftMax[i - 1]);
}
for (let i = n - 1; i >= 0; i--) {
rightMin[i] = Math.min(arr[i], rightMin[i + 1]);
}
let count = 0;
for (let i = 0; i < n; i++) {
if (leftMax[i] <= rightMin[i + 1]) {
count++;
}
}
return count;
}
console.log(maxChunksToSorted([2, 1, 3, 4, 4]));#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int maxChunksToSorted(int* arr, int arrSize) {
int* leftMax = (int*)malloc(arrSize * sizeof(int));
int* rightMin = (int*)malloc((arrSize + 1) * sizeof(int));
leftMax[0] = arr[0];
for (int i = 1; i < arrSize; i++) {
leftMax[i] = arr[i] > leftMax[i - 1] ? arr[i] : leftMax[i - 1];
}
rightMin[arrSize] = 1e8;
for (int i = arrSize - 1; i >= 0; i--) {
rightMin[i] = arr[i] < rightMin[i + 1] ? arr[i] : rightMin[i + 1];
}
int count = 0;
for (int i = 0; i < arrSize; i++) {
if (leftMax[i] <= rightMin[i + 1]) {
count++;
}
}
free(leftMax);
free(rightMin);
return count;
}
int main() {
int arr[] = {2, 1, 3, 4, 4};
int arrSize = sizeof(arr) / sizeof(arr[0]);
printf("%d\n", maxChunksToSorted(arr, arrSize));
return 0;
}using System;
public class Solution {
public int MaxChunksToSorted(int[] arr) {
int n = arr.Length;
int[] leftMax = new int[n];
int[] rightMin = new int[n + 1];
leftMax[0] = arr[0];
for (int i = 1; i < n; i++) {
leftMax[i] = Math.Max(arr[i], leftMax[i - 1]);
}
Array.Fill(rightMin, int.MaxValue);
for (int i = n - 1; i >= 0; i--) {
rightMin[i] = Math.Min(arr[i], rightMin[i + 1]);
}
int count = 0;
for (int i = 0; i < n; i++) {
if (leftMax[i] <= rightMin[i + 1]) {
count++;
}
}
return count;
}
static void Main() {
int[] arr = {2, 1, 3, 4, 4};
Solution solution = new Solution();
Console.WriteLine(solution.MaxChunksToSorted(arr));
}
}Python implementation of the prefix max and suffix min approach involves calculating two arrays, which are compared to count possible chunks effectively.
Time Complexity: O(n).
Space Complexity: O(n), due to arrays used for maxima and minima.
Approach 3: Monotonic Stack
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 (non-strictly 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.
Time complexity is O(n), where n represents the length of arr.
function maxChunksToSorted(arr: number[]): number {
const stk: number[] = [];
for (let v of arr) {
if (stk.length === 0 || v >= stk[stk.length - 1]) {
stk.push(v);
} else {
let mx = stk.pop()!;
while (stk.length > 0 && stk[stk.length - 1] > v) {
stk.pop();
}
stk.push(mx);
}
}
return stk.length;
}func maxChunksToSorted(arr []int) int {
var stk []int
for _, v := range arr {
if len(stk) == 0 || stk[len(stk)-1] <= v {
stk = append(stk, v)
} else {
mx := stk[len(stk)-1]
stk = stk[:len(stk)-1]
for len(stk) > 0 && stk[len(stk)-1] > v {
stk = stk[:len(stk)-1]
}
stk = append(stk, mx)
}
}
return len(stk)
}impl Solution {
pub fn max_chunks_to_sorted(arr: Vec<i32>) -> i32 {
let mut stk = Vec::new();
for &v in arr.iter() {
if stk.is_empty() || v >= *stk.last().unwrap() {
stk.push(v);
} else {
let mut mx = stk.pop().unwrap();
while let Some(&top) = stk.last() {
if top > v {
stk.pop();
} else {
break;
}
}
stk.push(mx);
}
}
stk.len() as i32
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Using Monotonic Stack | Time Complexity: O(n). |
| Prefix Maximum and Suffix Minimum Comparison | Time Complexity: O(n). |
| Monotonic Stack | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Prefix Max & Suffix Min | O(n) | O(n) | When you want a straightforward method that clearly identifies chunk boundaries using precomputed ordering information. |
| Monotonic Stack | O(n) | O(n) | Preferred in interviews and optimal single-pass solution when handling ordering violations dynamically. |
Frequently asked questions
Is Max Chunks To Make Sorted II easy or hard?
Max Chunks To Make Sorted II is classified as a Hard problem on LeetCode. Handling duplicate values and determining safe partition boundaries makes it more complex than the original version. Efficient solutions require recognizing greedy merging patterns or prefix–suffix ordering checks.
Max Chunks To Make Sorted II Python/Java solution
Python and Java implementations usually follow either the monotonic stack pattern or the prefix max/suffix min approach. The stack solution iterates once and merges chunks dynamically, while the prefix-suffix solution precomputes boundary constraints before counting valid splits.
How to solve Max Chunks To Make Sorted II in O(n)?
Compute prefix maximums and suffix minimums, then count indices where prefixMax[i] <= suffixMin[i+1]. Each such index represents a valid chunk boundary. Another O(n) method uses a monotonic stack that merges chunks whenever a smaller element violates the ordering of previous chunks.
What is the best approach for Max Chunks To Make Sorted II?
The monotonic stack approach is considered the best solution. It processes the array in one pass while maintaining chunk boundaries using a stack of maximum values. When a smaller element appears, earlier chunks are merged to preserve global order. The algorithm runs in O(n) time with O(n) space.
Is Max Chunks To Make Sorted II asked at Google/Amazon/Meta?
Max Chunks To Make Sorted II appears in interview preparation lists for companies like Google, Amazon, and Meta because it tests array partitioning, greedy reasoning, and monotonic stack patterns. Variations of this problem often appear in coding interviews focused on segment boundaries and ordering constraints.
What data structure is used in Max Chunks To Make Sorted II?
The key data structure is a monotonic stack that stores the maximum value of each chunk. It allows efficient merging of previous chunks when a new element breaks sorted ordering. The alternative approach uses prefix and suffix arrays to track maximum and minimum values.
What is the time complexity of Max Chunks To Make Sorted II?
The optimal solutions run in O(n) time where n is the length of the array. Both the monotonic stack approach and the prefix maximum–suffix minimum method require a single or small constant number of passes through the array. Space complexity is O(n) due to either the auxiliary arrays or the stack.