# 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

| Item | Meaning |
|---|---|
| Input | A permutation array `arr` |
| Output | Maximum number of valid chunks |
| Operation | Sort each chunk independently |
| Requirement | Concatenating sorted chunks must produce the sorted array |
| Important constraint | `arr` contains each number from `0` to `n - 1` exactly once |

Example function shape:

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

## Examples

Example 1:

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

Output:

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

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

After sorting:

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

Example 2:

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

Output:

```python
4
```

One maximum split is:

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

After sorting each chunk:

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

Concatenating gives:

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

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

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

```python
max_seen
```

At index `i`, if:

```python
max_seen == i
```

then all numbers in the prefix must be exactly:

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

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

Scan from left to right:

| Index | Value | `max_seen` | Can cut? |
|---:|---:|---:|---|
| `0` | `1` | `1` | No, `max_seen != index` |
| `1` | `0` | `1` | Yes |
| `2` | `2` | `2` | Yes |
| `3` | `3` | `3` | Yes |
| `4` | `4` | `4` | Yes |

So we get `4` chunks:

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

Now take:

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

Scan:

| Index | Value | `max_seen` | Can cut? |
|---:|---:|---:|---|
| `0` | `4` | `4` | No |
| `1` | `3` | `4` | No |
| `2` | `2` | `4` | No |
| `3` | `1` | `4` | No |
| `4` | `0` | `4` | Yes |

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:

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

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We scan the array once |
| Space | `O(1)` | Only two integer variables are used |

## Implementation

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

```python
chunks = 0
```

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

```python
max_seen = 0
```

As we scan:

```python
for i, x in enumerate(arr):
```

we update the maximum:

```python
max_seen = max(max_seen, x)
```

If this maximum equals the current index:

```python
if max_seen == i:
```

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

So we can close a chunk:

```python
chunks += 1
```

Finally:

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

```python
max_seen == i
```

sufficient.

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

## Testing

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

| Test | Why |
|---|---|
| Reversed array | Only one chunk works |
| Main example | Confirms multiple chunks |
| Already sorted | Every element can be its own chunk |
| `[2,0,1,3]` | First three values must stay together |
| Single value | One chunk |
| `[1,2,0,3]` | Delayed `0` forces merge |