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.
1def partitionDisjoint(nums):
2 max_left = nums[0]
3 max_so_far = nums[0]
4 partition_idx = 0
5
6 for i in range(1, len(nums)):
7 if nums[i] < max_left:
8 max_left = max_so_far
9 partition_idx = i
10 else:
11 max_so_far = max(max_so_far, nums[i])
12
13 return partition_idx + 1
14
15print(partitionDisjoint([5, 0, 3, 8, 6])) # Output: 3
16The Python solution achieves the partitioning by maintaining current maximums within the loop as it traverses the array. The partition index is adjusted whenever an element smaller than max_left is found, ensuring a valid disjoint partition is 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
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.