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.
1using System;
2
3public class PartitionArray {
4 public static int PartitionDisjoint(int[] nums) {
5 int maxLeft = nums[0];
6 int maxSoFar = nums[0];
7 int partitionIdx = 0;
8
9 for (int i = 1; i < nums.Length; i++) {
10 if (nums[i] < maxLeft) {
11 maxLeft = maxSoFar;
12 partitionIdx = i;
13 } else if (nums[i] > maxSoFar) {
14 maxSoFar = nums[i];
15 }
16 }
17 return partitionIdx + 1;
18 }
19
20 public static void Main() {
21 int[] nums = {5, 0, 3, 8, 6};
22 Console.WriteLine(PartitionDisjoint(nums)); // Output: 3
23 }
24}
25The C# solution uses similar constructs as other languages to partition the array by maintaining track of maximum values in respective subarrays. This ensures that left is always greater than or equal right at determined points.
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
Java employs two auxiliary arrays like the other approaches to determine partition points efficiently. Synchronization of leftMax and rightMin arrays enables satisfying partition structures.