Max Chunks To Make Sorted

Max Chunks To Make Sorted

What is this problem about?

The Max Chunks To Make Sorted problem gives you an array arr of length n that represents a permutation of the integers in the range [0, n - 1]. You must split the array into some number of contiguous "chunks" (partitions). The rule is: if you sort each individual chunk in ascending order and then concatenate them back together, the entire array must end up perfectly sorted. Your goal is to return the maximum number of chunks you can create.

Why is this asked in interviews?

This problem is a brilliant test of logical deduction and array properties. Interviewers ask it because candidates who try to simulate the sorting process will create overly complex $O(N^2)$ solutions. Candidates who understand the properties of a permutation can solve it in a highly elegant $O(N)$ pass. It evaluates your ability to track maximums and recognize alignment states.

Algorithmic pattern used

This problem uses a Greedy / Running Maximum pattern. Because the array is a permutation of [0, n - 1], the perfectly sorted array will simply have the value i at index i. Therefore, as we iterate through the array, we keep track of the maximum value seen so far. If the running maximum is exactly equal to the current index, it means all the numbers required to fill the positions up to index have been encountered! We can safely make a cut (create a chunk) right at this index.

Example explanation

Array: [1, 0, 2, 3, 4]

• Index 0: value 1. max_seen = 1. max_seen != index (1 != 0). No chunk.
• Index 1: value 0. max_seen = 1. max_seen == index (1 == 1). All numbers from 0 to 1 are in this block. Cut! Chunk count = 1.
• Index 2: value 2. max_seen = 2. max_seen == index (2 == 2). Cut! Chunk count = 2.
• Index 3: value 3. max_seen = 3. max_seen == index (3 == 3). Cut! Chunk count = 3.
• Index 4: value 4. max_seen = 4. max_seen == index (4 == 4). Cut! Chunk count = 4. Total maximum chunks = 4. (Chunks are [1, 0], [2], [3], [4]).

Common mistakes candidates make

A common mistake is trying to track the minimum value as well, or attempting to use a Monotonic Stack, which overcomplicates the logic. Because the values are strictly 0 to n - 1, the running maximum is the only variable you need to track. If the max value matches the index, the math guarantees that all smaller required values are trapped behind it.

Interview preparation tip

When tackling the Max Chunks To Make Sorted interview question, pay very close attention to the constraint: "permutation of integers [0, n - 1]". Whenever an array's values directly correspond to its valid indices, you have a massive mathematical advantage. Track the max and check if it aligns with the index—it's one of the cleanest $O(N)$ tricks in array problems.