LeetCode 769: Max Chunks To Make Sorted

Problem Restatement

We are given an array arr of length n.

The array is a permutation of integers from 0 to n - 1.

We want to split arr into the maximum number of chunks.

Then we sort each chunk individually and concatenate the chunks back in the same order.

The final result must equal the fully sorted array.

Return the largest number of chunks we can make. The original problem states that arr is a permutation of [0, n - 1].

Input and Output

Example function shape:

def maxChunksToSorted(arr: list[int]) -> int:
    ...

Examples

Example 1:

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

Output:

1

The array is fully reversed.

If we split it into multiple chunks, small values on the right cannot move far enough left after sorting only inside their chunks.

So the only valid split is the whole array:

[4, 3, 2, 1, 0]

After sorting:

[0, 1, 2, 3, 4]

Example 2:

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

Output:

4

One maximum split is:

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

After sorting each chunk:

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

Concatenating gives:

[0, 1, 2, 3, 4]

So the answer is 4.

First Thought: Compare With Sorted Array

The fully sorted version of a permutation from 0 to n - 1 is:

[0, 1, 2, 3, ..., n - 1]

A chunk ending at index i is valid if all numbers needed for sorted positions 0 through i have already appeared.

Since the array is a permutation of 0 to n - 1, this condition becomes simple:

maximum value seen so far == current index

When this is true, the current prefix can be sorted independently.

Key Insight

While scanning from left to right, keep the maximum value seen so far.

Call it:

max_seen

At index i, if:

max_seen == i

then all numbers in the prefix must be exactly:

0, 1, 2, ..., i

Why?

There are i + 1 numbers in the prefix.

All values are unique.

If the largest value is i, then every value in the prefix is between 0 and i.

So the prefix contains exactly the numbers needed for the first i + 1 sorted positions.

That means we can cut a chunk here.

Walkthrough

Take:

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

Scan from left to right:

So we get 4 chunks:

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

Now take:

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

Scan:

Only one cut is possible, so the answer is 1.

Algorithm

1. Initialize:
   1. max_seen = 0
   2. chunks = 0
2. Scan the array with index i and value x.
3. Update:

max_seen = max(max_seen, x)

4. If max_seen == i, then the prefix up to i forms a valid chunk, so increment chunks.
5. Return chunks.

Correctness

At any index i, max_seen is the maximum value in the current prefix arr[0:i + 1].

If max_seen == i, then all values in this prefix are at most i. Since the array is a permutation and the prefix has exactly i + 1 distinct values, the prefix must contain exactly the values 0 through i. Sorting this prefix will produce exactly the first i + 1 values of the fully sorted array, so cutting here is valid.

If max_seen > i, then some value in the prefix belongs to a later sorted position. Therefore, this prefix cannot be closed as a chunk yet, because sorting it alone would leave that large value before smaller values that appear later.

The algorithm cuts exactly when the current prefix can form a valid sorted prefix. Each cut is the earliest valid cut after the previous one, so it maximizes the number of chunks.

Therefore, the algorithm returns the largest possible number of chunks.

Complexity

Let n = len(arr).

Implementation

class Solution:
    def maxChunksToSorted(self, arr: list[int]) -> int:
        chunks = 0
        max_seen = 0

        for i, x in enumerate(arr):
            max_seen = max(max_seen, x)

            if max_seen == i:
                chunks += 1

        return chunks

Code Explanation

We count how many valid chunk boundaries we find:

chunks = 0

The variable max_seen stores the largest value in the current scanned prefix:

max_seen = 0

As we scan:

for i, x in enumerate(arr):

we update the maximum:

max_seen = max(max_seen, x)

If this maximum equals the current index:

if max_seen == i:

then the prefix contains exactly the values that belong in this prefix after sorting.

So we can close a chunk:

chunks += 1

Finally:

return chunks

returns the maximum chunk count.

Relation to LeetCode 768

LeetCode 768 allows duplicate values and arbitrary integer values.

This problem is simpler because arr is a permutation of 0 to n - 1.

That special constraint is what makes the condition:

max_seen == i

sufficient.

For arrays with duplicates, use the monotonic stack or prefix-max/suffix-min method from LeetCode 768.

Testing

def run_tests():
    s = Solution()

    assert s.maxChunksToSorted([4, 3, 2, 1, 0]) == 1
    assert s.maxChunksToSorted([1, 0, 2, 3, 4]) == 4
    assert s.maxChunksToSorted([0, 1, 2, 3, 4]) == 5
    assert s.maxChunksToSorted([2, 0, 1, 3]) == 2
    assert s.maxChunksToSorted([0]) == 1
    assert s.maxChunksToSorted([1, 2, 0, 3]) == 2

    print("all tests passed")

run_tests()

Test meaning: