Max Chunks To Make Sorted II

Hard
1410.

Max Chunks To Make Sorted II

Max Chunks To Make Sorted II is a hard coding problem on arrays, greedy and stack, asked in Amazon and Google interviews.

Split the integer array arr into contiguous chunks, sort each chunk on its own, and put the chunks back together in their original order. The split is valid if the result equals arr sorted in non-decreasing order.

Values may repeat. Return the largest number of chunks a valid split can have.

Example 1

Input
arr = [3,2,4,4,6,5]
Output
4
Explanation
`[3,2] [4] [4] [6,5]` sorts to `[2,3,4,4,5,6]`.

Example 2

Input
arr = [5,1,1,8,2]
Output
1
Explanation
The final 2 must move in front of the 5, so everything is one chunk.

Example 3

Input
arr = [1,1,0,0,1]
Output
2
Explanation
`[1,1,0,0] [1]`.

Constraints

  • 1 <= arr.length <= 2000
  • 0 <= arr[i] <= 10^8
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @return {number}
 */
var maxChunksToSorted = function(arr) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Max Chunks To Make Sorted II — Problem & Solution

Max Chunks To Make Sorted II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Max Chunks To Make Sorted II is a hard coding problem on arrays, greedy and stack, asked in Amazon and Google interviews.

Problem statement

Split the integer array arr into contiguous chunks, sort each chunk on its own, and put the chunks back together in their original order. The split is valid if the result equals arr sorted in non-decreasing order.

Values may repeat. Return the largest number of chunks a valid split can have.

Example 1

Input: arr = [3,2,4,4,6,5]
Output: 4
Explanation: `[3,2] [4] [4] [6,5]` sorts to `[2,3,4,4,5,6]`.

Example 2

Input: arr = [5,1,1,8,2]
Output: 1
Explanation: The final 2 must move in front of the 5, so everything is one chunk.

Example 3

Input: arr = [1,1,0,0,1]
Output: 2
Explanation: `[1,1,0,0] [1]`.

Constraints

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

Hints for Max Chunks To Make Sorted II

  1. Hint 1

    A cut after position i is allowed exactly when everything to its left is <= everything to its right.

  2. Hint 2

    Represent each chunk by its maximum and keep the chunks on a stack. What happens when a value smaller than some chunk maxima arrives?

  3. Hint 3

    If the new value x is smaller than the top chunk's maximum, it must join that chunk — and every earlier chunk whose maximum is greater than x. Pop them all and push back the largest maximum.

How to solve Max Chunks To Make Sorted II

Maintain the current best partition of the prefix as a stack of chunk maxima (non-decreasing from bottom to top). A new value either starts a chunk of its own or forces the chunks with larger maxima to fuse with it.

Approach

  1. For each x in arr: if the stack is empty or x >= top, push x — it can be a chunk on its own.
  2. Otherwise remember mx = top (the largest maximum so far), pop it, and keep popping while the new top is > x.
  3. Push mx back: the fused chunk's maximum.
  4. The answer is the stack size.

Why it works

A value x must end up before every value greater than it, so it cannot be separated from any earlier chunk whose maximum exceeds x; those chunks are contiguous at the top of the stack because the maxima are non-decreasing. Chunks whose maximum is <= x can stay separate, since x (and everything in its chunk so far) is not smaller than anything in them. Merging only what is forced keeps the number of chunks as large as possible.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • Duplicates break the 'Max Chunks I' trick of comparing with indices — compare values instead.
  • Pop only while the top is strictly greater than x; equal maxima can stay apart.
  • Push back the largest popped maximum, not x.

Reference solution

Python

from typing import List

def maxChunksToSorted(arr: List[int]) -> int:
    st = []
    for x in arr:
        if not st or x >= st[-1]:
            st.append(x)
        else:
            mx = st.pop()
            while st and st[-1] > x:
                st.pop()
            st.append(mx)
    return len(st)

Java

public static int maxChunksToSorted(int[] arr) {
    int[] st = new int[arr.length];
    int top = 0;
    for (int x : arr) {
        if (top == 0 || x >= st[top - 1]) {
            st[top++] = x;
        } else {
            int mx = st[--top];
            while (top > 0 && st[top - 1] > x) top--;
            st[top++] = mx;
        }
    }
    return top;
}

C++

int maxChunksToSorted(vector<int>& arr) {
    vector<int> st;
    for (int x : arr) {
        if (st.empty() || x >= st.back()) {
            st.push_back(x);
        } else {
            int mx = st.back();
            st.pop_back();
            while (!st.empty() && st.back() > x) st.pop_back();
            st.push_back(mx);
        }
    }
    return st.size();
}

JavaScript

var maxChunksToSorted = function(arr) {
    var st = [];
    for (var i = 0; i < arr.length; i++) {
        var x = arr[i];
        if (st.length === 0 || x >= st[st.length - 1]) {
            st.push(x);
        } else {
            var mx = st.pop();
            while (st.length > 0 && st[st.length - 1] > x) st.pop();
            st.push(mx);
        }
    }
    return st.length;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Greedy Algorithms