Introduction

LeetCode 769, Max Chunks To Make Sorted, is an interesting array partitioning problem.

The array is a permutation of numbers from 0 to n - 1. The goal is to divide the array into multiple contiguous chunks, sort each chunk independently, and then join all the sorted chunks together.

The challenge is to find the maximum number of chunks for which the final concatenated array becomes completely sorted.

For example:

arr = [1,0,2,3,4]

The array can be divided as:

[1,0] [2] [3] [4]

After sorting every chunk:

[0,1] [2] [3] [4]

The final array is:

[0,1,2,3,4]

Therefore, the answer is 4.

The given solution approaches the problem using recursion and backtracking to generate possible partitions and then checks which partitions produce a sorted array.

Question Link

LeetCode 769 – Max Chunks To Make Sorted

Understanding the Problem

The important word in the problem is chunks.

A chunk must contain consecutive elements from the original array.

For example:

[4,3,2,1,0]

Possible partition:

[4,3] [2,1,0]

After sorting:

[3,4] [0,1,2]

Combining them gives:

[3,4,0,1,2]

which is not sorted.

So this partition is invalid.

The task is not simply to split the array into as many pieces as possible. Every chosen partition must satisfy the condition that sorting each piece independently produces the globally sorted array.

Approach: Recursion + Backtracking

The given solution tries every possible way of partitioning the array.

At every index, it considers every possible ending position for the current chunk.

For example:

arr = [1,0,2]

Starting from index 0, possible first chunks are:

[1]

[1,0]

[1,0,2]

For each choice, recursion continues from the next index.

This generates different partition configurations such as:

[1] [0] [2]

[1,0] [2]

[1] [0,2]

[1,0,2]

Each complete partition is then checked to determine whether it produces a sorted array.

Generating the Chunks

The recursive function is:

public void sol(int[] arr, int ind, List<List<Integer>> chunk)

Here:

ind represents the current starting index.
chunk stores the chunks selected so far.

The loop:

for(int i = ind; i < arr.length; i++){

List<Integer> lis = subar(arr, ind, i);

chunk.add(lis);

sol(arr, i + 1, chunk);

chunk.remove(chunk.size() - 1);

}

tries every possible ending point for the current chunk.

The important part is:

sol(arr, i + 1, chunk);

Once a chunk from ind to i has been selected, the next chunk must begin at i + 1.

Creating a Chunk

The subar() method creates a list containing the elements between two indices.

public List<Integer> subar(int[] arr, int st, int en){

List<Integer> lis = new ArrayList<>();

for(int i = st; i <= en; i++){

lis.add(arr[i]);

}

return lis;

}

For example:

arr = [1,0,2,3]

st = 0

en = 1

produces:

[1,0]

Checking a Partition

Once a complete partition has been generated, the vali() method checks whether it is valid.

First, every chunk is sorted:

Collections.sort(a);

Then all sorted chunks are concatenated into one list:

res.add(a.get(i));

Finally, the resulting array is checked to see whether it is globally sorted.

for(int i = 0; i < res.size() - 1; i++){

if(res.get(i) > res.get(i + 1)){

return false;

}

If no decreasing pair exists, the partition is valid.

Java Solution

class Solution {

int an = 0;

// Generates all possible partitions

public void sol(int[] arr, int ind, List<List<Integer>> chunk) {

// A complete partition has been created

if(ind == arr.length){

// Check whether this partition produces

// the completely sorted array

if(vali(chunk)){

an = Math.max(an, chunk.size());

}

return;

}

// Try every possible ending point

// for the current chunk

for(int i = ind; i < arr.length; i++){

// Create the current chunk

List<Integer> lis = subar(arr, ind, i);

// Choose the chunk

chunk.add(lis);

// Recursively create the remaining chunks

sol(arr, i + 1, chunk);

// Backtrack

chunk.remove(chunk.size() - 1);

}

// Creates a subarray from st to en

public List<Integer> subar(int[] arr, int st, int en){

List<Integer> lis = new ArrayList<>();

for(int i = st; i <= en; i++){

lis.add(arr[i]);

}

return lis;

}

// Checks whether the selected partition is valid

public boolean vali(List<List<Integer>> liss){

List<Integer> res = new ArrayList<>();

// Sort every chunk independently

for(List<Integer> a : liss){

Collections.sort(a);

// Add the sorted chunk to the result

for(int i = 0; i < a.size(); i++){

res.add(a.get(i));

}

// Check whether the final array is sorted

for(int i = 0; i < res.size() - 1; i++){

if(res.get(i) > res.get(i + 1)){

return false;

}

return true;

}

public int maxChunksToSorted(int[] arr){

List<List<Integer>> liss = new ArrayList<>();

sol(arr, 0, liss);

return an;

}

Dry Run

Consider:

arr = [1,0,2,3,4]

One of the partitions generated by recursion is:

[1,0] [2] [3] [4]

The chunks are individually sorted:

[0,1] [2] [3] [4]

After concatenation:

[0,1,2,3,4]

The resulting array is sorted, so the partition is valid.

It contains:

4 chunks

The recursion also examines partitions with fewer chunks, such as:

[1,0,2,3,4]

[1,0] [2,3,4]

[1] [0,2,3,4]

[1,0] [2] [3,4]

Among all valid partitions, the solution keeps the maximum number of chunks using:

an = Math.max(an, chunk.size());

Therefore:

Answer = 4

Why Does the Maximum Number of Chunks Matter?

A partition with fewer chunks can still produce the sorted array.

For example:

[1,0,2,3,4]

can be split as:

[1,0] [2,3,4]

After sorting:

[0,1] [2,3,4]

which produces:

[0,1,2,3,4]

So this is valid.

But it is not the maximum because:

[1,0] [2] [3] [4]

also works and gives more chunks.

Therefore, every valid partition cannot simply be accepted—the number of chunks must also be maximized.

Complexity Analysis

The number of ways to split an array of length n into contiguous chunks is:

2^(n-1)

because every gap between two elements can either contain a partition or not.

For example, with:

[a,b,c]

there are two gaps:

a | b | c

Each gap has two choices, giving:

2² = 4

possible partitions.

For every complete partition, the solution also sorts the chunks and constructs the resulting array.

Therefore, the overall complexity is exponential.

Time Complexity: Approximately O(2^n × n log n)

Space Complexity: Approximately O(n × 2^n) in the worst case because many partition configurations and temporary lists are generated.

Since the given constraint is only:

n <= 10

this brute-force approach is feasible.

A Better Observation

Although recursion works for the small constraint, this problem has a much simpler O(n) greedy solution.

The key observation comes from the fact that the array is a permutation of:

0, 1, 2, ..., n-1

Suppose the current chunk ends at index i.

If the maximum value seen so far is exactly i, then the current elements contain exactly the values that should occupy positions 0 through i.

Therefore, the chunk can safely end at this position.

For example:

arr = [1,0,2,3,4]

Track the maximum:

index value max

0 1 1

1 0 1

2 2 2

3 3 3

4 4 4

Whenever:

max == index

a new chunk can be created.

This happens at:

index 1

index 2

index 3

index 4

So the answer is:

The optimized implementation is:

class Solution {

public int maxChunksToSorted(int[] arr) {

int max = 0;

int chunks = 0;

for(int i = 0; i < arr.length; i++){

max = Math.max(max, arr[i]);

if(max == i){

chunks++;

}

return chunks;

}

This reduces the complexity to:

Time Complexity: O(n)

Space Complexity: O(1)

Interview Tip

When a problem says the array is a permutation from 0 to n-1, that property is usually extremely important.

Instead of immediately trying to generate all possibilities, look for a relationship between:

the current index
the values seen so far
the final sorted position

For this problem, the condition:

maximum value seen so far == current index

means that the current portion contains exactly the values needed for that prefix of the sorted array.

That single observation turns an exponential backtracking solution into a linear greedy solution.

Conclusion

LeetCode 769 is a good example of how the same problem can be approached at different levels.

The recursive solution explores every possible contiguous partition, sorts each chunk, and checks whether the final result is sorted. It is straightforward and works well under the small constraint n <= 10.

However, the permutation property provides a much stronger observation. Whenever the maximum value seen so far equals the current index, a chunk can safely end there.

That leads to a simple:

O(n) time

O(1) space

greedy solution.

The main lesson is to first understand the brute-force structure, then look for properties in the input that can eliminate the need to explore every possibility.

LeetCode 769: Max Chunks To Make Sorted – Java Solution, Approach & Explanation

Introduction

Question Link

Understanding the Problem

Approach: Recursion + Backtracking

Generating the Chunks

Creating a Chunk

Checking a Partition

Java Solution

Dry Run

Why Does the Maximum Number of Chunks Matter?

Complexity Analysis

A Better Observation

Interview Tip

Conclusion

Related Articles

LeetCode 2161: Partition Array According to Given Pivot – Java Easy Stable Partition Solution

Quick Sort Algorithm Explained | Java Implementation, Partition Logic & Complexity

Count the Number of Good Subarrays – Apple OA DSA Problem & Java Solution

Subsets Problem (LeetCode 78) Explained | Recursion, Iterative & Bit Manipulation

Ai Assistant Kas