0965MediumArrayStackGreedySortingMonotonic Stack

Most Blocks a Line Can Be Cut Into

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A line of labels is given as arr, holding each of the numbers from 0 up to one less than its length exactly once.

Cut the line into blocks of neighbouring labels, then sort each block on its own and join the blocks back up in the same order. Return the greatest number of blocks for which this leaves the whole line in increasing order.

Examples

Example 1

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

Cutting after position 2 and after position 4 gives the blocks 2, 0, 1 and 4, 3, each of which sorts into place. Cutting anywhere else would leave a label in the wrong block.

Example 2

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

Each neighbouring pair is swapped, so the line cuts into three blocks of two.

Example 3

Input: arr = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
Output: 1

The whole line is reversed, so no cut works and it must be sorted as one block.

Constraints

1 <= arr.length <= 10
0 <= arr[i] <= arr.length - 1
Every number from 0 to arr.length - 1 appears exactly once

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def max_chunks_to_sorted(arr: list[int]) -> int:

Java

public int maxChunksToSorted(int[] arr)

The intended approach

Time O(n) for a line of n labels, one pass.Space O(1).

Since the labels are exactly the numbers from zero upward, the sorted line puts label `k` at position `k`. A cut after position `i` works only if the labels before the cut are exactly the numbers up to `i`, because those are the labels that must end up there and no others may. That is easy to test: the labels seen so far are the numbers up to `i` exactly when the largest of them is `i`, since there are `i + 1` of them and they are all different and all within range. So walk the line carrying the largest label seen and count a cut every time that largest matches the position. Every such cut is safe and taking all of them gives the most blocks.

Pythonentry point: max_chunks_to_sorted

def max_chunks_to_sorted(arr):
    blocks = 0
    tallest = -1
    for i in range(len(arr)):
        if arr[i] > tallest:
            tallest = arr[i]
        if tallest == i:
            blocks += 1
    return blocks

The obvious version

Try every way of cutting the line, sort each block, join them up and check the result is in order, keeping the most blocks that works. Exponential in the line's length and it makes no argument about where a cut is safe.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_max_chunks_to_sorted(arr):
    n = len(arr)
    best = 1
    for mask in range(1 << (n - 1)):
        cuts = [0]
        for i in range(n - 1):
            if mask >> i & 1:
                cuts.append(i + 1)
        cuts.append(n)
        built = []
        for t in range(len(cuts) - 1):
            piece = sorted(arr[cuts[t]:cuts[t + 1]])
            built.extend(piece)
        ok = True
        for i in range(1, n):
            if built[i] < built[i - 1]:
                ok = False
                break
        if ok and len(cuts) - 1 > best:
            best = len(cuts) - 1
    return best

How this problem was checked

Reference solution executed against 10 test cases — 10 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in