Max Chunks To Make Sorted II

You are given an integer array arr. 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 = [5,4,3,2,1]
Output: 1
Explanation:
Splitting into two or more chunks will not return the required result.
For example, splitting into [5, 4], [3, 2, 1] will result in [4, 5, 1, 2, 3], which isn't sorted.

Example 2:

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

Constraints:

• 1 <= arr.length <= 2000
• 0 <= arr[i] <= 10^8

def max_chunks_to_sorted(arr):
    """Calculates the maximum number of chunks that can be made to sort the array.

    Args:
        arr (list of int): The input array.

    Returns:
        int: The largest number of chunks we can make to sort the array.
    """
    n = len(arr)
    max_so_far = 0
    chunks = 0

    for i in range(n):
        max_so_far = max(max_so_far, arr[i])
        if max_so_far == i:
            chunks += 1

    return chunks


# Example Usage
arr1 = [5, 4, 3, 2, 1]
print(f"Input: {arr1}, Output: {max_chunks_to_sorted(arr1)}")

arr2 = [2, 1, 3, 4, 4]
print(f"Input: {arr2}, Output: {max_chunks_to_sorted(arr2)}")

arr3 = [0, 2, 1, 4, 3, 5, 7, 6, 9, 8]
print(f"Input: {arr3}, Output: {max_chunks_to_sorted(arr3)}")

Explanation:

The core idea is to keep track of the maximum element encountered so far as we iterate through the array. If at any index i, the maximum element encountered so far is equal to i, it means all elements to the left of i are less than or equal to i. Therefore, we can form a chunk at this index.

1. Initialization:

   • max_so_far = 0: This variable keeps track of the maximum element encountered so far.
   • chunks = 0: This variable counts the number of chunks.

2. Iteration:

   • Iterate through the array arr from left to right.
   • Update max_so_far at each index i to be the maximum of max_so_far and arr[i].
   • If max_so_far == i, it means that all elements from arr[0] to arr[i] are less than or equal to i. In other words, the maximum element in the subarray arr[0...i] is i. This satisfies the condition for creating a chunk because if we sort this chunk, it will contain the elements 0, 1, 2, ..., i in some order.
   • Increment chunks by 1.

3. Return:

   • Finally, return the value of chunks, which represents the maximum number of chunks.

Example Walkthrough:

Consider the array arr = [2, 1, 3, 4, 4].

• i = 0: max_so_far = max(0, arr[0]) = 2. Since max_so_far (2) != i (0), we don't form a chunk.
• i = 1: max_so_far = max(2, arr[1]) = 2. Since max_so_far (2) != i (1), we don't form a chunk.
• i = 2: max_so_far = max(2, arr[2]) = 3. Since max_so_far (3) != i (2), we don't form a chunk.
• i = 3: max_so_far = max(3, arr[3]) = 4. Since max_so_far (4) != i (3), we don't form a chunk.
• i = 4: max_so_far = max(4, arr[4]) = 4. Since max_so_far (4) == i (4), we form a chunk.

Therefore, the chunks will be [2, 1], [3], [4], [4], so the output is 4

Big O Time Complexity Analysis:

The time complexity is O(n), where n is the length of the array. This is because we iterate through the array once.

Big O Space Complexity Analysis:

The space complexity is O(1), because we only use a constant amount of extra space to store variables like max_so_far and chunks.

Edge Cases:

1. Empty Array: If the array is empty, the function should return 0 because there are no chunks to be made.
2. Array with one element: If the array has one element, the function should return 1 because the entire array can be considered as a single chunk.
3. Array already sorted: If the array is already sorted in ascending order from 0 to n-1, the function should return n because each element can be considered as a separate chunk.
4. Array sorted in descending order: If the array is sorted in descending order, only one chunk is possible.