Max Chunks To Make Sorted II: Prefix Max and Suffix Min

You are given an integer array arr. You need to split it into the maximum number of chunks such that sorting each chunk individually and concatenating them produces the fully sorted array. Return that maximum number of chunks.

This is LeetCode 768: Max Chunks To Make Sorted II, a hard problem. The array can contain duplicates (unlike the easier version, LeetCode 769). You need to find the maximum number of chunks you can split the array into such that sorting each chunk individually produces the same result as sorting the entire array.

Examples:

• [2,1,3,4,4] can be split into [2,1], [3], [4], [4] for 4 chunks
• [5,4,3,2,1] can only be 1 chunk (the whole array)

The approach

The key observation is that you can place a chunk boundary after index i when every value in the left portion is at most every value in the right portion. In other words, the maximum of arr[0..i] must be at most the minimum of arr[i+1..n-1]. If that condition holds, sorting the left side will never produce values that belong on the right side, and vice versa.

To check this efficiently, you precompute two arrays:

• prefix_max: prefix_max[i] stores the maximum of arr[0..i].
• suffix_min: suffix_min[i] stores the minimum of arr[i..n-1].

Then you scan from left to right. At each index i (from 0 to n-2), if prefix_max[i] is at most suffix_min[i+1], you have a valid chunk boundary. The total number of chunks is the number of boundaries plus one (the final chunk after the last boundary, or the whole array if no boundaries exist).

Algorithm:

1. Build prefix_max array where prefix_max[i] = max(arr[0..i])
2. Build suffix_min array where suffix_min[i] = min(arr[i..n-1])
3. Count chunk boundaries: for each i from 0 to n-2, if prefix_max[i] is at most suffix_min[i+1], that is a valid boundary
4. Return boundaries + 1 (the last chunk after the final boundary)

Visual walkthrough

Python solution

def maxChunksToSorted(arr):
    n = len(arr)
    prefix_max = [0] * n
    suffix_min = [0] * n

    prefix_max[0] = arr[0]
    for i in range(1, n):
        prefix_max[i] = max(prefix_max[i - 1], arr[i])

    suffix_min[n - 1] = arr[n - 1]
    for i in range(n - 2, -1, -1):
        suffix_min[i] = min(suffix_min[i + 1], arr[i])

    chunks = 1
    for i in range(n - 1):
        if prefix_max[i] <= suffix_min[i + 1]:
            chunks += 1

    return chunks

Here is what each piece does:

1. Initialize two arrays of size n, prefix_max and suffix_min, both filled with zeros.
2. Forward pass builds prefix_max. Starting from index 0, each entry records the running maximum seen so far. After this pass, prefix_max[i] tells you the largest value in the subarray from the start through index i.
3. Backward pass builds suffix_min. Starting from index n-1, each entry records the running minimum seen so far going right to left. After this pass, suffix_min[i] tells you the smallest value in the subarray from index i through the end.
4. Boundary scan checks each index from 0 to n-2. If the max of the left portion (prefix_max[i]) is at most the min of the right portion (suffix_min[i+1]), you can safely cut here. Each valid cut adds one more chunk.
5. Return the chunk count, which starts at 1 because there is always at least one chunk (the whole array).

Complexity analysis

Time: O(n) three passes through the array (one forward, one backward, one boundary scan).

Space: O(n) for the prefix max and suffix min arrays.

Building blocks

Prefix max / suffix min arrays

Prefix and suffix arrays are one of the most reusable patterns in array problems. The idea is to precompute cumulative information from one direction so you can answer range queries in O(1). In this problem, prefix_max[i] answers "what is the largest value in arr[0..i]?" and suffix_min[i] answers "what is the smallest value in arr[i..n-1]?" Together they let you check the chunk boundary condition at every index without re-scanning subarrays.

You will see the same technique in Trapping Rain Water (prefix max and suffix max of heights), Product of Array Except Self (prefix product and suffix product), and Candy (forward and backward constraint passes). Once you recognize the pattern, you can apply it mechanically.

Chunk boundary detection

The invariant is simple: a valid chunk boundary exists after index i when everything to the left is at most everything to the right. If the maximum on the left exceeds any value on the right, those two sides cannot be sorted independently, so they must belong to the same chunk.

This invariant also explains why the greedy approach works. You are placing as many boundaries as possible, and each boundary is independent: the condition depends only on prefix_max and suffix_min at that index, not on where other boundaries are placed.

Edge cases

Before submitting, make sure your solution handles these:

• Already sorted [1, 2, 3, 4]: every index is a valid boundary, so chunks = n. Each element forms its own chunk.
• Reverse sorted [4, 3, 2, 1]: prefix_max is always greater than suffix_min at every index, so chunks = 1. The entire array is one chunk.
• All duplicates [3, 3, 3]: prefix_max = suffix_min = [3, 3, 3]. Every boundary is valid, so chunks = n.
• Single element [5]: no boundary scan needed. Return 1.

From understanding to recall

You have read through the prefix max and suffix min approach. The algorithm is clean: build two arrays, scan for boundaries, count them. But writing it from scratch under pressure requires remembering the details. Which direction does each array scan? What comparison do you use at each boundary? Does the chunk count start at 0 or 1?

Spaced repetition locks in those details. You practice writing the three passes from memory at increasing intervals. After a few rounds, you see "split array into sortable chunks" and the prefix_max/suffix_min skeleton flows out automatically.

Related posts

• Max Chunks To Make Sorted - The simpler version where elements are a permutation of 0 to n-1
• Sort Colors - Another array partitioning problem
• Largest Rectangle in Histogram - Uses monotonic stack, an alternative approach for this problem