Given an array nums
, partition it into two (contiguous) subarrays left
and right
so that:
- Every element in
left
is less than or equal to every element inright
. -
left
andright
are non-empty. -
left
has the smallest possible size.
Return the length of left
after such a partitioning. It is guaranteed that such a partitioning exists.
Example 1:
Input: nums = [5,0,3,8,6]
Output: 3
Explanation: left = [5,0,3], right = [8,6]
Example 2:
Input: nums = [1,1,1,0,6,12]
Output: 4
Explanation: left = [1,1,1,0], right = [6,12]
Note:
2 <= nums.length <= 30000
0 <= nums[i] <= 106
- It is guaranteed there is at least one way to partition
nums
as described.
public int partitionDisjoint(int[] A) { int maxUntilI = A[0]; int leftPartitionMax=A[0]; int partitionSpot = 0; for(int i=1;i<A.length;i++){ maxUntilI =Math.max(maxUntilI, A[i]) ; if(A[i]<leftPartitionMax){ leftPartitionMax=maxUntilI; partitionSpot =i; } } return partitionSpot+1; }
https://leetcode.com/problems/partition-array-into-disjoint-intervals/discuss/175945/Java-one-pass-7-lines