768. Max Chunks To Make Sorted II
Tags: leetcode, hard
Published: 2023-06-17 15:08:48

Problem Source: [Max Chunks To Make Sorted II](https://leetcode.com/problems/max-chunks-to-make-sorted-ii/description/)

<strong>1. Understand the problem</strong>

We need to be able to determine how to split the array into chunks such that when sort them and concatenate create a sorted array.

With this, we will have an observation:
- If we split the array into chunks and pick 2 consecutive ones `chunk(i)` and `chunk(i + 1)`, then the maximum value of `chunk(i)` should be `<=` the minimum value of `chunk(i + 1)`. This will ensure the sorted order being maintain for the resulting array.

<strong>2. Solving the problem</strong>
With the observation above, we can have an algorithm:
- Keep track of the maximum value of the current chunk we are in, whenever there is a value that is larger than that maximum one, update the maximum and increase the count (increase the number of chunks)

For example:
`arr = [2, 1, 3, 4, 4]`

For chunk `[2, 1]`, the maximum value is 2. When visit element `3`, because `2` < `3` we can update the maximum value and increase the number of chunks. At this point, we have 2 chunks: `[2, 1]`, and `[3]`.

Follow the same process, we have `3` < `4`, so new chunk created. And `4` <= `4`, new chunk created.

At the end, we have 4 chunks: `[2, 1]`, `[3]`, `[4]`, and `[4]`.

Sounds good? Yeah, but not enough. What is wrong with this? 
The mistake is that we create a new chunk immediately when seeing an element with value larger than the current one. Why is this an issue?

Try this: `arr = [5, 4, 3, 6, 3]`. If we apply the algorithm above, we will have 2 chunks: `[5, 4, 3]`, and `[6, 3]` since `5` < `6`. But this is wrong, right?

<strong>3. Final Solution</strong>
The issue we have is that we do not know what comes after the element that has a higher value than the current one.

In our case where: `arr = [5, 4, 3, 6, 3]`, We do not know that there is a number `3` comes after `6`.

So, in order to solve that, we need to be able to keep track of the values after a specific element, in our case, we want to know what is the minimum value that comes after the element.

With `arr = [5, 4, 3, 6, 3]` the array containing minimums value is: `min = [3, 3, 3, 3, 3]` this is because there is a `3` to the right of `5`, and so are with `4`, `3`, `6`, and `3`.

Lets try one more time. With `arr = [5,1,1,8,1,6,5,9,7,8]`, the mins values will be: `mins = [1, 1, 1, 1, 1, 5, 5, 7, 7, 7]`.

So now that we have the mins value, what next? We will apply the same algorithm discussed in step <strong>2</strong> but with a small modification:
1. We construct the mins value array. We can do this using DP while traversing in reverse order. You will see this in the code
2. Start with the first element in `arr` while keeping track of the index of it. Let's store the current max value in `currentMax`
3. For i in range(arr.length):
    + If mins[i] >= currentMax: increase the count by 1 (with `count` is the result of the number of chunks we need)
    + Update `currentMax` = Math.max(currentMax, arr[i])

This algorithm will ensure that we can both keep track of the maximum value of the current chunks and also make sure that we can create a new chunk when knowing there is no smaller values after a certain element.

So here is the code in Java:
```java
class Solution {
    public int maxChunksToSorted(int[] arr) {
        // DP to find the mins value
        int[] min = new int[arr.length];
        min[arr.length - 1] = arr[arr.length - 1];
        for (int i = arr.length - 2; i >= 0; i--) {
            min[i] = Math.min(arr[i], min[i + 1]);
        }


        int count = 1;
        int current = arr[0];

        for (int i = 1; i < arr.length; i ++) {
            if (current <= min[i]) {
                count ++;
            }

            current = Math.max(current, arr[i]);
        }

        return count;
    }
}
```