Max Chunks To Make Sorted

Problem Statement

Given an integer array arr (of length n), which is a permutation of the integers in the range [0, n - 1], our goal is to split this array into several non-overlapping "chunks" (or partitions). Each chunk, when sorted independently and then concatenated back together, should form the correctly sorted array (i.e., [0, 1, 2, ..., n-1]). The challenge is to determine the maximum number of chunks we can create from the array such that when they are separately sorted and reassembled, they still produce the sorted array.

Examples

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.

Approach and Intuition

1. Each index in the array can be used as a guide to determine a valid chunk boundary. If a chunk can be confirmed as individually sortable within its segment to align with its final sorted state, it can be considered as a chunk. The goal is to maximize such chunks.
2. Start traversing the array and maintain a record of the maximum element observed till the current index. If at any index, the maximum element observed so far is equal to the current index (as the array is a permutation of numbers from 0 to n-1), a chunk boundary can be established.
3. Splitting logic can be deduced from the examples:
   • For arr = [4,3,2,1,0], despite the reverse order, the whole array is a single chunk because any internal partitioning breaks the consecutive sequence due to the disorder.
   • For arr = [1,0,2,3,4], smaller chunks like [1, 0], [2], [3], and [4] can be sorted independently and still form part of the larger sorted sequence.
4. Understanding that each valid partition point (or chunk boundary) is where the array’s element values can align sequentially and up to that point all numbers are present eases the decision for a split.
5. With small maximum array size constraints (max.length = 10), this method is computationally feasible. For each observation, check if the maximum value equals the current index, incrementing a chunk count whenever this holds true.

The challenge primarily revolves around recognizing these partition points and ensuring that at each potential chunk end, the maximum of the included elements matches the criteria for forming a contiguous sorted sequence after that point.

Solutions

class Solution {
public:
    int calculateMaxChunks(vector<int>& numbers) {
        int length = numbers.size();
        int countChunks = 0, highest = 0;
    
        for (int index = 0; index < length; index++) {
            highest = max(highest, numbers[index]);
            if (highest == index) {
                countChunks++;
            }
        }
    
        return countChunks;
    }
};