768. Max Chunks To Make Sorted II

Problem Source: Max Chunks To Make Sorted II

1. Understand the problem

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.

2. Solving the problem
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?

3. Final Solution
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 2 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:

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;
    }
}