Given an array A, partition it into two (contiguous) subarrays left and right so that:
Every element in left is less than or equal to every element in right.
left and right 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: [5,0,3,8,6]
Output: 3
Explanation: left = [5,0,3], right = [8,6]
Example 2:
Input: [1,1,1,0,6,12]
Output: 4
Explanation: left = [1,1,1,0], right = [6,12]
Note:
2 <= A.length <= 30000
0 <= A[i] <= 10^6
It is guaranteed there is at least one way to partition A as described.
Solution:
nlgn
class Solution {
public int partitionDisjoint(int[] A) {
List<int[]> list = new ArrayList();
for (int i = 0; i < A.length; i ++) {
list.add(new int[]{A[i], i});
}
Collections.sort(list, (a, b) -> { return Integer.compare(a[0], b[0]); });
int len = 1;
int maxIndex = list.get(0)[1];
for (int i = 1; i < list.size(); i ++) {
if (len == maxIndex + 1) {
return len;
}
int[] curr = list.get(i);
maxIndex = Math.max(maxIndex, curr[1]);
len ++;
}
return len;
}
}
O(n)
class Solution {
/*
suppose the original left subarray is from 0 to partitionIdx, the max value of that is localMax. If it is a valid partition, every value from partitionIdx + 1 to end should be >= localMax. But if we find a value in the right part, a[i], is smaller than localMax, which means the partition is not correct and we have to incorporate a[i] to form the left subarray. So the partitionIdx is set to be i, and we have to recalculate the max value of the new left subarray.(recorded in max)
*/
public int partitionDisjoint(int[] A) {
int localMax = A[0], partitionIdx = 0, max = A[0];
for (int i = 1; i < A.length; i ++) {
if (A[i] < localMax) {
localMax = max;
partitionIdx = i;
} else {
max = Math.max(max, A[i]);
}
}
return partitionIdx + 1;
}
}