Max Chunks To Make Sorted II

Problem Split an array (duplicates allowed, values arbitrary) into the maximum number of contiguous chunks such that individually sorting each chunk and concatenating yields the fully sorted array.

Input / Output

• Input: int array arr. Output: max chunk count.

Constraints

• n up to 10^5; O(n) expected.

Example

• [2,5,1,9,7,6] → 2 ([2,5,1] + [9,7,6]); [2,1,3,4,4] → 4 ([2,1],[3],[4],[4]).

Expected approach

• A cut after index i is valid iff max(arr[0..i]) <= min(arr[i+1..n−1]). Precompute suffixMin[]; sweep with a running prefixMax counting valid cut points. O(n)/O(n). Equivalent one-pass: monotonic stack of chunk-maxima — merge stack tops greater than the current element (their chunks must fuse); stack size = answer; O(n)/O(n) worst. Duplicates are why the "compare with sorted copy by position-sum/count" trick from version I fails — explaining that distinction is the point.