Max Chunks To Make Sorted II

Reported in interviews at Hudson River Trading

Problem statement

You are given an integer array arr (which may contain duplicate values and is not necessarily sorted). Split arr into some number of contiguous, non-overlapping subarrays ("chunks"). After sorting each chunk individually and then concatenating the chunks back together in their original left-to-right order, the result must equal the fully sorted version of arr.

Return the largest number of chunks you can split the array into.

Write a function with the signature:

def maxChunks(arr: list) -> int:

Constraints:

  • $1 \leq |arr| \leq 2000$
  • $0 \leq arr[i] \leq 10^8$
  • The array may contain duplicates

Examples:

  1. maxChunks([5, 4, 3, 2, 1]) -> 1 (the whole array is one chunk; no smaller split sorts correctly)
  2. maxChunks([2, 1, 3, 4, 4]) -> 4 (chunks [2, 1] [3] [4] [4])
  3. maxChunks([1, 1, 2, 3]) -> 4 (already sorted, so every element is its own chunk)
Show hint

What has to be true about the values on each side of a boundary for sorting the two sides separately to be harmless?

Relevant roles: ML Engineer, Forward Deployed Engineer and AI Engineer.

Related free problems