Max Chunks To Make Sorted: Running Maximum

May 22, 20264 min read

leetcodeproblemmediumarrayssortingstacks

You are given an array arr that is a permutation of [0, 1, ..., n-1]. You need to split it into the maximum number of "chunks" (partitions) so that sorting each chunk individually produces the fully sorted array. This is LeetCode 769: Max Chunks To Make Sorted, a medium problem that rewards you for noticing how permutation structure connects to a simple greedy scan.

The array is a permutation of integers from 0 to n-1. You want to split it into the maximum number of chunks such that sorting each chunk produces the sorted array [0, 1, 2, ..., n-1].

Examples:

[1,0,2,3,4] gives 4 chunks: [1,0], [2], [3], [4]
[4,3,2,1,0] gives 1 chunk (the whole array)

arr = [1, 0, 2, 3, 4] splits into 4 chunks. Sorting each chunk independently produces [0, 1, 2, 3, 4].

The approach

The key insight comes from the permutation constraint. Since the array contains exactly the values 0 through n-1, each chunk arr[l..r] when sorted must equal [l, l+1, ..., r]. For that to work, every value in the range [l, r] must appear within that subarray. In other words, no value inside the chunk can "belong" to a position outside it, and no value outside can belong inside it.

Here is the trick: if max(arr[0..i]) == i, then all values from 0 through i are contained within arr[0..i]. Why? Because the values are a permutation, so they are all distinct. If the maximum is i, there are i+1 values in arr[0..i], and they are all in the range [0, i]. The only way that works is if they are exactly the set {0, 1, ..., i}. That means arr[0..i] can be sorted into [0, 1, ..., i] on its own, and everything after index i can form its own independent group.

Algorithm:

Track max_so_far as you scan left to right
At each index i, update max_so_far = max(max_so_far, arr[i])
If max_so_far == i, increment the chunk count
Return the chunk count

Practice this pattern

Visual walkthrough

Step 1: i = 0, arr[0] = 1. max_so_far = max(0, 1) = 1.

max_so_far (1) != i (0). The value 1 belongs ahead, so we cannot close a chunk here.

Step 2: i = 1, arr[1] = 0. max_so_far = max(1, 0) = 1.

max_so_far (1) == i (1). All values 0 and 1 are within arr[0..1]. Close chunk! chunks = 1.

Step 3: i = 2, arr[2] = 2. max_so_far = max(1, 2) = 2.

max_so_far (2) == i (2). Value 2 is exactly where it belongs. Close chunk! chunks = 2.

Step 4: i = 3, arr[3] = 3. max_so_far = max(2, 3) = 3.

max_so_far (3) == i (3). Another single-element chunk. chunks = 3.

Step 5: i = 4, arr[4] = 4. max_so_far = max(3, 4) = 4.

max_so_far (4) == i (4). Final chunk closed. Total chunks = 4.

Python solution

def maxChunksToSorted(arr):
    chunks = 0
    max_so_far = 0

    for i, val in enumerate(arr):
        max_so_far = max(max_so_far, val)
        if max_so_far == i:
            chunks += 1

    return chunks

Here is what each piece does:

max_so_far starts at 0 and tracks the largest value seen so far in the scan.
At each index i, you update max_so_far with the current value.
When max_so_far == i, you know all values 0 through i are contained in arr[0..i], so you can close a chunk and increment the count.
After the loop, chunks holds the maximum number of chunks.

This works because the values form a permutation. If max_so_far == i, there are exactly i+1 values in positions 0 through i, all in the range [0, i]. Since they are distinct (permutation), they must be exactly {0, 1, ..., i}. That guarantees the chunk sorts correctly on its own.

Drill this solution with spaced repetition

Complexity analysis

Time: O(n) single pass.

Space: O(1) only tracking the max and count.

Aspect	Value
Time	O(n)
Space	O(1)
Difficulty	Medium

Building blocks

Running maximum

Tracking the running maximum as you scan is one of the most common greedy primitives. You maintain a single variable that stores the largest value encountered so far. At each step you compare the new value to the stored maximum and update if needed. This same pattern appears in Jump Game (tracking farthest reachable index), Best Time to Buy and Sell Stock (tracking running minimum for the complementary direction), and trapping rain water (prefix and suffix maximums).

Permutation properties

The permutation constraint is what makes this problem solvable in O(1) space. Because every value from 0 to n-1 appears exactly once, the maximum of a prefix tells you everything about its contents. If the max is i after scanning i+1 elements, those elements must be {0, 1, ..., i}. Without the permutation guarantee, you would need more information (like prefix sums or sorted comparisons) to verify chunk validity, which is exactly what the harder version of this problem (Max Chunks To Make Sorted II) requires.

Edge cases

Already sorted [0, 1, 2, 3]: every element satisfies max_so_far == i, so you get n chunks (each element is its own chunk).
Reverse sorted [4, 3, 2, 1, 0]: max_so_far stays at 4 for the entire scan. The only time max_so_far == i is at the last index, giving 1 chunk.
Single element [0]: max_so_far = 0 == i = 0 immediately, so you get 1 chunk.
Two elements swapped [1, 0, 2, 3]: max_so_far becomes 1 at index 0 (no boundary), then at index 1 max_so_far is still 1 which equals i, creating the first chunk [1, 0]. The remaining elements each form their own chunk.

From understanding to recall

The logic here is only a few lines, but the reasoning behind it is what you need to internalize. Practice explaining why max_so_far == i guarantees a valid chunk boundary. Then practice writing the loop from scratch. The running-maximum pattern and the permutation insight are the two building blocks to drill. Once they are automatic, you can apply them to variations like Max Chunks To Make Sorted II and Partition Labels without rethinking the fundamentals.

Try CodeBricks free

Max Chunks To Make Sorted II - The harder version allowing duplicates, requires prefix max and suffix min
Jump Game - Another greedy array scan tracking a running value
Sort Colors - Array partitioning with invariant tracking