LeetCode 768: Max Chunks To Make Sorted II

Problem Restatement

We are given an integer array arr.

We want to split it into some number of chunks.

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

The final result must equal the fully sorted version of arr.

Return the maximum number of chunks we can make.

The array may contain duplicate values.

Input and Output

Example function shape:

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

Examples

Example 1:

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

Output:

1

The array is fully reversed.

If we split it into more than one chunk, sorting each chunk separately cannot move the smaller values far enough left.

So the only valid split is the whole array:

[5, 4, 3, 2, 1]

After sorting that chunk:

[1, 2, 3, 4, 5]

Example 2:

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

Output:

4

One best split is:

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

After sorting each chunk:

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

Concatenating gives:

[1, 2, 3, 4, 4]

which equals the fully sorted array.

First Thought: Compare Prefixes

A valid split after index i means:

all values on the left <= all values on the right

So one solution is to precompute:

1. maximum value from the left
2. minimum value from the right

Then a split is valid when:

max_left[i] <= min_right[i + 1]

This works well.

There is also a compact monotonic stack solution that avoids storing two arrays.

Key Insight

Think of each chunk by its maximum value.

If chunks are valid, their maximum values should be non-decreasing from left to right.

For example:

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

The chunk maximums are:

2, 3, 4, 4

This is non-decreasing.

Now suppose we read a new value that is smaller than the maximum of the previous chunk.

Then it cannot start a new chunk. It must be merged with the previous chunk, because after sorting, that smaller value needs to move before the previous larger value.

This is why a monotonic stack works.

The stack stores the maximum value of each chunk.

Stack Behavior

Maintain a stack where each item is the maximum value of one chunk.

For each value x in arr:

If the stack is empty or x >= stack[-1], then x can start a new chunk.

stack.append(x)

If x < stack[-1], then x violates the order between chunks.

We need to merge chunks until the previous chunk maximum is no longer greater than x.

But the merged chunk must keep the largest maximum that was already seen.

So we save the old maximum:

largest = stack.pop()

Then pop while:

stack and stack[-1] > x

Finally, push largest back.

That represents one merged chunk whose maximum is still largest.

Walkthrough

Take:

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

Process values:

Final stack length is 4.

So the answer is:

4

Now take:

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

Every new value is smaller than the current chunk maximum, so all values merge into one chunk.

Final stack:

[5]

Answer:

1

Algorithm

1. Create an empty stack.
2. For each value x in arr:
   1. If the stack is empty or x >= stack[-1], push x.
   2. Otherwise:
      1. Save largest = stack.pop().
      2. Pop while the stack top is greater than x.
      3. Push largest back.
3. Return len(stack).

Correctness

The stack stores the maximum value of each current chunk.

The stack is kept in non-decreasing order. This means the chunks represented by the stack can appear in sorted order after each chunk is sorted.

When a new value x is greater than or equal to the maximum of the previous chunk, it can safely start a new chunk. Sorting this new chunk will not place any value before the previous chunk, because x is not smaller than the previous chunk maximum.

When x is smaller than the previous chunk maximum, x cannot be placed in a separate later chunk. If it were separate, sorting chunks independently would leave the previous larger value before x, which would violate the globally sorted order.

Therefore, x must be merged with the previous chunk. If earlier chunk maximums are also greater than x, those chunks must be merged as well. The algorithm pops exactly those chunks.

The merged chunk maximum is the largest value among the merged chunks, which is the saved value largest. Pushing it back correctly represents the merged chunk.

At the end, every stack item represents one valid chunk, and the chunk maximums are non-decreasing. The algorithm only merges chunks when separation would be invalid, so it preserves as many chunks as possible.

Therefore, the stack length is the maximum number of chunks.

Complexity

Let n = len(arr).

Implementation

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

        for x in arr:
            if not stack or x >= stack[-1]:
                stack.append(x)
                continue

            largest = stack.pop()

            while stack and stack[-1] > x:
                stack.pop()

            stack.append(largest)

        return len(stack)

Code Explanation

The stack stores chunk maximums:

stack = []

If the current value can appear after the previous chunk, we create a new chunk:

if not stack or x >= stack[-1]:
    stack.append(x)
    continue

If x is smaller than the previous chunk maximum, it must merge with earlier chunks.

We save the maximum of the chunk being merged:

largest = stack.pop()

Then we remove every earlier chunk whose maximum is greater than x:

while stack and stack[-1] > x:
    stack.pop()

Finally, we push back the maximum of the merged chunk:

stack.append(largest)

The number of chunks is the number of remaining stack entries:

return len(stack)

Alternative Prefix-Max and Suffix-Min Solution

Another clean solution is to find every valid boundary directly.

A split after index i is valid if every value on the left is less than or equal to every value on the right.

class Solution:
    def maxChunksToSorted(self, arr: list[int]) -> int:
        n = len(arr)

        min_right = [0] * n
        min_right[-1] = arr[-1]

        for i in range(n - 2, -1, -1):
            min_right[i] = min(arr[i], min_right[i + 1])

        answer = 1
        max_left = arr[0]

        for i in range(n - 1):
            max_left = max(max_left, arr[i])

            if max_left <= min_right[i + 1]:
                answer += 1

        return answer

This version is often easier to prove, while the stack version is more space-efficient in practice when there are few chunks.

Testing

def run_tests():
    s = Solution()

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

    print("all tests passed")

run_tests()

Test meaning: