# 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

| Item | Meaning |
|---|---|
| Input | An integer array `arr` |
| Output | Maximum number of valid chunks |
| Operation | Sort each chunk independently |
| Requirement | Concatenating sorted chunks must equal `sorted(arr)` |
| Duplicate values | Allowed |

Example function shape:

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

## Examples

Example 1:

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

Output:

```python
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:

```python
[5, 4, 3, 2, 1]
```

After sorting that chunk:

```python
[1, 2, 3, 4, 5]
```

Example 2:

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

Output:

```python
4
```

One best split is:

```text
[2, 1] [3] [4] [4]
```

After sorting each chunk:

```text
[1, 2] [3] [4] [4]
```

Concatenating gives:

```python
[1, 2, 3, 4, 4]
```

which equals the fully sorted array.

## First Thought: Compare Prefixes

A valid split after index `i` means:

```text
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:

```python
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:

```text
[2, 1] [3] [4] [4]
```

The chunk maximums are:

```text
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.

```python
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:

```python
largest = stack.pop()
```

Then pop while:

```python
stack and stack[-1] > x
```

Finally, push `largest` back.

That represents one merged chunk whose maximum is still `largest`.

## Walkthrough

Take:

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

Process values:

| Value | Stack | Meaning |
|---:|---|---|
| `2` | `[2]` | First chunk max is `2` |
| `1` | `[2]` | Merge `1` into previous chunk |
| `3` | `[2, 3]` | New chunk |
| `4` | `[2, 3, 4]` | New chunk |
| `4` | `[2, 3, 4, 4]` | New chunk |

Final stack length is `4`.

So the answer is:

```python
4
```

Now take:

```python
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:

```python
[5]
```

Answer:

```python
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)`.

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each value is pushed once and popped at most once |
| Space | `O(n)` | The stack may store one item per chunk |

## Implementation

```python
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:

```python
stack = []
```

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

```python
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:

```python
largest = stack.pop()
```

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

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

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

```python
stack.append(largest)
```

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

```python
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.

```python
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

```python
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:

| Test | Why |
|---|---|
| Reversed array | Everything must be one chunk |
| Main duplicate example | Confirms maximum split count |
| Duplicates mixed with smaller values | Confirms merging logic with equal values |
| Several partial chunks | Confirms repeated merging |
| Single value | One chunk |
| Already sorted | Every value can be its own chunk |