Problem Recap:

We are given an array arr of length n

The goal is to split the array into the maximum number of chunks such that sorting each chunk individually and concatenating the results will produce a completely sorted array.

Method 1: Using Running Sums (Anagram-Based Partitioning)

Intuition:

The key observation is that the sum of elements in a chunk from the input array should match the sum of elements in the corresponding sorted range. This is because the sum ensures that the composition of elements in the chunk matches the sorted array's chunk, making them "anagrams" of each other.

Approach:

1. Cumulative Sum Matching:

   • Compute a running total (sum1) for the current input array.

   • Compute another running total (sum2) for the expected sorted array indices (from to ).

     00

     n−1n-1

   • At each index, if sum1 == sum2, the current chunk is valid because all elements are in their correct sorted positions when combined.

2. Increment Chunk Count:
   • Whenever the running sums match, it signifies that the elements up to this point can form one valid chunk. Increment the chunk counter.
3. Return Total Chunks:
   • At the end of the iteration, the number of chunks gives the result.

Code:

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        int n = arr.size();
        int chunks = 0;
        int sum1 = 0, sum2 = 0;

        for (int i = 0; i < n; i++) {
            sum1 += arr[i];
            sum2 += i; // Expected element in sorted array is i (0 to n-1)

            if (sum1 == sum2) {
                chunks++;
            }
        }

        return chunks;
    }
};

Example Walkthrough:

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

1. Initialization: sum1 = 0, sum2 = 0, chunks = 0.
2. Iteration:
   • i=0i = 0: sum1 = 1, sum2 = 0 → Not equal.
   • i=1i = 1: sum1 = 1, sum2 = 1 → Equal → chunks = 1.
   • i=2i = 2: sum1 = 3, sum2 = 3 → Equal → chunks = 2.
   • i=3i = 3: sum1 = 6, sum2 = 6 → Equal → chunks = 3.
   • i=4i = 4: sum1 = 10, sum2 = 10 → Equal → chunks = 4.
3. Output: chunks = 4.

Time Complexity:

• O(n)O(n): Single pass through the array.

• Space Complexity: .

  O(1)O(1)

Method 2: Using Greedy Approach (Max Element Seen)

Intuition:

Another key observation is that the largest number seen so far in the array dictates whether a chunk can be formed. Specifically:

• At any index , if the largest number encountered so far is equal to , all numbers from the start of this chunk to can be sorted in-place to match the sorted array

Approach:

1. Track the Maximum Element Seen So Far:
   • Use a variable max_seen to keep track of the largest number encountered in the array as we iterate.
2. Check Chunk Validity:

   • At each index , check if max_seen == i.

     ii

   • If true, it means all elements in the current chunk are in their correct positions relative to the sorted array, so we can form a chunk.

3. Increment Chunk Count:
   • Whenever the condition holds, increment the chunk counter.
4. Return Total Chunks:
   • The total count of chunks gives the result.

Code:

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        int count = 0;
        int max_seen = 0;

        for (int i = 0; i < arr.size(); i++) {
            max_seen = max(max_seen, arr[i]);
            if (max_seen == i)
                count++;
        }

        return count;
    }
};

Example Walkthrough:

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

1. Initialization: count = 0, max_seen = 0.
2. Iteration:
   • i=0i = 0: max_seen = max(0, 1) = 1 → Not equal to i.
   • i=1i = 1: max_seen = max(1, 0) = 1 → Equal to i → count = 1.
   • i=2i = 2: max_seen = max(1, 2) = 2 → Equal to i → count = 2.
   • i=3i = 3: max_seen = max(2, 3) = 3 → Equal to i → count = 3.
   • i=4i = 4: max_seen = max(3, 4) = 4 → Equal to i → count = 4.
3. Output: count = 4.

Time Complexity:

• O(n)O(n): Single pass through the array.

• Space Complexity: .

  O(1)O(1)

Comparison of Approaches:

Thought Process Summary:

1. Understand the Problem:
   • Chunks must individually sort to match the global sorted array.
   • Explore patterns in how indices and elements align.
2. Choose an Approach:
   • Use cumulative sums if you think in terms of composition (anagrams).
   • Use max-seen logic if you think in terms of greedy bounds.
3. Optimize:

   • Both approaches achieve O(n) , but method 2 is simpler to implement and debug.

HAPPY CODING