LeetCode 769 - Max Chunks To Make Sorted

This problem is asking us to determine the maximum number of contiguous chunks into which we can split an array such that sorting each chunk individually and concatenating them results in a fully sorted array.

leetcodemediumarraystackgreedysortingmonotonic-stack

LeetCode Problem 769

Difficulty: 🟡 Medium
Topics: Array, Stack, Greedy, Sorting, Monotonic Stack

Solution

Problem Understanding

This problem is asking us to determine the maximum number of contiguous chunks into which we can split an array such that sorting each chunk individually and concatenating them results in a fully sorted array. The input array arr is a permutation of integers from 0 to n-1, meaning it contains each integer exactly once. The output is a single integer representing the largest number of chunks possible under this constraint.

The key points to note are that the array elements are unique, the values directly correspond to their positions in the sorted array, and the array length n is small (up to 10). These constraints imply that we can rely on element indices to reason about whether a split is valid and that we can consider approaches that iterate over the array without worrying about excessive computational cost.

Edge cases to be aware of include arrays that are already sorted (each element could potentially be its own chunk), arrays sorted in reverse order (only one chunk is possible), and minimal arrays with a single element (trivially one chunk).

Approaches

The brute-force approach would attempt every possible partition of the array into chunks, sort each chunk individually, concatenate the sorted chunks, and check if the result equals the sorted array. This guarantees correctness because it exhaustively checks all possible combinations. However, this approach is exponentially slow, with a time complexity of O(2^n) for partitioning possibilities and additional overhead for sorting, making it impractical for even moderate values of n.

The optimal approach relies on a key observation: a valid split point occurs when the maximum value encountered in the current prefix of the array is equal to the last index of that prefix. Formally, if max(arr[0..i]) == i, then we can split after index i. This works because the array contains all integers from 0 to n-1. When this condition is satisfied, all values within the current chunk are exactly those required to sort into that position, ensuring correctness. We can solve the problem in a single pass using a simple prefix maximum calculation.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n * n log n) O(n) Generates all partitions, sorts each, checks concatenation
Optimal O(n) O(1) Single pass, track prefix maximum, split when max equals index

Algorithm Walkthrough

  1. Initialize a variable max_seen to track the maximum value encountered in the array so far and a counter chunks to count valid chunks.
  2. Iterate over the array from the first element to the last.
  3. For each element arr[i], update max_seen to be the maximum of max_seen and arr[i].
  4. If max_seen equals the current index i, increment the chunks counter. This indicates that all numbers up to i are exactly the numbers that should occupy this portion of the sorted array, so we can safely split here.
  5. After iterating through the array, return the total chunks count.

Why it works: The key invariant is that when max_seen == i, the current segment contains all integers in a contiguous range [0..i]. Sorting this segment locally will place all numbers in their correct final positions, ensuring correctness. The greedy approach works because we only split when the prefix is self-contained in terms of sorted order, which maximizes the number of chunks.

Python Solution

from typing import List

class Solution:
    def maxChunksToSorted(self, arr: List[int]) -> int:
        max_seen = 0
        chunks = 0
        for i, val in enumerate(arr):
            max_seen = max(max_seen, val)
            if max_seen == i:
                chunks += 1
        return chunks

In this implementation, max_seen keeps track of the highest value seen so far in the array. As we iterate through the array, whenever the max_seen matches the current index i, it means all elements in this segment are exactly those needed to form a sorted subarray, so we increment the chunk count. This matches the algorithm walkthrough exactly.

Go Solution

func maxChunksToSorted(arr []int) int {
    maxSeen := 0
    chunks := 0
    for i, val := range arr {
        if val > maxSeen {
            maxSeen = val
        }
        if maxSeen == i {
            chunks++
        }
    }
    return chunks
}

In Go, we similarly track maxSeen and iterate using range. Since Go does not have a built-in max function for integers, we use a simple comparison. Other than that, the logic is identical to Python, and slices handle array access seamlessly.

Worked Examples

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

i val max_seen chunks
0 4 4 0
1 3 4 0
2 2 4 0
3 1 4 0
4 0 4 1

We cannot split until the last element. Output is 1.

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

i val max_seen chunks
0 1 1 0
1 0 1 1
2 2 2 2
3 3 3 3
4 4 4 4

We can split after every valid prefix. Output is 4.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Single pass through the array to compute prefix maximum and check split points
Space O(1) Only two integer variables are used regardless of input size

Because n is small and the algorithm is linear, this solution is highly efficient and optimal.

Test Cases

# Provided examples
assert Solution().maxChunksToSorted([4,3,2,1,0]) == 1  # reverse sorted
assert Solution().maxChunksToSorted([1,0,2,3,4]) == 4  # mixed but can split early

# Edge cases
assert Solution().maxChunksToSorted([0]) == 1  # single element
assert Solution().maxChunksToSorted([0,1,2,3,4]) == 5  # already sorted
assert Solution().maxChunksToSorted([2,0,1,4,3]) == 2  # chunks need to be larger than 1
Test Why
[4,3,2,1,0] Reverse order forces single chunk
[1,0,2,3,4] Can split multiple times for max chunks
[0] Single element array
[0,1,2,3,4] Already sorted, every element can be a chunk
[2,0,1,4,3] Requires non-trivial chunk sizes

Edge Cases

The first important edge case is a single-element array. Since the array contains only one number, the algorithm correctly identifies it as a chunk by checking max_seen == i.

The second edge case is a fully sorted array. Every element can be its own chunk, and our prefix maximum logic naturally increments chunks at each index because max_seen will always equal i.

The third edge case is a reverse-sorted array, where no intermediate splits are valid until the last element. The algorithm correctly accumulates the maximum without incrementing chunks until the very end, producing a single chunk. This ensures the greedy approach does not incorrectly split too early.