Max Chunks To Make Sorted

Medium
398.

Max Chunks To Make Sorted

Max Chunks To Make Sorted is a medium coding problem on arrays, sorting and greedy, asked in Amazon and Google interviews.

You are given an array arr that is a permutation of [0, 1, …, n-1].

Split it into the largest possible number of contiguous chunks such that sorting each chunk individually and concatenating them yields the fully sorted array. Return that number of chunks.

Example 1

Input
arr = [4,3,2,1,0]
Output
1
Explanation
Any split would leave the array unsorted.

Example 2

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

Example 3

Input
arr = [0,1,2]
Output
3

Constraints

  • 1 <= arr.length <= 40
  • arr is a permutation of [0, 1, …, arr.length - 1].
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @return {number}
 */
var maxChunksToSorted = function(arr) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Max Chunks To Make Sorted — Solution in Python, Java & C++

Max Chunks To Make Sorted solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Max Chunks To Make Sorted is a medium coding problem on arrays, sorting and greedy, asked in Amazon and Google interviews.

Problem statement

You are given an array arr that is a permutation of [0, 1, …, n-1].

Split it into the largest possible number of contiguous chunks such that sorting each chunk individually and concatenating them yields the fully sorted array. Return that number of chunks.

Example 1

Input: arr = [4,3,2,1,0]
Output: 1
Explanation: Any split would leave the array unsorted.

Example 2

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

Example 3

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

Constraints

  • 1 <= arr.length <= 40
  • arr is a permutation of [0, 1, …, arr.length - 1].

Hints for Max Chunks To Make Sorted

  1. Hint 1

    A chunk can end at index i only if it holds exactly the values 0…i in some order.

  2. Hint 2

    Because the array is a permutation, that happens precisely when the maximum of the prefix equals i.

  3. Hint 3

    Sweep once, tracking the running maximum, and count every index where it matches.

How to solve Max Chunks To Make Sorted

A chunk can end at i exactly when the prefix holds the values 0..i, which for a permutation means the running maximum equals i.

Approach

  1. Sweep with running = max(running, arr[i]).
  2. Count every i where running == i.

Why it works

A permutation prefix of length i + 1 with maximum i must contain exactly 0..i, so it sorts into place independently of the rest; cutting at every such point maximises the count.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • For non-permutation inputs the general version compares prefix max with suffix min.

Reference solution

Python

def maxChunksToSorted(arr) -> int:
    chunks = 0
    running = -1
    for i, x in enumerate(arr):
        running = max(running, x)
        if running == i:
            chunks += 1
    return chunks

Java

public static int maxChunksToSorted(int[] arr) {
    int chunks = 0, running = -1;
    for (int i = 0; i < arr.length; i++) {
        running = Math.max(running, arr[i]);
        if (running == i) chunks++;
    }
    return chunks;
}

C++

int maxChunksToSorted(vector<int>& arr) {
    int chunks = 0, running = -1;
    for (int i = 0; i < (int) arr.size(); i++) {
        running = max(running, arr[i]);
        if (running == i) chunks++;
    }
    return chunks;
}

JavaScript

var maxChunksToSorted = function(arr) {
    let chunks = 0, running = -1;
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] > running) running = arr[i];
        if (running === i) chunks++;
    }
    return chunks;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms