Show problems as
Classic problem #769MediumArrayStackGreedySortingMonotonic Stack

Max Chunks To Make Sorted

Real-world version: Most Blocks a Line Can Be Cut Into
Tracked in this browser only
Read Max Chunks To Make Sorted on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def max_chunks_to_sorted(arr: list[int]) -> int:
Java
public int maxChunksToSorted(int[] arr)

More on the same topics