In LeetCode 769: Max Chunks To Make Sorted, we are given an integer array arr of length n that represents a permutation of the integers in the range [0, n - 1]. We want to partition arr into the maximum number of contiguous chunks (subarrays) such that sorting each chunk independently and concatenating the results produces the fully sorted array [0, 1, 2, ..., n - 1].

Problem Statement and Examples

Because arr is a permutation of 0 through n - 1, we already know the exact final destination index of every element in the globally sorted array: integer v must end up at index v.

Example 1: Strictly Reversed Array

Input:  arr = [4, 3, 2, 1, 0]
Output: 1
Explanation:
The value 4 at index 0 must travel all the way to index 4, and 0 at index 4 must travel to index 0.
Splitting into two or more chunks (e.g., [4, 3] and [2, 1, 0]) yields [3, 4, 0, 1, 2], which is unsorted.

Example 2: Local Swap with Independent Tail

Input:  arr = [1, 0, 2, 3, 4]
Output: 4
Explanation:
We can partition the array into four independent chunks: [1, 0], [2], [3], [4].
Sorting each chunk yields [0, 1] + [2] + [3] + [4] = [0, 1, 2, 3, 4].

Mathematical Proof: The Prefix Maximum Permutation Invariant

Why can we solve this problem with greedy partitioning in a single pass? Consider a prefix subarray arr[0..i] of length i + 1. When the entire array is sorted, the first i + 1 slots must contain the exact set of integers {0, 1, ..., i}.

Since all elements in arr are distinct non-negative integers from [0, n - 1], the prefix arr[0..i] contains the exact set {0, 1, ..., i} if and only if the prefix maximum across arr[0..i] equals i:

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

• If prefixMax > i, at least one element in arr[0..i] belongs to an index strictly to the right of i, so we cannot close the chunk at index i.
• If prefixMax == i, all i + 1 distinct integers in arr[0..i] are bounded within [0, i]. Closing a chunk boundary immediately at index i is always optimal because smaller valid chunks never obstruct subsequent splits.

C++20 Implementation (Count & Partition Reconstruction)

Below are two C++20 functions: maxChunksToSorted computes the maximum chunk count in O(n) time and O(1) auxiliary space using the permutation invariant, while extractSortedChunks materializes the actual subarray partitions for debugging and visualization:

#include <algorithm>
#include <iostream>
#include <vector>

int maxChunksToSorted(const std::vector<int>& arr) {
    int chunks = 0;
    int prefixMax = 0;

    for (int i = 0; i < static_cast<int>(arr.size()); ++i) {
        prefixMax = std::max(prefixMax, arr[i]);
        if (prefixMax == i) {
            ++chunks;
        }
    }
    return chunks;
}

std::vector<std::vector<int>> extractSortedChunks(const std::vector<int>& arr) {
    std::vector<std::vector<int>> partitions;
    int chunkStart = 0;
    int prefixMax = 0;

    for (int i = 0; i < static_cast<int>(arr.size()); ++i) {
        prefixMax = std::max(prefixMax, arr[i]);
        if (prefixMax == i) {
            partitions.emplace_back(arr.begin() + chunkStart, arr.begin() + i + 1);
            chunkStart = i + 1;
        }
    }
    return partitions;
}

int main() {
    std::cout << maxChunksToSorted({4, 3, 2, 1, 0}) << "\n"; // 1
    std::cout << maxChunksToSorted({1, 0, 2, 3, 4}) << "\n"; // 4
    std::cout << maxChunksToSorted({1, 0, 3, 2, 4}) << "\n"; // 3
    return 0;
}

TypeScript Implementation & Monotonic Stack Generalization

What if the input array contains arbitrary integers or duplicates rather than a strict permutation of [0, n - 1] (LeetCode 768: Max Chunks To Make Sorted II)? In that generalized setting, we maintain a monotonic stack of chunk maximums: whenever a new element x is smaller than the current top of the stack, we pop and merge all preceding chunks whose maximum exceeds x, then push the original maximum back onto the stack.

// Optimal O(n) time, O(1) space for permutation [0..n-1] (LeetCode 769)
export function maxChunksToSortedPermutation(arr: ReadonlyArray<number>): number {
  let chunks = 0;
  let prefixMax = -1;

  for (let i = 0; i < arr.length; i++) {
    if (arr[i] > prefixMax) {
      prefixMax = arr[i];
    }
    if (prefixMax === i) {
      chunks++;
    }
  }
  return chunks;
}

// Generalized O(n) monotonic stack for arbitrary integers & duplicates (LeetCode 768)
export function maxChunksToSortedGeneral(arr: ReadonlyArray<number>): number {
  const chunkMaxStack: number[] = [];

  for (const value of arr) {
    if (chunkMaxStack.length === 0 || value >= chunkMaxStack[chunkMaxStack.length - 1]) {
      chunkMaxStack.push(value);
    } else {
      const largestInMergedChunk = chunkMaxStack.pop()!;
      while (
        chunkMaxStack.length > 0 &&
        chunkMaxStack[chunkMaxStack.length - 1] > value
      ) {
        chunkMaxStack.pop();
      }
      chunkMaxStack.push(largestInMergedChunk);
    }
  }
  return chunkMaxStack.length;
}

Complexity Comparison