How should I practice Max Chunks to Make Sorted II?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Amazon phone screen problems in FastPrep.

Is Max Chunks to Make Sorted II associated with Amazon?

FastPrep tags this as a Amazon phone screen coding practice problem when the problem catalog has that company and stage context.

Problem · Array

Max Chunks to Make Sorted II

Learn this problem

● Hard

AmazonNEW GRADPHONE SCREEN

See Amazon hiring insights

Problem statement

Given an integer array arr, partition it into the maximum number of non-empty contiguous chunks. Sort every chunk independently in nondecreasing order, then concatenate the chunks.

Return the maximum number of chunks for which the concatenated result equals a globally sorted copy of arr. Values may repeat.

Function

maxChunksToSorted(arr: int[]) → int

Examples

Example 1

arr = [5,4,3,2,1]return = 1

Every proper split leaves a larger value before a smaller value across the boundary, so the entire array is one chunk.

Example 2

arr = [2,1,3,4,4]return = 4

The chunks can be [2,1], [3], [4], and [4].

Example 3

arr = [1,0,1,3,2]return = 3

The chunks [1,0], [1], and [3,2] sort and concatenate to [0,1,1,2,3].

Constraints

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