Skip to main content
Talentd

Max Chunks To Make Sorted II - Solution & Explanation

HardArrayStackGreedySorting16 min readAsked at: Amazon, Microsoft, Salesforce +2
Practice this problem

Problem Statement

You are given an integer array arr.

We split arr into some number of chunks (i.e., partitions), and individually sort each chunk. After concatenating them, the result should equal the sorted array.

Return the largest number of chunks we can make to sort the array.

 

Example 1:

Input: arr = [5,4,3,2,1]
Output: 1
Explanation:
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
Explanation:
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

Approach Overview

Problem Overview: Given an integer array (with possible duplicates), split it into the maximum number of chunks so that sorting each chunk individually and concatenating them results in the entire array being sorted. The challenge is identifying valid split points where the left part never needs elements from the right part to maintain global order.

Approach 1: Prefix Maximum and Suffix Minimum Comparison (O(n) time, O(n) space)

This approach precomputes ordering constraints from both directions. Build a prefixMax array where prefixMax[i] stores the maximum value from index 0..i. Build a suffixMin array where suffixMin[i] stores the minimum value from index i..n-1. A valid chunk boundary exists at index i if prefixMax[i] <= suffixMin[i+1]. That condition guarantees every element in the left chunk is less than or equal to every element in the right chunk, so sorting them independently preserves global order. Iterate once to compute prefix and suffix arrays, then scan again to count valid split points. This method is easy to reason about and works well when clarity matters more than memory usage. It relies heavily on concepts from Array processing and Sorting order properties.

Approach 2: Monotonic Stack (O(n) time, O(n) space)

The optimal interview solution uses a Monotonic Stack to dynamically maintain chunk boundaries. Traverse the array while keeping a stack where each element represents the maximum value of a chunk. If the current value is greater than or equal to the top of the stack, it can safely start a new chunk, so push it onto the stack. When the current value is smaller than the stack top, it violates the ordering of previous chunks. Pop stack elements until the stack top is less than or equal to the current value, merging those chunks into one larger chunk. Track the maximum value from the popped elements and push it back to represent the merged chunk. The stack size at the end equals the number of valid chunks. This greedy merging ensures earlier chunks expand whenever later elements would otherwise break global ordering.

Recommended for interviews: The monotonic stack approach is typically what interviewers expect for Hard-level array partitioning problems. It shows you recognize ordering violations and can merge segments efficiently in a single pass. The prefix–suffix method demonstrates strong reasoning about global ordering constraints and is often easier to implement quickly. Showing awareness of both approaches signals solid understanding of Greedy techniques and boundary detection patterns.

Approach 1: Using Monotonic Stack

This approach uses a monotonic stack to determine when the current number in arr can form a valid chunk. The logic involves maintaining the maximum number in the current chunk and popping elements from the stack until the current number is larger than the stack's top, effectively merging chunks. This ensures the final order is still preserved.

This C solution uses a stack to keep track of the current chunk's maximum elements. As it iterates through the array, it decides whether a new chunk can start or if merging is necessary.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), because we are iterating through the array once.
Space Complexity: O(n), for the stack used to track the maximum of current chunks.

Try this approach in the editor →

Approach 2: Prefix Maximum and Suffix Minimum Comparison

This approach leverages prefix maximums and suffix minimums to determine the point of split where a new chunk can start. We maintain an array that keeps track of the maximum value up to the current index from the left and the minimum from the right.

This C solution calculates and compares prefix maximums with suffix minimums to decide valid chunk points. If the prefix max up to i is less than or equal to the suffix min starting from i+1, a new chunk can start.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), due to two linear passes through the array.
Space Complexity: O(n), for maintaining the prefix max and suffix min arrays.

Try this approach in the editor →

Approach 3: 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.

Time complexity is O(n), where n represents the length of arr.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Using Monotonic Stack

Time Complexity: O(n), because we are iterating through the array once.
Space Complexity: O(n), for the stack used to track the maximum of current chunks.

Prefix Maximum and Suffix Minimum Comparison

Time Complexity: O(n), due to two linear passes through the array.
Space Complexity: O(n), for maintaining the prefix max and suffix min arrays.

Monotonic Stack—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Prefix Max & Suffix MinO(n)O(n)When you want a straightforward method that clearly identifies chunk boundaries using precomputed ordering information.
Monotonic StackO(n)O(n)Preferred in interviews and optimal single-pass solution when handling ordering violations dynamically.

Video Solution

Max Chunks To Make Array Sorted - 2 | Arrays & Strings | Leetcode 768 Solution in Hindi • Pepcoding • 18,309 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Max Chunks To Make Sorted II easy or hard?
Max Chunks To Make Sorted II is classified as a Hard problem on LeetCode. Handling duplicate values and determining safe partition boundaries makes it more complex than the original version. Efficient solutions require recognizing greedy merging patterns or prefix–suffix ordering checks.
Max Chunks To Make Sorted II Python/Java solution
Python and Java implementations usually follow either the monotonic stack pattern or the prefix max/suffix min approach. The stack solution iterates once and merges chunks dynamically, while the prefix-suffix solution precomputes boundary constraints before counting valid splits.
How to solve Max Chunks To Make Sorted II in O(n)?
Compute prefix maximums and suffix minimums, then count indices where prefixMax[i] <= suffixMin[i+1]. Each such index represents a valid chunk boundary. Another O(n) method uses a monotonic stack that merges chunks whenever a smaller element violates the ordering of previous chunks.
What is the best approach for Max Chunks To Make Sorted II?
The monotonic stack approach is considered the best solution. It processes the array in one pass while maintaining chunk boundaries using a stack of maximum values. When a smaller element appears, earlier chunks are merged to preserve global order. The algorithm runs in O(n) time with O(n) space.
Is Max Chunks To Make Sorted II asked at Google/Amazon/Meta?
Max Chunks To Make Sorted II appears in interview preparation lists for companies like Google, Amazon, and Meta because it tests array partitioning, greedy reasoning, and monotonic stack patterns. Variations of this problem often appear in coding interviews focused on segment boundaries and ordering constraints.
What data structure is used in Max Chunks To Make Sorted II?
The key data structure is a monotonic stack that stores the maximum value of each chunk. It allows efficient merging of previous chunks when a new element breaks sorted ordering. The alternative approach uses prefix and suffix arrays to track maximum and minimum values.
What is the time complexity of Max Chunks To Make Sorted II?
The optimal solutions run in O(n) time where n is the length of the array. Both the monotonic stack approach and the prefix maximum–suffix minimum method require a single or small constant number of passes through the array. Space complexity is O(n) due to either the auxiliary arrays or the stack.

Ready to solve this problem?

Practice Max Chunks To Make Sorted II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Max Chunks To Make Sorted