LeetCode Solutions
class Solution {
public:
int partitionDisjoint(vector<int>& A) {
const int n = A.size();
vector<int> min(n);
min[n - 1] = A[n - 1];
int max = INT_MIN;
for (int i = n - 2; i >= 0; --i)
min[i] = std::min(min[i + 1], A[i]);
for (int i = 0; i < n; ++i) {
max = std::max(max, A[i]);
if (max <= min[i + 1])
return i + 1;
}
throw;
}
};
|
class Solution {
public int partitionDisjoint(int[] A) {
final int n = A.length;
int[] min = new int[n];
min[n - 1] = A[n - 1];
int max = Integer.MIN_VALUE;
for (int i = n - 2; i >= 0; --i)
min[i] = Math.min(min[i + 1], A[i]);
for (int i = 0; i < n; ++i) {
max = Math.max(max, A[i]);
if (max <= min[i + 1])
return i + 1;
}
throw new IllegalArgumentException();
}
}
|
class Solution:
def partitionDisjoint(self, A: List[int]) -> int:
n = len(A)
mini = [0] * (n - 1) + [A[-1]]
maxi = -math.inf
for i in range(n - 2, - 1, -1):
mini[i] = min(mini[i + 1], A[i])
for i, a in enumerate(A):
maxi = max(maxi, a)
if maxi <= mini[i + 1]:
return i + 1
|
