Max Chunks To Make Sorted solution and explanation
Google
9 more videos on this problem
Max Chunks To Make Sorted - Leetcode 769 - PythonNeetCodeIO · 10:50 · 10K views
Max Chunks To Make Sorted | 3 Detailed Approaches | Leetcode 769 | codestorywithMIKcodestorywithMIK · 36:04 · 8K views
Max Chunks To Make Sorted | Leetcode 769Techdose · 16:43 · 5K views
769. Max Chunks To Make Sorted | Prefix Sums | Multiple ApproachesAryan Mittal · 14:09 · 2K views
769. Max Chunks To Make Sorted | leetcode daily challenge | shashcode30ShashCode · 11:32 · 2K views
LeetCode: 769. Max Chunks To Make SortedZipher zyzz · 7:30 · 1K views
769. Max Chunks To Make Sorted (Leetcode Medium)Programming Live with Larry · 9:07 · 786 views
769. Max Chunks To Make Sorted | Leetcode Daily (POTD) 19 Dec 2024 | Java | HindiAlgorithmHQ · 10:04 · 645 views
LeetCode 769 Max Chunks To Make Sorted | Monotonic | Greedy | Asked in GoogleCode Harmony · 13:18 · 269 views
769. Max Chunks To Make Sorted || Leetcode Daily Problem || 19 DECNITian Kamal · 1:28 · 107 views
The problem
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.
class Solution:
def maxChunksToSorted(self, arr):
max_val = 0
count = 0
for i, num in enumerate(arr):
max_val = max(max_val, num)
if max_val == i:
count += 1
return count
sol = Solution()
arr = [1, 0, 2, 3, 4]
print(sol.maxChunksToSorted(arr))public class Solution {
public int maxChunksToSorted(int[] arr) {
int max = 0, count = 0;
for (int i = 0; i < arr.length; i++) {
max = Math.max(max, arr[i]);
if (max == i) {
count++;
}
}
return count;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] arr = {1, 0, 2, 3, 4};
System.out.println(sol.maxChunksToSorted(arr));
}
}#include <vector>
#include <iostream>
using namespace std;
class Solution {
public:
int maxChunksToSorted(vector<int>& arr) {
int max = 0, count = 0;
for (int i = 0; i < arr.size(); i++) {
max = std::max(max, arr[i]);
if (max == i) {
count++;
}
}
return count;
}
};
int main() {
vector<int> arr = {1, 0, 2, 3, 4};
Solution sol;
cout << sol.maxChunksToSorted(arr) << endl;
return 0;
}function maxChunksToSorted(arr) {
let max = 0, count = 0;
for (let i = 0; i < arr.length; i++) {
max = Math.max(max, arr[i]);
if (max === i) {
count++;
}
}
return count;
}
let arr = [1, 0, 2, 3, 4];
console.log(maxChunksToSorted(arr));#include <stdio.h>
int maxChunksToSorted(int* arr, int arrSize) {
int max = 0, count = 0;
for (int i = 0; i < arrSize; i++) {
if (arr[i] > max) {
max = arr[i];
}
if (max == i) {
count++;
}
}
return count;
}
int main() {
int arr[] = {1, 0, 2, 3, 4};
int n = sizeof(arr) / sizeof(arr[0]);
printf("%d\n", maxChunksToSorted(arr, n));
return 0;
}using System;
class Solution {
public int MaxChunksToSorted(int[] arr) {
int max = 0, chunks = 0;
for (int i = 0; i < arr.Length; i++) {
max = Math.Max(max, arr[i]);
if (max == i) {
chunks++;
}
}
return chunks;
}
static void Main(string[] args) {
int[] arr = { 1, 0, 2, 3, 4 };
Solution sol = new Solution();
Console.WriteLine(sol.MaxChunksToSorted(arr));
}
}We use Python's max function to maintain the highest value encountered so far while iterating over the array, and count full chunks when max equals the positional index.
Time Complexity: O(n)
Space Complexity: O(1)
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.
class Solution:
def maxChunksToSorted(self, arr):
sorted_arr = sorted(arr)
sum1 = sum2 = count = 0
for a, s in zip(arr, sorted_arr):
sum1 += a
sum2 += s
if sum1 == sum2:
count += 1
return count
sol = Solution()
arr = [1, 0, 2, 3, 4]
print(sol.maxChunksToSorted(arr))import java.util.Arrays;
public class Solution {
public int maxChunksToSorted(int[] arr) {
int[] sorted = arr.clone();
Arrays.sort(sorted);
int sum1 = 0, sum2 = 0, count = 0;
for (int i = 0; i < arr.length; i++) {
sum1 += arr[i];
sum2 += sorted[i];
if (sum1 == sum2) {
count++;
}
}
return count;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] arr = {1, 0, 2, 3, 4};
System.out.println(sol.maxChunksToSorted(arr));
}
}#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
class Solution {
public:
int maxChunksToSorted(vector<int>& arr) {
vector<int> sorted = arr;
sort(sorted.begin(), sorted.end());
int sum1 = 0, sum2 = 0, count = 0;
for (int i = 0; i < arr.size(); i++) {
sum1 += arr[i];
sum2 += sorted[i];
if (sum1 == sum2) {
count++;
}
}
return count;
}
};
int main() {
vector<int> arr = {1, 0, 2, 3, 4};
Solution sol;
cout << sol.maxChunksToSorted(arr) << endl;
return 0;
}function maxChunksToSorted(arr) {
let sorted = [...arr].sort((a, b) => a - b);
let sum1 = 0, sum2 = 0, count = 0;
for (let i = 0; i < arr.length; i++) {
sum1 += arr[i];
sum2 += sorted[i];
if (sum1 === sum2) {
count++;
}
}
return count;
}
let arr = [1, 0, 2, 3, 4];
console.log(maxChunksToSorted(arr));#include <stdio.h>
#include <stdlib.h>
int compare(const void* a, const void* b) {
return (*(int*)a - *(int*)b);
}
int maxChunksToSorted(int* arr, int arrSize) {
int sorted[arrSize];
for (int i = 0; i < arrSize; i++) {
sorted[i] = arr[i];
}
qsort(sorted, arrSize, sizeof(int), compare);
int sum1 = 0, sum2 = 0, count = 0;
for (int i = 0; i < arrSize; i++) {
sum1 += arr[i];
sum2 += sorted[i];
if (sum1 == sum2) {
count++;
}
}
return count;
}
int main() {
int arr[] = {1, 0, 2, 3, 4};
int n = sizeof(arr) / sizeof(arr[0]);
printf("%d\n", maxChunksToSorted(arr, n));
return 0;
}using System;
using System.Collections.Generic;
class Solution {
public int MaxChunksToSorted(int[] arr) {
int[] sorted = (int[])arr.Clone();
Array.Sort(sorted);
int sum1 = 0, sum2 = 0, count = 0;
for (int i = 0; i < arr.Length; i++) {
sum1 += arr[i];
sum2 += sorted[i];
if (sum1 == sum2) {
count++;
}
}
return count;
}
static void Main(string[] args) {
int[] arr = { 1, 0, 2, 3, 4 };
Solution sol = new Solution();
Console.WriteLine(sol.MaxChunksToSorted(arr));
}
}By summing original and sorted array values, chunk boundaries are found where these sums equalize.
Time Complexity: O(n log n)
Space Complexity: O(n)
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.
function maxChunksToSorted(arr: number[]): number {
const n = arr.length;
let ans = 0;
let mx = 0;
for (let i = 0; i < n; i++) {
mx = Math.max(arr[i], mx);
if (mx == i) {
ans++;
}
}
return ans;
}func maxChunksToSorted(arr []int) int {
ans, mx := 0, 0
for i, v := range arr {
mx = max(mx, v)
if i == mx {
ans++
}
}
return ans
}impl Solution {
pub fn max_chunks_to_sorted(arr: Vec<i32>) -> i32 {
let mut ans = 0;
let mut mx = 0;
for i in 0..arr.len() {
mx = mx.max(arr[i]);
if mx == (i as i32) {
ans += 1;
}
}
ans
}
}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.
function maxChunksToSorted(arr: number[]): number {
const stk: number[] = [];
for (const x of arr) {
if (stk.at(-1)! > x) {
const top = stk.pop()!;
while (stk.length && stk.at(-1)! > x) stk.pop();
stk.push(top);
} else stk.push(x);
}
return stk.length;
}func maxChunksToSorted(arr []int) int {
stk := []int{}
for _, v := range arr {
if len(stk) == 0 || v >= stk[len(stk)-1] {
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)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Greedy with Max Tracking | Time Complexity: O(n) |
| Approach 2: Sort and Compare | Time Complexity: O(n log n) |
| Greedy + One Pass | – |
| Monotonic Stack | – |
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 |
Frequently asked questions
Is Max Chunks To Make Sorted easy or hard?
Max Chunks To Make Sorted is categorized as a Medium problem. The implementation is simple once the greedy observation is discovered, but recognizing the correct chunk boundary condition requires algorithmic insight.
Max Chunks To Make Sorted Python/Java solution
In Python or Java, iterate through the array while updating a variable that stores the maximum value seen so far. Whenever this maximum equals the current index, increment a chunk counter. The implementation is short and runs in O(n) time with constant extra space.
How to solve Max Chunks To Make Sorted in O(n)?
Track the maximum element encountered while iterating through the array. If the maximum value equals the current index, all elements within that segment belong in the first i+1 positions of the sorted array. That position becomes a valid chunk boundary, and you increment the chunk count.
What is the best approach for Max Chunks To Make Sorted?
The best approach uses a greedy scan with maximum tracking. While iterating through the array, keep track of the maximum value seen so far. When the running maximum equals the current index, a valid chunk boundary exists. This method runs in O(n) time and O(1) space.
Is Max Chunks To Make Sorted asked at Google/Amazon/Meta?
Variants of this problem appear in interviews at companies like Amazon, Google, and other large tech firms because it tests greedy reasoning and array invariants. Interviewers often expect candidates to recognize the O(n) greedy boundary condition.
What data structure is used in Max Chunks To Make Sorted?
The most common solution only uses a running integer variable to track the maximum value, making it a greedy array traversal problem. Conceptually, related variants can be solved using a monotonic stack when duplicates or different constraints are introduced.
What is the time complexity of Max Chunks To Make Sorted?
The optimal greedy solution runs in O(n) time because the array is scanned once while maintaining a running maximum. A simpler approach that sorts a copy of the array requires O(n log n) time due to the sorting step.