Partition Array into Disjoint Intervals

Naive Solution

A brute-force approach would be to iterate through all possible split points of the array, creating left and right subarrays at each split. For each split, check if the maximum element in left is less than or equal to the minimum element in right. The first split that satisfies this condition gives the desired length of the left subarray.

Code (Python)

def partition_array_naive(nums):
    for i in range(1, len(nums)):
        left = nums[:i]
        right = nums[i:]
        if max(left) <= min(right):
            return i
    return len(nums)  # Should not happen as problem guarantees a solution

Time Complexity

O(n^2) in the worst case because, for each possible split point, we compute max(left) and min(right) which take O(n) time.

Space Complexity

O(1) since we are only using a constant amount of extra space.

Optimal Solution

We can improve the time complexity by pre-computing the maximum value from the left and the minimum value from the right for each index. This way, we only need to iterate once to find the partition point.

Algorithm

1. Create two arrays, max_left and min_right, of the same size as the input array nums.
2. max_left[i] stores the maximum value in nums[0...i]. We can compute this in one pass.
3. min_right[i] stores the minimum value in nums[i...n-1]. We can compute this in one pass from right to left.
4. Iterate from i = 1 to n-1. If max_left[i-1] <= min_right[i], then i is the partition index. Return i.

Code (Python)

def partition_array_optimal(nums):
    n = len(nums)
    max_left = [0] * n
    min_right = [0] * n

    max_left[0] = nums[0]
    for i in range(1, n):
        max_left[i] = max(max_left[i - 1], nums[i])

    min_right[n - 1] = nums[n - 1]
    for i in range(n - 2, -1, -1):
        min_right[i] = min(min_right[i + 1], nums[i])

    for i in range(1, n):
        if max_left[i - 1] <= min_right[i]:
            return i

    return n  # Should not happen as problem guarantees a solution

Time Complexity

O(n) because we iterate through the array three times.

Space Complexity

O(n) due to the max_left and min_right arrays.

Edge Cases

• Empty array: The problem states that 2 <= nums.length. So, an empty array is not a valid input.
• Single element array: Not a valid input, same reason as above.
• All elements are the same: The algorithm should still find a valid split.
• Sorted array: If the input array nums is sorted in ascending order, the first element forms the left subarray.
• Reverse-sorted array: If the input array nums is sorted in descending order, the algorithm will iterate until the end to find the split.