Max Chunks to Make Sorted — Greedy Running Maximum [LeetCode 769]

Problem Statement#

LeetCode 769 — Max Chunks to Make Sorted (Medium)

You are given an integer array arr of length n that represents a permutation of the integers in the range [0, n - 1]. We split arr into some number of chunks (i.e., partitions), and individually sort each chunk. After concatenating them, the result should equal the sorted array. Return the largest number of chunks we can make to sort the array.

Constraints:

• n == arr.length
• 1 <= n <= 10
• 0 <= arr[i] < n
• All the integers of arr are unique.

Example 1:

Input:  arr = [4, 3, 2, 1, 0]
Output: 1
Explanation: Splitting into any chunk other than the whole array will not produce the sorted array.

Example 2:

Input:  arr = [1, 0, 2, 3, 4]
Output: 4
Explanation: Split into [1,0], [2], [3], [4].
             After sorting each: [0,1], [2], [3], [4] → [0,1,2,3,4]. ✓

Example 3:

Input:  arr = [0, 1, 2, 3, 4]
Output: 5
Explanation: Already sorted — each element is its own chunk.

Why This Problem Matters#

Max Chunks to Make Sorted is a beautifully simple greedy problem that tests a deep insight: when can you safely "cut" an array into a partition without breaking the global sorted order? The answer — the running maximum equals the current index — is concise, correct, and non-obvious enough to distinguish candidates who truly understand array invariants.

Amazon and Google use this problem because it models real partitioning systems: dividing a dataset into blocks that can be sorted independently (distributed sorting), partitioning a stream into segments where each segment's maximum is bounded by its last index. The problem is also a natural precursor to harder problems like Max Chunks to Make Sorted II (LeetCode 768), which extends to non-distinct elements and requires tracking both the prefix max and suffix min.

The problem is often presented as a warm-up in interview sessions because the solution code is short but the explanation requires clear reasoning about invariants. Interviewers award high marks for candidates who can articulate why max_so_far == i implies a valid chunk boundary, not just that it works.

The Core Insight#

Since arr is a permutation of [0, n-1], the sorted array has value i at index i. For a chunk [start, end] to be independently sortable into the correct global position, every element in the chunk must land in indices [start, end] after sorting. Since arr contains all values 0 to n-1 exactly once, this is equivalent to: the maximum element in the chunk equals the chunk's last index.

Why? If max(arr[start..end]) == end, then:

• All elements in the chunk are in [0, end] (no element exceeds the last position of the chunk).
• The chunk has exactly end - start + 1 elements.
• Therefore all elements in [start, end] are within [start, end] (by the permutation property and the max constraint).

So a chunk boundary can be placed after index i if and only if max(arr[0..i]) == i. The running maximum tells us exactly when this condition is met.

Algorithm: Track the running maximum. Increment the chunk count whenever the running maximum equals the current index.

Visual Dry Run#

arr = [1, 0, 2, 3, 4]
 
i=0 (val=1): max_so_far=1, i=0 → 1 != 0 → no cut
i=1 (val=0): max_so_far=1, i=1 → 1 == 1 → CUT! chunks=1
i=2 (val=2): max_so_far=2, i=2 → 2 == 2 → CUT! chunks=2
i=3 (val=3): max_so_far=3, i=3 → 3 == 3 → CUT! chunks=3
i=4 (val=4): max_so_far=4, i=4 → 4 == 4 → CUT! chunks=4
 
Answer = 4  ✓

Trace for the descending case:

arr = [4, 3, 2, 1, 0]
 
i=0 (val=4): max_so_far=4, i=0 → 4 != 0
i=1 (val=3): max_so_far=4, i=1 → 4 != 1
i=2 (val=2): max_so_far=4, i=2 → 4 != 2
i=3 (val=1): max_so_far=4, i=3 → 4 != 3
i=4 (val=0): max_so_far=4, i=4 → 4 == 4 → CUT! chunks=1
 
Answer = 1  ✓  (entire array is one chunk)

Running max table for Example 2:

Solution (Optimal)#

class Solution:
    def maxChunksToSorted(self, arr: list[int]) -> int:
        chunks = 0
        max_so_far = 0  # running maximum from left to current index
 
        for i, val in enumerate(arr):
            max_so_far = max(max_so_far, val)
 
            # If max element seen so far equals current index,
            # all elements in this chunk belong exactly to [start, i]
            if max_so_far == i:
                chunks += 1
 
        return chunks

var maxChunksToSorted = function(arr) {
    let chunks = 0;
    let maxSoFar = 0;  // running maximum
 
    for (let i = 0; i < arr.length; i++) {
        maxSoFar = Math.max(maxSoFar, arr[i]);
 
        // Chunk boundary: all elements in [0..i] can sort to [0..i]
        if (maxSoFar === i) {
            chunks++;
        }
    }
 
    return chunks;
};

Complexity Analysis:

Common Mistakes#

• Using the current value instead of the running maximum. The condition checks max(arr[0..i]) == i, not arr[i] == i. A single element can satisfy arr[i] == i even though a larger element before it disqualifies that chunk.
• Counting boundaries instead of chunks. If you count boundary crossings (the number of times max_so_far == i holds), you get the chunk count directly. But if you count boundary positions and then add 1, you can get off-by-one.
• Starting max_so_far at arr[0] instead of 0. If arr[0] = 0, you get a chunk immediately. Initialising max_so_far = 0 and updating at each step (including i=0) handles this naturally.
• Confusing this with LeetCode 768 (Max Chunks to Make Sorted II). In LC 768, the array is not a permutation — elements can repeat and range is unconstrained. The simple max_so_far == i check does not work; you need to track both prefix max and suffix min.

Follow-up Questions#

Q: What is the minimum number of chunks? Always 1 — the entire array is one valid chunk that sorts to the sorted array.

Q: How does this change for LeetCode 768 (Max Chunks to Make Sorted II) where elements are not a permutation? You cannot use max_so_far == i since elements can exceed n-1. Instead, compute the prefix maximum array and suffix minimum array. A chunk boundary exists at i where prefix_max[i] <= suffix_min[i+1]. This requires two passes and O(n) space.

Q: What if we want to find the actual chunk boundaries, not just the count? Track the start of each chunk. When max_so_far == i, record [start, i] as a chunk and set start = i + 1.

Q: What if the array is not a permutation but elements are bounded by n? The simple greedy may fail. Use the prefix max / suffix min approach from LC 768 for a general solution.

Q: Can you solve this in O(1) space? Yes — the solution above already uses O(1) space. The only variable needed is max_so_far.

Q: What is the connection between this problem and merge sort? The chunks correspond to natural merge sort segments. When max_so_far == i, you have identified a "run" that sorts independently. This is related to natural merge sort's detection of monotonic runs, though the constraint here (permutation) is more specific.

Related Problems#

• LeetCode 768 — Max Chunks to Make Sorted II: Generalised to non-permutation arrays — requires prefix max and suffix min.
• LeetCode 1. Two Sum / Prefix techniques: Running maximum and prefix approaches generalise to many problems.
• LeetCode 84 — Largest Rectangle in Histogram: Monotonic stack for finding optimal segment boundaries.
• LeetCode 56 — Merge Intervals: Finding merge boundaries in sorted intervals — related partitioning concept.
• LeetCode 134 — Gas Station: Greedy restart when balance goes negative — similar "reset boundary" pattern.
• LeetCode 135 — Candy: Two-pass greedy for constraint satisfaction — same family of problems requiring careful boundary reasoning.

Interview Tips#

• State the invariant first: "A cut after index i is valid iff max(arr[0..i]) == i."
• Justify with the permutation property in one sentence; do not skip this step.
• Mention that the trick fails for the harder LeetCode 768 variant, and explain prefix-max/suffix-min as a fallback.

Key Takeaways#

• The array is a permutation of [0, n-1], so the sorted array places value i at index i.
• A valid chunk boundary at i exists iff the running maximum equals i.
• One linear pass with O(1) memory is optimal; sorting or partition enumeration is wasteful.
• Initialise max_so_far to 0 and update before the comparison so index 0 is handled naturally.
• For LeetCode 768 (non-permutation), switch to prefix-max combined with suffix-min.
• The same "running max equals index" pattern appears in problems about monotonic runs and natural merge sort segments.
• Distinguishing permutation versus general array assumptions is the main interview trap; always confirm with the interviewer.