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 <iostream>
2#include <vector>
3using namespace std;
4
5int partitionDisjoint(vector<int>& nums) {
6 int maxLeft = nums[0], maxSoFar = nums[0], partitionIdx = 0;
7 for (int i = 1; i < nums.size(); ++i) {
8 if (nums[i] < maxLeft) {
9 maxLeft = maxSoFar;
10 partitionIdx = i;
11 } else if (nums[i] > maxSoFar) {
12 maxSoFar = nums[i];
13 }
14 }
15 return partitionIdx + 1;
16}
17
18int main() {
19 vector<int> nums = {5, 0, 3, 8, 6};
20 cout << partitionDisjoint(nums) << endl; // Output: 3
21 return 0;
22}
23The C++ solution applies the same logic as the C code utilizing vectors. It maintains running maximums and determines the partition index by comparing each element against maxLeft. If the current element is smaller, it adjusts the partition index and updates maxLeft.
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
public class PartitionArray {
public static int PartitionDisjoint(int[] nums) {
int n = nums.Length;
int[] leftMax = new int[n];
int[] rightMin = new int[n];
leftMax[0] = nums[0];
for (int i = 1; i < n; i++) {
leftMax[i] = Math.Max(nums[i], leftMax[i - 1]);
}
rightMin[n - 1] = nums[n - 1];
for (int i = n - 2; i >= 0; i--) {
rightMin[i] = Math.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;
}
public static void Main() {
int[] nums = { 5, 0, 3, 8, 6 };
Console.WriteLine(PartitionDisjoint(nums)); // Output: 3
}
}
This C# approach uses two separate arrays to maintain values required for a correct partition, allowing easy identification of the appropriate partition point based on the maximum and minimum conditions set during pre-processing.