LeetCode 768 - Max Chunks To Make Sorted II

LeetCode Problem 768

Difficulty: 🔴 Hard
Topics: Array, Stack, Greedy, Sorting, Monotonic Stack

Solution

Problem Understanding

The problem asks us to partition an array into the maximum possible number of contiguous chunks such that, after sorting each chunk independently and concatenating the results, the entire array becomes globally sorted.

The key detail is that each chunk must remain contiguous. We cannot rearrange elements across chunk boundaries after splitting. Once the chunks are defined, each chunk is sorted individually, then all sorted chunks are concatenated in their original order.

The goal is to maximize the number of chunks.

For example, consider:

arr = [2,1,3,4,4]

We can split this into:

[2,1], [3], [4], [4]

Sorting each chunk gives:

[1,2], [3], [4], [4]

Concatenating them produces:

[1,2,3,4,4]

which is fully sorted.

The challenge becomes harder because the array can contain duplicates. This is the major difference from LeetCode 769, where the array is a permutation of 0..n-1. In this problem, values may repeat and may be arbitrarily large.

The constraints are:

• 1 <= arr.length <= 2000
• 0 <= arr[i] <= 10^8

An array length of 2000 is not extremely large, so quadratic solutions may pass, but cubic solutions would likely be too slow. The presence of duplicates means we cannot rely on index-value matching tricks.

Several edge cases are important:

• Arrays already sorted, where every element may form its own chunk.
• Arrays sorted in reverse order, where only one chunk is possible.
• Arrays with many duplicates, where chunk boundaries become subtle.
• Arrays where local ordering looks valid but global ordering breaks if split incorrectly.
• Single-element arrays, where the answer is always 1.

A naive implementation can easily fail by considering only local comparisons instead of ensuring that all elements in the left chunk are less than or equal to all elements in the right chunk.

Approaches

Brute Force Approach

A brute-force solution would try every possible partitioning of the array and verify whether sorting each chunk produces the globally sorted array.

For an array of length n, there are 2^(n-1) possible ways to place separators between elements. For each partitioning:

1. Split the array into chunks.
2. Sort each chunk independently.
3. Concatenate the sorted chunks.
4. Compare the result with the fully sorted version of the original array.

This approach is correct because it exhaustively checks every valid partitioning configuration. If any partitioning works, it is considered, and the maximum number of chunks can be tracked.

However, this approach is computationally infeasible because the number of partitionings grows exponentially.

Key Insight for the Optimal Solution

A chunk boundary between indices i and i+1 is valid if every element on the left side is less than or equal to every element on the right side.

This leads to a very important observation:

If:

max(arr[0..i]) <= min(arr[i+1..n-1])

then we can safely split after index i.

Why does this work?

After sorting the left chunk, its largest value will still be at the end of the chunk. After sorting the right chunk, its smallest value will still be at the beginning of that chunk. Therefore, the concatenation remains globally sorted if the maximum value in the left chunk does not exceed the minimum value in the right chunk.

This suggests a prefix/suffix preprocessing strategy:

• Compute prefix_max[i], the maximum value from the start through index i.
• Compute suffix_min[i], the minimum value from index i through the end.

Then every valid split position satisfies:

prefix_max[i] <= suffix_min[i+1]

Each such position adds one more chunk.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n * n log n)	O(n)	Tries every partitioning and validates by sorting
Optimal	O(n)	O(n)	Uses prefix maximums and suffix minimums

Algorithm Walkthrough

1. Create a prefix_max array.

For every index i, store the maximum value seen from the beginning of the array through index i.

This tells us the largest value that would appear in the left chunk if we split after i. 2. Create a suffix_min array.

For every index i, store the minimum value seen from index i through the end of the array.

This tells us the smallest value that would appear in the right chunk if we split before i. 3. Initialize the first chunk count.

Even if no splits are possible, the entire array itself forms one valid chunk. Therefore, we start with:

chunks = 1

4. Iterate through all possible split positions.

For every index i from 0 to n-2:

• The left chunk would be arr[0..i]
• The right chunk would be arr[i+1..n-1]

If:

prefix_max[i] <= suffix_min[i+1]

then the split is safe. 5. Increment the chunk count whenever a valid split exists.

Each valid split creates one additional chunk. 6. Return the final chunk count.

Why it works

The algorithm relies on the invariant that every element in the left chunk must be less than or equal to every element in the right chunk.

prefix_max[i] represents the largest element on the left side of a potential split. suffix_min[i+1] represents the smallest element on the right side.

If:

prefix_max[i] <= suffix_min[i+1]

then sorting the two chunks independently cannot create an inversion across the boundary. Therefore, the concatenated result remains globally sorted.

Because the algorithm checks every possible boundary independently and counts all valid ones, it produces the maximum possible number of chunks.

Python Solution

from typing import List

class Solution:
    def maxChunksToSorted(self, arr: List[int]) -> int:
        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

The implementation follows the exact strategy described in the algorithm walkthrough.

First, two helper arrays are allocated:

• prefix_max
• suffix_min

The prefix_max array is built from left to right. Each position stores the maximum value seen so far. This allows constant-time access to the largest value in any left partition.

The suffix_min array is built from right to left. Each position stores the minimum value from that index onward. This allows constant-time access to the smallest value in any right partition.

The algorithm then checks every possible split position. If the maximum value on the left side is less than or equal to the minimum value on the right side, the split is valid and the chunk count increases.

The solution runs in linear time because each array is traversed only a constant number of times.

Go Solution

func maxChunksToSorted(arr []int) int {
	n := len(arr)

	prefixMax := make([]int, n)
	suffixMin := make([]int, n)

	prefixMax[0] = arr[0]
	for i := 1; i < n; i++ {
		if prefixMax[i-1] > arr[i] {
			prefixMax[i] = prefixMax[i-1]
		} else {
			prefixMax[i] = arr[i]
		}
	}

	suffixMin[n-1] = arr[n-1]
	for i := n - 2; i >= 0; i-- {
		if suffixMin[i+1] < arr[i] {
			suffixMin[i] = suffixMin[i+1]
		} else {
			suffixMin[i] = arr[i]
		}
	}

	chunks := 1

	for i := 0; i < n-1; i++ {
		if prefixMax[i] <= suffixMin[i+1] {
			chunks++
		}
	}

	return chunks
}

The Go implementation mirrors the Python solution closely.

Go does not provide built-in max and min functions for integers, so explicit comparisons are used while constructing the prefix and suffix arrays.

Slices are dynamically allocated using make, and integer overflow is not a concern because the constraints fit comfortably within Go's int range on modern systems.

The algorithm still runs in linear time and linear space.

Worked Examples

Example 1

arr = [5,4,3,2,1]

Step 1: Build Prefix Maximums

Index	Value	prefix_max
0	5	5
1	4	5
2	3	5
3	2	5
4	1	5

Result:

prefix_max = [5,5,5,5,5]

Step 2: Build Suffix Minimums

Index	Value	suffix_min
4	1	1
3	2	1
2	3	1
1	4	1
0	5	1

Result:

suffix_min = [1,1,1,1,1]

Step 3: Check Split Positions

Split After Index	Left Max	Right Min	Valid?
0	5	1	No
1	5	1	No
2	5	1	No
3	5	1	No

No valid splits exist.

Final answer:

1

Example 2

arr = [2,1,3,4,4]

Step 1: Build Prefix Maximums

Index	Value	prefix_max
0	2	2
1	1	2
2	3	3
3	4	4
4	4	4

Result:

prefix_max = [2,2,3,4,4]

Step 2: Build Suffix Minimums

Index	Value	suffix_min
4	4	4
3	4	4
2	3	3
1	1	1
0	2	1

Result:

suffix_min = [1,1,3,4,4]

Step 3: Check Split Positions

Split After Index	Left Max	Right Min	Valid?
0	2	1	No
1	2	3	Yes
2	3	4	Yes
3	4	4	Yes

We begin with one chunk and add three valid splits:

chunks = 4

Final answer:

4

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each array is traversed a constant number of times
Space	O(n)	Two auxiliary arrays are stored

The algorithm performs three linear passes:

1. Build prefix_max
2. Build suffix_min
3. Count valid split points

Each pass touches every element once, producing overall linear time complexity.

The additional memory comes from the two helper arrays, each of size n.

Test Cases

from typing import List

class Solution:
    def maxChunksToSorted(self, arr: List[int]) -> int:
        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

solution = Solution()

assert solution.maxChunksToSorted([5,4,3,2,1]) == 1  # reverse sorted
assert solution.maxChunksToSorted([2,1,3,4,4]) == 4  # provided example
assert solution.maxChunksToSorted([1,2,3,4,5]) == 5  # already sorted
assert solution.maxChunksToSorted([1]) == 1  # single element
assert solution.maxChunksToSorted([2,2,2]) == 3  # all duplicates
assert solution.maxChunksToSorted([1,0,1,3,2]) == 3  # mixed ordering
assert solution.maxChunksToSorted([4,3,2,1,0]) == 1  # another reverse case
assert solution.maxChunksToSorted([0,0,1,1,1]) == 5  # duplicates already sorted
assert solution.maxChunksToSorted([1,1,0,0,1]) == 2  # duplicate boundary interactions
assert solution.maxChunksToSorted([2,0,1]) == 1  # no valid split

Test	Why
[5,4,3,2,1]	Ensures reverse sorted arrays produce one chunk
[2,1,3,4,4]	Validates the official example
[1,2,3,4,5]	Every position should be splittable
[1]	Smallest possible input
[2,2,2]	Handles all duplicate values
[1,0,1,3,2]	Tests mixed valid and invalid boundaries
[4,3,2,1,0]	Confirms no premature splits
[0,0,1,1,1]	Checks repeated sorted values
[1,1,0,0,1]	Verifies duplicate-heavy edge behavior
[2,0,1]	Ensures incorrect local splits are rejected

Edge Cases

Reverse Sorted Arrays

A reverse sorted array such as:

[5,4,3,2,1]

is an important edge case because every element on the left side is larger than some element on the right side. A naive implementation might incorrectly split based on local ordering.

The prefix/suffix approach handles this correctly because the prefix maximum always remains 5, while every suffix minimum remains 1. Since the condition:

prefix_max[i] <= suffix_min[i+1]

never holds, no splits are allowed.

Arrays With Duplicate Values

Duplicates make this problem significantly harder than the simpler permutation version.

For example:

[2,2,2]

Every split is valid because equal values are allowed across chunk boundaries.

The implementation correctly uses <= rather than <. This detail is critical. Using strict inequality would incorrectly reject valid chunk boundaries involving equal values.

Single Element Arrays

An array with one element has no split positions at all, but the entire array itself still forms one valid chunk.

The implementation handles this naturally because:

chunks = 1

is initialized before checking split positions. Since the loop over split positions never executes, the method correctly returns 1.