Sponsored
Sponsored
This approach involves maintaining a running maximum for the left subarray and a suffix minimum for the right subarray. By iterating through the array and comparing these values, we can determine the appropriate partition point where all conditions are satisfied.
Time Complexity: O(n) - Linear scan of the array.
Space Complexity: O(1) - Only variables used for tracking, no extra storage required.
1#include <stdio.h>
2
3int partitionDisjoint(int* nums, int numsSize) {
4 int maxLeft = nums[0];
5 int partitionIdx = 0;
6 int maxSoFar = nums[0];
7
8 for (int i = 1; i < numsSize; i++) {
9 if (nums[i] < maxLeft) {
10 partitionIdx = i;
11 maxLeft = maxSoFar;
12 } else {
13 if (nums[i] > maxSoFar) {
14 maxSoFar = nums[i];
15 }
16 }
17 }
18
19 return partitionIdx + 1;
20}
21
22int main() {
23 int nums[] = {5, 0, 3, 8, 6};
24 int result = partitionDisjoint(nums, 5);
25 printf("%d\n", result); // Output: 3
26 return 0;
27}
28The C solution uses two variables, maxLeft and maxSoFar, to track the maximum values during the iteration through the array. Whenever we encounter an element smaller than maxLeft, it updates the partition index to that position and sets maxLeft to maxSoFar. This ensures all conditions of the partition are maintained.
This approach involves using two additional arrays: one to track the maximum values until any index from the left and another to track minimum values from the right. These auxiliary arrays help determine where a valid partition can be made in the original array.
Time Complexity: O(n) - Needs three linear passes through the array.
Space Complexity: O(n) - Additional space for two auxiliary arrays.
1#include <vector>
#include <climits>
using namespace std;
int partitionDisjoint(vector<int>& nums) {
int n = nums.size();
vector<int> leftMax(n), rightMin(n);
leftMax[0] = nums[0];
for (int i = 1; i < n; ++i) {
leftMax[i] = max(nums[i], leftMax[i - 1]);
}
rightMin[n - 1] = nums[n - 1];
for (int i = n - 2; i >= 0; --i) {
rightMin[i] = min(nums[i], rightMin[i + 1]);
}
for (int i = 0; i < n - 1; ++i) {
if (leftMax[i] <= rightMin[i + 1]) {
return i + 1;
}
}
return n;
}
int main() {
vector<int> nums = {5, 0, 3, 8, 6};
cout << partitionDisjoint(nums) << endl; // Output: 3
return 0;
}
The C++ approach maintains two arrays for maximum from the left and minimum from the right. These arrays are indexed to find the partition point whereby elements in leftMax are always lesser or equal to those in rightMin at a determined boundary.