# Max Chunks To Make Sorted
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/max-chunks-to-make-sorted)
Canonical: https://scaleengineer.com/dsa/problems/max-chunks-to-make-sorted
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Stack, Monotonic Stack
**Companies:** [Poshmark](https://scaleengineer.com/companies/poshmark)
---
## Problem
You are given an integer array `arr` of length `n` that represents a permutation of the integers in the range `[0, n - 1]`.

We split `arr` into some number of **chunks** (i.e., partitions), and individually sort each chunk. After concatenating them, the result should equal the sorted array.

Return _the largest number of chunks we can make to sort the array_.

**Example 1:**

**Input:** arr = [4,3,2,1,0]
**Output:** 1
**Explanation:**
Splitting into two or more chunks will not return the required result.
For example, splitting into [4, 3], [2, 1, 0] will result in [3, 4, 0, 1, 2], which isn't sorted.

**Example 2:**

**Input:** arr = [1,0,2,3,4]
**Output:** 4
**Explanation:**
We can split into two chunks, such as [1, 0], [2, 3, 4].
However, splitting into [1, 0], [2], [3], [4] is the highest number of chunks possible.

**Constraints:**

* `n == arr.length`
* `1 <= n <= 10`
* `0 <= arr[i] < n`
* All the elements of `arr` are **unique**.

# Approaches
## Greedy Approach with Chunk Validation
This approach iterates through the array to find the end of each chunk. We greedily try to make each chunk as small as possible to maximize the total number of chunks. Starting from the beginning of the current segment, we expand the potential chunk one element at a time. At each step, we check if the current subarray forms a "valid" chunk. A chunk is valid if the set of its elements corresponds exactly to the set of its indices in the final sorted array.
**Time:** O(n^2). The outer `while` loop and the inner `for` loop result in a nested iteration over the array elements. In the worst case (e.g., `arr = [n-1, n-2, ..., 0]`), the inner loop runs `n` times for the first and only chunk. · **Space:** O(1). We only use a few variables to store sums and counters, regardless of the input size.
**Pros:** Conceptually straightforward greedy approach.; Doesn't require complex data structures.
**Cons:** Inefficient due to the nested loop structure, leading to a quadratic time complexity.
### Explanation
We can define a chunk starting at index `i`. We then search for the smallest ending index `j >= i` such that the subarray `arr[i...j]` is a permutation of the numbers `{i, i+1, ..., j}`. To check this condition efficiently, we can use the property that since all numbers are unique, if the sum of elements in `arr[i...j]` is equal to the sum of numbers from `i` to `j`, the condition is met. The algorithm proceeds as follows:

- Start with the first chunk at index `i = 0`.
- Iterate `j` from `i` to `n-1`. In this inner loop, maintain the sum of elements in `arr[i...j]` (`current_sum`) and the sum of indices from `i` to `j` (`expected_sum`).
- When `current_sum == expected_sum`, we have found the smallest possible valid chunk `arr[i...j]`.
- We increment our chunk count, and start searching for the next chunk from index `j + 1`.
- We repeat this process until the entire array is partitioned.

```java
class Solution {
    public int maxChunksToSorted(int[] arr) {
        int n = arr.length;
        int chunks = 0;
        int i = 0;
        while (i < n) {
            long currentSum = 0;
            long expectedSum = 0;
            for (int j = i; j < n; j++) {
                currentSum += arr[j];
                expectedSum += j;
                if (currentSum == expectedSum) {
                    chunks++;
                    i = j + 1;
                    break;
                }
            }
        }
        return chunks;
    }
}
```
### Algorithm
- Initialize `chunks = 0` and the starting index of the current segment `i = 0`.
- Loop while `i < n`:
  - Initialize `current_sum = 0` and `expected_sum = 0`.
  - Start an inner loop with `j` from `i` to `n-1`.
    - Add `arr[j]` to `current_sum`.
    - Add `j` to `expected_sum`.
    - If `current_sum` equals `expected_sum`, a valid chunk boundary is found at `j`.
      - Increment `chunks`.
      - Update `i` to `j + 1` to start searching for the next chunk.
      - Break the inner loop.
- Return `chunks`.

## Single-Pass Greedy Approach
A more efficient approach observes a key property of the problem. A split is possible after an index `i` if and only if the maximum element in the prefix `arr[0...i]` is exactly `i`. If this condition holds, it guarantees that the prefix `arr[0...i]` contains all numbers from `0` to `i` and no other numbers, which is the requirement for a valid first chunk in a partition.
**Time:** O(n). We iterate through the array only once. · **Space:** O(1). We only use a constant amount of extra space for variables.
**Pros:** Highly efficient with linear time complexity.; Simple to implement.; Optimal solution for this problem.
**Cons:** The reasoning behind why it works might be less intuitive at first glance compared to the O(n^2) approach.
### Explanation
The logic is that if we can partition the array into `k` chunks, `C_1, C_2, ..., C_k`, where `C_1 = arr[0...i_1]`, `C_2 = arr[i_1+1...i_2]`, etc., then after sorting, `sorted(C_1)` must be `[0, ..., i_1]`, `sorted(C_2)` must be `[i_1+1, ..., i_2]`, and so on. This implies that the set of elements in `arr[0...i_1]` must be `{0, ..., i_1}`. A simple way to check this is to verify if `max(arr[0...i_1]) == i_1`. Since `arr` is a permutation of `[0, ..., n-1]`, if the maximum element in the first `i_1+1` positions is `i_1`, then these `i_1+1` elements must be exactly `{0, ..., i_1}`. We can iterate through the array, keeping track of the maximum value encountered so far (`max_so_far`). Whenever `max_so_far` is equal to the current index `i`, it signifies that we have found a valid chunk boundary. This logic extends to subsequent chunks as well, because if `max(arr[0...i]) == i`, then the elements in `arr[0...i]` are `{0...i}`, which means the elements in the rest of the array `arr[i+1...n-1]` must be `{i+1...n-1}`.

```java
class Solution {
    public int maxChunksToSorted(int[] arr) {
        int chunks = 0;
        int maxSoFar = 0;
        for (int i = 0; i < arr.length; i++) {
            maxSoFar = Math.max(maxSoFar, arr[i]);
            if (maxSoFar == i) {
                chunks++;
            }
        }
        return chunks;
    }
}
```
### Algorithm
- Initialize `chunks = 0` and `max_so_far = 0`.
- Iterate through the array `arr` with index `i` from `0` to `n-1`.
  - Update `max_so_far` with the maximum value between the current `max_so_far` and `arr[i]`.
  - If `max_so_far` is equal to the current index `i`, it means the prefix `arr[0...i]` contains exactly the numbers from `0` to `i`. This forms a valid chunk.
    - Increment `chunks`.
- Return the total `chunks`.

# Solutions
### Java

```java
class Solution {
public
  int maxChunksToSorted(int[] arr) {
    int ans = 0, mx = 0;
    for (int i = 0; i < arr.length; ++i) {
      mx = Math.max(mx, arr[i]);
      if (i == mx) {
        ++ans;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxChunksToSorted(vector<int> &arr) {
    int ans = 0, mx = 0;
    for (int i = 0; i < arr.size(); ++i) {
      mx = max(mx, arr[i]);
      ans += i == mx;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maxChunksToSorted(self, arr: List[int]) -> int: mx = ans = 0 for i, v in enumerate(arr): mx = max(mx, v) if i == mx: ans += 1 return ans

```