768. Max Chunks

Max Chunks To Make Sorted II

This problem carries a very peculiar feeling for me: a sense that things have changed while the problem remains the same.

I solved it for the first time in late 2024.

Coming back in early 2026, I got AC again.

But these two solutions are based on different data structures.

I. Late 2024: Prefix and Suffix

Sword vs. Shield

Let's first think about two adjacent chunks.

After sorting each individually, they can be concatenated into a sorted array.

What does this imply? Quite obvious:

$\max(Chunk_{left}) \leq \min(Chunk_{right})$

Think of $\max(Chunk_{left})$ as a sword 🗡️

and $\min(Chunk_{right})$ as a shield 🛡.

For a shield to remain unbroken,

its weakest point must be no weaker than the sharpest tip of any sword.

Scan Right Then Left

So for an array $nums$ of length $n$ (the problem calls it $arr$, but I prefer $nums$),

for every index $i$ satisfying $1 \leq i < n$, we check:

Does $\max(nums[:i]) \leq \min(nums[i:])$ hold?

If so, index $i$ is a cut point, meaning the array can be split into two chunks at index $i$,

and sorting each chunk separately then concatenating will yield a sorted result.

This means we need to first scan left,

building a prefix_maxs array recording each $\max(nums[:i])$,

then scan back from the right, tracking $\min(nums[i:])$ with suffix_min.

Whenever $\max(nums[:i]) \leq \min(nums[i:])$ holds, increment max_chunks by 1.

But remember:

max_chunks starts at 1, not 0

Even a strictly decreasing $nums$ can count as one chunk.

C++

#include <vector>
using namespace std;

int findMaxSortableChunks(vector<int>& nums) {
    vector<int> prefixMaxs; // Max of each nums[:(i + 1)th idx].

    for (const auto& num : nums) {
        if (prefixMaxs.empty()) {
            prefixMaxs.push_back(num);
            continue;
        }

        prefixMaxs.push_back(max(prefixMaxs.back(), num));
    }

    int maxChunks = 1; // Base case.
    int suffixMin = nums.back(); // Min of nums[ith idx:].

    for (int idx = nums.size() - 1; idx >= 1; idx--) {
        if (nums[idx] < suffixMin)
            suffixMin = nums[idx];

        if (prefixMaxs[idx - 1] <= suffixMin)
            maxChunks++;
    }

    return maxChunks;
}

Python

def find_max_sortable_chunks(nums: list[int]) -> int:
    prefix_maxs = []  # Max of each nums[:(i + 1)th idx].

    for num in nums:
        if not prefix_maxs:
            prefix_maxs.append(num)
            continue

        prefix_maxs.append(max(num, prefix_maxs[-1]))

    max_chunks = 1  # Base case.
    suffix_min = nums[-1]  # Min of nums[ith idx:].

    for idx in range(len(nums) - 1, 0, -1):
        if nums[idx] < suffix_min:
            suffix_min = nums[idx]

        if prefix_maxs[idx - 1] <= suffix_min:
            max_chunks += 1

    return max_chunks

Time complexity $O(n)$, space complexity $O(n)$, with two passes through the array.

About a year and a half later, I thought of an alternative approach below...

II. Early 2026: Monotonic Increasing Stack

Eligibility to Lead a Chunk

Looking at previous code, prefix_maxs is a continuous process of expanding current leader.

Can you sense what situation would a leader get ineligible to be maximum of its chunk?

Consider this scenario: $0 \leq j < k < l < n$

$nums[j] \leq nums[k]$ holds.

$\max(nums[:j + 1]) = nums[j]$ holds.

$\max(nums[:k + 1]) = nums[k]$ holds.

So $nums[j]$ leads $Chunk_j = nums[:j + 1]$,

and $nums[k]$ leads $Chunk_k = nums[j + 1:k + 1]$. All good so far.

But Life Has Its "Buts"

Now comes $nums[l]$ satisfying $nums[l] < nums[j] \leq nums[k]$.

Since $k < l$, $nums[l]$ lies to the right of both $nums[j]$ and $nums[k]$.

With sharp instincts, we immediately have a problem:

I. If $nums[l]$ is kept out of $Chunk_k$ (led by $nums[k]$),

then $nums[l]$ forms $Chunk_y$ with elements to its right. After sorting,

$Chunk_y$ meets $Chunk_j$ from the left — $nums[j]$ and $nums[l]$ end up out of order.

II. Okay, so let $nums[l]$ join $Chunk_k$.

But after $Chunk_k$ is sorted and meets $Chunk_j$ from the left,

$nums[j]$ and $nums[l]$ are still out of order.

From both paths, we conclude directly:

$nums[l]$ and $nums[j]$ must be in the same chunk. Separating them causes problems.

This is precisely why $nums[j]$ must step down and can no longer lead any chunk.

Putting Monotonicity to Work

So we arrive at a conclusion: whenever the current $nums[i]$

is smaller than prefix_maxs[-1], we should:

(1). pop() to remove prefix_maxs[-1]

(2). If prefix_maxs is not yet empty,

keep checking whether prefix_maxs[-1] > nums[i]. If so, repeat step (2).

Otherwise, push the originally popped value back onto the right end of prefix_maxs.

Isn't this exactly the behavior of a monotonic increasing stack? 👌

After traversal, count how many elements remain in the stack, say $s$. That means there are $s$ eligible chunk leaders. Return $s$.

C++

#include <vector>
using namespace std;
#include <stack>

int findMaxSortableChunks(vector<int>& nums) {
    stack<int> stack;

    for (const auto& num : nums) {
        if (stack.empty()) {
            stack.push(num);
            continue;
        }

        int chunkMax = stack.top();

        while (!stack.empty() && num < stack.top())
            stack.pop();

        stack.push(max(chunkMax, num));
    }

    return stack.size();
}

Python

def find_max_sortable_chunks(nums: list[int]) -> int:
    stack: list[int] = []

    for num in nums:
        if not stack:
            stack.append(num)
            continue

        chunk_max = stack[-1]

        while stack and stack[-1] > num:
            stack.pop(-1)

        stack.append(max(chunk_max, num))

    return len(stack)

Both the stack and prefix approaches run in $O(n)$ time and $O(n)$ space, but the stack uses only a single pass.