Max Chunks To Make Sorted - Leetcode Solution

The Max Chunks To Make Sorted problem on LeetCode asks us to find the maximum number of chunks that can be formed to sort an array of distinct integers.

To solve this problem, we can use a simple approach where we iterate over the array and keep track of the maximum value of the elements seen so far. We can then compare this maximum value with the current index and increment the count of chunks if the maximum value is equal to the current index.

Here is the step-by-step approach to solve this problem:

1. Initialize a variable called count to 0 which will store the number of chunks.
2. Initialize a variable called max_val to 0 which will store the maximum value seen so far.
3. Loop through the array and do the following: a. Update the max_val variable by taking the maximum of the current element and the max_val. b. If the max_val is equal to the current index i, increment the count variable and reset the max_val to 0.
4. Return the count variable, which will be the maximum number of chunks that can be formed.

Here is the Python code for the above approach:

def maxChunksToSorted(arr):
    count = 0
    max_val = 0
    for i in range(len(arr)):
        max_val = max(max_val, arr[i])
        if max_val == i:
            count += 1
            max_val = 0
    return count

Let's consider an example to understand how the above code works:

Example:

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

Initially, count = 0 and max_val = 0.

When i = 0, arr[i] = 4, max_val = 4 which is not equal to i, so we don't increment the count.

When i = 1, arr[i] = 3, max_val = 4 which is not equal to i, so we don't increment the count.

When i = 2, arr[i] = 2, max_val = 4 which is not equal to i, so we don't increment the count.

When i = 3, arr[i] = 1, max_val = 4 which is not equal to i, so we don't increment the count.

When i = 4, arr[i] = 0, max_val = 4 which is equal to i, so we increment the count to 1 and reset the max_val to 0.

Therefore, the maximum number of chunks that can be formed is 1.

The time complexity of this approach is O(n) where n is the length of the array.

1