Loading problem...
You are given an integer array arr of length n that contains a permutation of the integers from 0 to n - 1 (inclusive). Each integer appears exactly once in the array.
Your goal is to divide the array into the maximum number of contiguous segments (partitions) such that when each segment is sorted independently and then all segments are concatenated in their original order, the resulting array is completely sorted in ascending order.
A segment is a contiguous subarray of arr. You must find the largest possible count of such segments that satisfy the above sorting condition.
Key Insight: For a valid partition, after sorting each segment individually and joining them back together, the final concatenated array must equal [0, 1, 2, ..., n-1].
arr = [4,3,2,1,0]1The entire array must be treated as a single segment. If we try to split it (e.g., into [4,3] and [2,1,0]), sorting each gives [3,4] and [0,1,2], which concatenates to [3,4,0,1,2] — not sorted. Hence, only 1 segment is possible.
arr = [1,0,2,3,4]4We can partition the array into [1,0], [2], [3], [4]. Sorting the first segment gives [0,1], and the rest are already sorted single elements. Concatenating yields [0,1,2,3,4], which is the sorted array. This gives us 4 segments, the maximum possible.
arr = [0,1,2,3,4]5The array is already sorted. Each element can be its own segment: [0], [1], [2], [3], [4]. Sorting and concatenating gives the same sorted array. Thus, we achieve the maximum of 5 segments.
Constraints