Partition Array into Disjoint Intervals

Problem Description

Given an integer array nums, partition it into two (contiguous) subarrays left and right so that:

• Every element in left is less than or equal to every element in right.
• left and right are non-empty.
• left has the smallest possible size.

Return the length of left after such a partitioning.

Key Insights

• We need to ensure that all elements in the left subarray are less than or equal to those in the right subarray.
• The partitioning should minimize the size of the left subarray while ensuring both subarrays are non-empty.
• To achieve this, we can track the maximum value in the left subarray and the minimum value in the right subarray as we iterate through the array.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

We can solve the problem using a single pass through the array. We will maintain two variables: the maximum value found in the left subarray and the minimum value found in the right subarray.

1. Start by determining the maximum value of the left subarray while iterating through the array.
2. Use a second iteration to find the minimum value of the right subarray.
3. Stop when the maximum of the left is less than or equal to the minimum of the right.
4. The index at which this condition holds gives the length of the left subarray.

Code Solutions