Most Blocks That Sort Independently

HardArrays & Hashing

Problem

A batch job sorts a large array nums by cutting it into contiguous blocks, sorting every block independently on a different machine, and concatenating the blocks back in their original order.

Return the maximum number of blocks you can cut so that the concatenated result equals nums fully sorted in non-decreasing order. Values may repeat.

Example 1

Input:
nums = [2, 1, 3, 4, 4]
Output:
4

Blocks [2, 1] | [3] | [4] | [4].

Example 2

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

Any cut leaves a larger value before a smaller one.

Example 3

Input:
nums = [1, 1, 1]
Output:
3

Constraints

  • 1 ≤ nums.length ≤ 10^5
  • -10^8 ≤ nums[i] ≤ 10^8

Hint

Show the first hint

Decide each cut independently: when is it safe to cut between index i and i + 1?

Walkthrough

How to approach it

01Clarify before coding

  • Can values repeat? Yes, which rules out the 'values are a permutation of 0..n-1' shortcut.
  • Are blocks contiguous and kept in order? Yes, only each block's interior is sorted.
  • Is one block (no cut) always valid? Yes, so the answer is at least 1.

02Brute force

For each possible cut, compute the max of the left part and the min of the right part from scratch.

Cost: O(n²) time: 10^10 operations at n = 10^5.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.