Domain 2MediumMEDIUM

Max Chunks To Make Sorted

Given a permutation of numbers from 0 to n-1, partition the array into maximum chunks such that sorting each chunk individually results in a fully sorted array.

Domain: medium•Updated: 2026-08-31
#Greedy#Array#O(N)#O(1)

Problem Breakdown

We are given an integer array arr which is guaranteed to be a permutation of numbers from 00 to n−1n-1. The objective is to partition this array into the maximum number of contiguous subarrays (“chunks”). Each chunk must satisfy the condition that if we sort it individually and concatenate all chunks, the final concatenated result matches the sorted version of arr (which is simply [0, 1, ..., n-1]).

Inputs:

  • arr: A list containing a permutation of integers [0,…,arr.length−1][0, \dots, arr.length - 1].
  • Length range: [1,10][1, 10] per constraints, though the algorithm is efficient for much larger inputs.

Outputs:

  • An integer representing the maximum number of chunks possible.

Implicit Constraints & Edge Cases:

  • Permutation Property: Since it is a permutation of 0 to n-1, all elements are unique and non-negative. This allows us to rely on value-to-index mapping logic without handling duplicates or arbitrary values.
  • Empty Input: The constraints state length ≥1\ge 1, so we do not need to handle empty lists explicitly, though the code handles it gracefully if needed.
  • Single Element: If arr has one element (e.g., [0]), it is trivially sorted; the answer should be 11.

Intuition

Consider the target state of the array: a fully sorted permutation where index ii holds value ii. When we process elements from left to right, any valid chunk ending at index i must contain all values that belong in indices ≤i\le i.

Since the input is a permutation of 0…n−10 \dots n-1, if we encounter an element with value greater than the current index i, it implies some larger number exists before its correct sorted position. However, specifically for this problem: If at any point during our scan from left to right, the maximum value seen so far (max_val) equals the current index i (where 0≤i<n0 \le i < n), we can conclude that all numbers required for indices 00 through ii are present in the subarray processed up to this point. No number greater than i has appeared yet, and since values are unique, no number less than or equal to i is missing. Thus, a valid cut (chunk boundary) can be made here. This greedy property allows us to count chunks without sorting or backtracking.

Approach

  1. Initialize a counter for the total number of chunks (chunks = 0) and track the maximum value seen so far in the current partition (current_max).
  2. Iterate through the array using index i from 00 to n−1n-1.
  3. Update current_max with the value at the current position arr[i].
  4. Check if current_max == i:
    • If true, it means all elements required for indices up to i are contained within the array segment ending at i. We can increment our chunk count and effectively “close” this chunk boundary.
  5. Return the total count of chunks found after iterating through the entire array.

Complexity Analysis

  • Time Complexity: O(N)O(N), where NN is the length of the input array. The algorithm performs a single pass through the list with constant-time operations inside the loop (comparison and increment). This meets the optimal requirement for this problem type.
  • Space Complexity: O(1)O(1). We only use two variables (chunks and current_max) regardless of the input size, avoiding any auxiliary data structures like sorting or hash maps.

Solution

def maxChunksToSorted(arr):
    """
    Calculates the maximum number of chunks to make sorted array.
    
    Args:
        arr (List[int]): A permutation of 0..n-1
        
    Returns:
        int: Maximum number of chunks
    """
    chunks = 0
    current_max = -1
    
    # Iterate through each element in the array
    for i, num in enumerate(arr):
        # Update the maximum value seen so far. 
        if num > current_max:
            current_max = num
        
        # If max_val equals index i, it means all numbers from 0 to i 
        # have been encountered in the subarray ending at i.
        # This forms a valid chunk boundary because no element larger than 'i' exists before this point.
        if current_max == i:
            chunks += 1
            
    return chunks

# Example usage matching problem description
print(maxChunksToSorted([4,3,2,1,0]))   # Output: 1
print(maxChunksToSorted([1,0,2,3,4]))  # Output: 4

Edge Cases Handled

  • Single Element Array: The loop runs once. current_max becomes the element value (which is 00). Since index i=0i=0, condition holds (max_val == i), returns 11. Correct.
  • Already Sorted Input ([0, 1, 2]): At every step arr[i] == i, so current_max equals i. Returns NN (length of array). This represents splitting into individual elements (maximum chunks). Correct.
  • Reverse Sorted Input ([4,3,2,1,0]): The maximum value grows until the end (max=4max=4 at index 4). Only at index 4 does current_max == i. Returns 11. Correct.