Problem
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 1: BST
Time complexity: O(nlogn)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
// Author: Huahua, 100 ms class Solution { public: int partitionDisjoint(vector<int>& A) { multiset<int> s(begin(A) + 1, end(A)); int left_max = A[0]; for (int i = 1; i < A.size(); ++i) { if (*begin(s) >= left_max) return i; s.erase(s.equal_range(A[i]).first); left_max = max(left_max, A[i]); } return -1; } }; |
Solution 2: Greedy
Time complexity: O(n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
// Author: Huahua, 28 ms class Solution { public: int partitionDisjoint(vector<int>& A) { int left_max = A[0]; int cur_max = A[0]; int left_len = 1; for (int i = 1; i < A.size(); ++i) { if (A[i] < left_max) { left_max = cur_max; left_len = i + 1; } else { cur_max = max(cur_max, A[i]); } } return left_len; } }; |