Problem Description

You are given an integer array nums. Your task is to split this array into two contiguous parts called left and right subarrays such that:

1. Every element in the left subarray must be less than or equal to every element in the right subarray. This means the maximum value in left should not exceed the minimum value in right.

2. Both subarrays must be non-empty. You cannot have an empty left or right subarray.

3. The left subarray should have the smallest possible size while still satisfying the above conditions.

Your goal is to return the length of the left subarray after performing this partition.

For example, if nums = [5, 0, 3, 8, 6], one valid partition would be left = [5, 0, 3] and right = [8, 6]. Here, the maximum of left is 5, and the minimum of right is 6. Since 5 ≤ 6, this is a valid partition. The function should return 3 (the length of the left subarray).

The problem guarantees that at least one valid partition exists for all test cases.

Intuition

To find the partition point, we need to ensure that the maximum value in the left subarray is less than or equal to the minimum value in the right subarray. This gives us the key insight: at any potential partition point i, we need to check if max(nums[0...i-1]) <= min(nums[i...n-1]).

If we try to check this condition naively for each possible partition point, we would need to compute the maximum of the left part and minimum of the right part repeatedly, which would be inefficient.

The clever observation is that we can precompute these values:

• As we move the partition point from left to right, the maximum of the left part can only increase or stay the same (since we're adding more elements to consider)
• For the minimum of the right part at each position, we can precompute all these values in advance by traversing the array from right to left

This leads us to a two-pass approach:

1. First pass (right to left): Build an array mi where mi[i] stores the minimum value from index i to the end of the array. This tells us "if we start the right subarray at position i, what would be its minimum value?"

2. Second pass (left to right): Keep track of the running maximum mx as we expand the left subarray. At each position i, we check if the current maximum of left (which ends at position i-1) is less than or equal to the minimum of right (which starts at position i). The first position where this condition holds gives us the smallest valid left subarray.

The beauty of this approach is that we only need O(n) time and O(n) space to solve the problem, making it very efficient.

Solution Approach

The solution implements the prefix maximum and suffix minimum approach to find the optimal partition point.

Step 1: Build the Suffix Minimum Array

mi = [inf] * (n + 1)
for i in range(n - 1, -1, -1):
    mi[i] = min(nums[i], mi[i + 1])

We create an array mi of size n + 1 where mi[i] stores the minimum value from index i to the end of the array. We initialize it with inf (infinity) values and traverse the array from right to left:

• mi[n] = inf (serves as a base case)
• mi[i] = min(nums[i], mi[i + 1]) for each position i

For example, if nums = [5, 0, 3, 8, 6], the mi array would be [0, 0, 3, 6, 6, inf].

Step 2: Find the Partition Point

mx = 0
for i, v in enumerate(nums, 1):
    mx = max(mx, v)
    if mx <= mi[i]:
        return i

We traverse the array from left to right, maintaining the running maximum mx of the elements seen so far (which represents the maximum of the left subarray):

• We use enumerate(nums, 1) to iterate with indices starting from 1, since i represents the length of the left subarray
• For each element v at position i-1, we update mx = max(mx, v)
• We check if mx <= mi[i], which means the maximum of left[0...i-1] is less than or equal to the minimum of right[i...n-1]
• The first position where this condition is satisfied gives us the smallest valid left subarray

Why This Works:

The algorithm guarantees to find the smallest valid partition because:

1. We check positions from left to right, so the first valid partition we find has the minimum size for the left subarray
2. The condition mx <= mi[i] ensures that every element in left is less than or equal to every element in right
3. The problem guarantees that a valid partition exists, so we will always find and return a result

Time and Space Complexity:

• Time: O(n) - two passes through the array
• Space: O(n) - for the suffix minimum array

Example Walkthrough

Let's walk through the solution with nums = [5, 0, 3, 8, 6].

Step 1: Build the Suffix Minimum Array

We create array mi to store the minimum value from each index to the end:

• Start with mi = [inf, inf, inf, inf, inf, inf] (size n+1 = 6)
• Traverse right to left:
  • i=4: mi[4] = min(nums[4], mi[5]) = min(6, inf) = 6
  • i=3: mi[3] = min(nums[3], mi[4]) = min(8, 6) = 6
  • i=2: mi[2] = min(nums[2], mi[3]) = min(3, 6) = 3
  • i=1: mi[1] = min(nums[1], mi[2]) = min(0, 3) = 0
  • i=0: mi[0] = min(nums[0], mi[1]) = min(5, 0) = 0
• Result: mi = [0, 0, 3, 6, 6, inf]

Step 2: Find the Partition Point

Traverse left to right, tracking the maximum of the left subarray:

• i=1 (considering nums[0]=5):

  • Update mx = max(0, 5) = 5
  • Check: Is mx <= mi[1]? Is 5 <= 0? No, continue

• i=2 (considering nums[1]=0):

  • Update mx = max(5, 0) = 5
  • Check: Is mx <= mi[2]? Is 5 <= 3? No, continue

• i=3 (considering nums[2]=3):

  • Update mx = max(5, 3) = 5
  • Check: Is mx <= mi[3]? Is 5 <= 6? Yes!
  • Return 3

Result Verification:

• left = [5, 0, 3] has maximum value 5
• right = [8, 6] has minimum value 6
• Since 5 ≤ 6, this is a valid partition
• The length of left is 3, which is our answer

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm consists of two main phases:

1. Building the suffix minimum array: The first loop iterates from index n-1 down to 0, performing a constant-time operation (min comparison) at each step. This takes O(n) time.
2. Finding the partition point: The second loop iterates through the array once using enumerate, performing constant-time operations (max comparison and condition check) at each step. This also takes O(n) time.

Since both loops run sequentially and each performs O(n) operations, the overall time complexity is O(n) + O(n) = O(n).

Space Complexity: O(n)

The algorithm uses additional space for:

• The mi array of size n + 1 to store suffix minimums, which requires O(n) space
• A few scalar variables (n, mx, i, v) which require O(1) space

Therefore, the total space complexity is O(n) + O(1) = O(n), where n is the length of the array nums.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Off-by-One Error in Index Management

A common mistake is confusion between the partition index and the length of the left subarray. Since we're using enumerate(nums, 1), the variable i represents the length of the left subarray, not the index of the current element.

Incorrect Implementation:

for i, value in enumerate(nums):  # i starts from 0
    max_left = max(max_left, value)
    if max_left <= min_suffix[i]:  # Wrong! This checks wrong boundary
        return i  # Returns 0-based index, not length

Why it's wrong: When i = 0, we're checking if the first element alone can be the left subarray, but min_suffix[0] includes that same element in the minimum calculation, leading to incorrect comparisons.

Correct Implementation:

for i, value in enumerate(nums, 1):  # i starts from 1
    max_left = max(max_left, value)
    if max_left <= min_suffix[i]:  # Correctly checks min of remaining elements
        return i  # Returns the length of left subarray

2. Incorrect Initialization of Maximum Value

Incorrect Implementation:

max_left = float('-inf')  # Wrong initialization
for i, value in enumerate(nums, 1):
    max_left = max(max_left, value)
    if max_left <= min_suffix[i]:
        return i

Why it's wrong: If the first element is negative, initializing with negative infinity could cause issues. However, initializing with 0 when all array elements are negative would also be incorrect.

Correct Implementation:

max_left = float('-inf')  # Actually correct for general case
# OR more explicitly:
max_left = nums[0]
for i in range(1, n):
    if max_left <= min_suffix[i]:
        return i
    max_left = max(max_left, nums[i])

3. Forgetting Edge Case Validation

While the problem guarantees a valid partition exists, in practice you might want to handle edge cases:

Defensive Implementation:

def partitionDisjoint(self, nums: List[int]) -> int:
    if not nums or len(nums) < 2:
        return -1  # or raise an exception
  
    n = len(nums)
    min_suffix = [float('inf')] * (n + 1)
    # ... rest of the solution

4. Using Wrong Comparison in Suffix Array Building

Incorrect Implementation:

# Building suffix minimum incorrectly
for i in range(n):
    min_suffix[i] = min(nums[i], min_suffix[i - 1])  # Wrong direction!

Correct Implementation:

# Build from right to left
for i in range(n - 1, -1, -1):
    min_suffix[i] = min(nums[i], min_suffix[i + 1])

The key insight is that suffix minimum must be built from right to left to correctly capture the minimum of all elements from position i to the end.