Problem Description

Given an array arr that is a permutation of the numbers 0 to n-1 (where n is the length of the array), your goal is to split the array into the maximum number of "chunks" such that sorting each chunk individually and concatenating them results in a fully sorted array.

You must find the largest number of chunks possible. Each chunk must be a contiguous subarray, and you cannot reuse elements between chunks. The array always contains each number from 0 to n-1 exactly once.

Thought Process

At first glance, you might consider trying every possible way to split the array and check if sorting the chunks gives the sorted array. However, this brute-force approach is inefficient.

Instead, let's think about what it means for a chunk to be "sortable" in isolation. For a chunk ending at index i, if the largest number we've seen so far is exactly i, then all numbers from 0 up to i must have already appeared. That means we can safely split here, because sorting this chunk will put those numbers in their correct place.

The optimization comes from recognizing we only need to track the maximum value we've seen as we scan the array from left to right.

Solution Approach

• Initialize a variable to track the current maximum value seen so far (max_so_far).
• Initialize a counter for the number of chunks (chunks), starting at 0.
• Iterate through the array from left to right:
  • At each index i, update max_so_far to be the maximum of max_so_far and arr[i].
  • If max_so_far == i, it means all numbers from 0 to i are present in the first i+1 elements, and we can make a chunk ending here.
  • Increment chunks each time this condition is met.
• Return the final count of chunks.

This is efficient because it only requires a single pass through the array and constant-time operations at each step.

Example Walkthrough

Let's use the example arr = [1, 0, 2, 3, 4].

• Start with max_so_far = 0, chunks = 0.
• Index 0: arr[0] = 1, max_so_far = max(0,1) = 1. max_so_far != 0, so no chunk yet.
• Index 1: arr[1] = 0, max_so_far = max(1,0) = 1. Now max_so_far == 1, so we can make a chunk ending at index 1 ([1,0]).
• Increment chunks to 1.
• Index 2: arr[2] = 2, max_so_far = max(1,2) = 2. max_so_far == 2, so we can make a chunk ending at index 2 ([2]).
• Increment chunks to 2.
• Index 3: arr[3] = 3, max_so_far = max(2,3) = 3. max_so_far == 3, so we can make a chunk ending at index 3 ([3]).
• Increment chunks to 3.
• Index 4: arr[4] = 4, max_so_far = max(3,4) = 4. max_so_far == 4, so we can make a chunk ending at index 4 ([4]).
• Increment chunks to 4.

The final answer is 4 chunks.

Time and Space Complexity

• Brute-force approach: Trying all possible partitions is exponential in time, specifically O(2^n), since every position could be a split point.
• Optimized approach: The algorithm only iterates through the array once, updating a maximum and a counter, so it is O(n) time and O(1) extra space.

This efficiency comes from realizing we only need to track the current maximum to determine split points.

Summary

The key insight is that you can split the array at position i if all numbers up to i have already appeared. By tracking the running maximum, you can efficiently determine these split points in a single pass. This makes the solution both elegant and optimal for this permutation-based array chunking problem.

Code Implementation

class Solution:
    def maxChunksToSorted(self, arr):
        max_so_far = 0
        chunks = 0
        for i, num in enumerate(arr):
            max_so_far = max(max_so_far, num)
            if max_so_far == i:
                chunks += 1
        return chunks
      

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        int max_so_far = 0, chunks = 0;
        for (int i = 0; i < arr.size(); ++i) {
            max_so_far = max(max_so_far, arr[i]);
            if (max_so_far == i) {
                ++chunks;
            }
        }
        return chunks;
    }
};
      

class Solution {
    public int maxChunksToSorted(int[] arr) {
        int maxSoFar = 0, chunks = 0;
        for (int i = 0; i < arr.length; i++) {
            maxSoFar = Math.max(maxSoFar, arr[i]);
            if (maxSoFar == i) {
                chunks++;
            }
        }
        return chunks;
    }
}
      

var maxChunksToSorted = function(arr) {
    let maxSoFar = 0, chunks = 0;
    for (let i = 0; i < arr.length; i++) {
        maxSoFar = Math.max(maxSoFar, arr[i]);
        if (maxSoFar === i) {
            chunks++;
        }
    }
    return chunks;
};