Show problems as
Classic problem #768HardArrayStackGreedySortingMonotonic Stack

Max Chunks To Make Sorted II

Real-world version: Cutting the Row Into the Most Blocks
Tracked in this browser only
Read Max Chunks To Make Sorted II on LeetCode(opens in a new tab)

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

A row holds the weights weights, and weights may repeat. Cut the row into blocks of neighbouring crates so that sorting each block on its own leaves the whole row in non-decreasing order.

Return the largest number of blocks such a cut can use.

Examples

Example 1

Input
weights = [1, 3, 2, 4]
Output
3

Cut after the first crate and after the third. The middle block of 3 and 2 sorts into 2 and 3, and the whole row comes out in order.

Example 2

Input
weights = [2, 3, 1, 4]
Output
2

The 1 has to end up before both the 2 and the 3, so those three crates must share a block. Cutting after them gives two blocks.

Example 3

Input
weights = [1, 1]
Output
2

Both crates weigh the same, so the cut between them is allowed and each is its own block.

Constraints

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

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(weights: list[int]) -> int:
Java
public int maxChunksToSorted(int[] weights)

More on the same topics