#768

Hard

auto_awesomeStack-based state management

LeetCode Problem Workspace

Max Chunks To Make Sorted II

Determine the maximum number of chunks you can split an array into so that sorting each chunk results in a fully sorted array.

array stack greedy sorting monotonic stack

Problem Statement

You are given an integer array arr. Your goal is to split arr into contiguous chunks such that sorting each chunk individually and concatenating them produces the fully sorted array. Return the largest number of chunks possible.

Each chunk must preserve the original order of elements in arr. The challenge is identifying cut points using stack-based state management so that no sorted chunk interferes with the correctness of later chunks.

Examples

Example 1

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

Output: 1

Splitting into two or more chunks will not return the required result. For example, splitting into [5, 4], [3, 2, 1] will result in [4, 5, 1, 2, 3], which isn't sorted.

Example 2

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

Output: 4

We can split into two chunks, such as [2, 1], [3, 4, 4]. However, splitting into [2, 1], [3], [4], [4] is the highest number of chunks possible.

Constraints

1 <= arr.length <= 2000
0 <= arr[i] <= 108

Solution Approach

Use a Monotonic Stack to Track Chunks

Initialize an empty stack. Iterate through arr and for each element, push it onto the stack if it is greater than or equal to the top. Otherwise, merge elements by popping until the current element is larger than the top, maintaining the maximum of the merged chunk. The stack size at the end represents the maximum chunks.

Merge Overlapping Chunk Intervals

Whenever a new element is smaller than the stack top, merge it with all previous chunks that could cause the concatenated array to become unsorted. Keep the maximum value of the merged chunk to ensure future comparisons correctly identify further merges.

Return Stack Size for Final Count

After processing all elements, the number of elements remaining in the stack corresponds to the maximum number of chunks. Each represents a safe interval that can be sorted independently without violating the overall sorted order.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) for iterating and merging chunks via the stack. Space complexity is O(n) in the worst case when all elements form individual chunks.

What Interviewers Usually Probe

The candidate considers stack-based merging of overlapping intervals for chunk validity.
They track running maxima to determine safe cut points for sorting chunks independently.
They explicitly verify that concatenated sorted chunks match the fully sorted array.

Common Pitfalls or Variants

Common pitfalls

Failing to merge overlapping chunks leads to invalid concatenation of sorted intervals.
Assuming all elements can start a new chunk without comparing maxima can produce incorrect counts.
Neglecting repeated elements in arr may break monotonic stack assumptions.

Follow-up variants

Max Chunks To Make Sorted with distinct elements, simplifying merging logic.
Counting minimum chunks to sort using the same stack approach but merging aggressively.
Handling negative integers or larger ranges while maintaining correct chunk merges.

FAQ

What is the core pattern used in Max Chunks To Make Sorted II?

The problem uses stack-based state management, merging overlapping intervals to safely identify valid chunks.

Can repeated elements affect chunk splitting?

Yes, repeated elements require careful maximum tracking in the stack to ensure valid merges and avoid incorrect chunk counts.

Is it necessary to sort each chunk physically during the algorithm?

No, you only track maximum values and merge intervals; physical sorting is not needed to determine the chunk count.

What is the time complexity of the stack-based solution?

The solution runs in O(n) time because each element is pushed and popped at most once in the stack.

How does GhostInterview guide solving arrays like [5,4,3,2,1]?

It demonstrates that all elements merge into a single chunk, showing step-by-step stack merging and why the maximum chunk count is 1.

terminal

Solution

Solution 1: Monotonic Stack

According to the problem, we can find that from left to right, each chunk has a maximum value, and these maximum values are monotonically increasing (non-strictly increasing). We can use a stack to store these maximum values of the chunks. The size of the final stack is the maximum number of chunks that can be sorted.

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def maxChunksToSorted(self, arr: List[int]) -> int:
        stk = []
        for v in arr:
            if not stk or v >= stk[-1]:
                stk.append(v)
            else:
                mx = stk.pop()
                while stk and stk[-1] > v:
                    stk.pop()
                stk.append(mx)
        return len(stk)

Continue Practicing

#769 max chunks to make sorted #581 shortest unsorted continuous subarray #853 car fleet