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
In this C solution, two arrays leftMax and rightMin are used to keep track of the maximum values up to an index and the minimum values from an index onward. By comparing elements from leftMax and rightMin, we determine the appropriate partition point.