Max Chunks To Make Sorted

Share

Split array (0..n-1 permutation) into max chunks so each sorted separately gives sorted array.

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

Solution Approach

Greedy: at each index, if max so far equals index, a valid chunk ends here.

  • Track running maximum
  • At each index i: if max == i, increment chunk count
  • Return chunk count
Java
public int maxChunksToSorted(int[] arr) {
    int max = 0, chunks = 0;
    for (int i = 0; i < arr.length; i++) {
        max = Math.max(max, arr[i]);
        if (max == i) chunks++;
    }
    return chunks;
}
  • Time Complexity: O(n)
  • Space Complexity: O(1)