Mid/SeniorArray
Partition Array into Disjoint Intervals
Given an integer array nums, partition it into two contiguous subarrays left and right so that:
- Every element in
leftis less than or equal to every element inright. leftandrightare non-empty.lefthas the smallest possible size.
Return the length of left after such a partitioning.
Test cases are generated such that partitioning exists.
Example 1
Input
nums = [5,0,3,8,6]Output
3The smallest valid partition is left = [5, 0, 3] and right = [8, 6].
Example 2
Input
nums = [1,1,1,0,6,12]Output
4The smallest valid partition is left = [1, 1, 1, 0] and right = [6, 12].
Constraints
- 2 <= nums.length <= 10^5
- 0 <= nums[i] <= 10^6
- There is at least one valid answer for the given input.