Partition Array into Disjoint Intervals

Problem Statement

The task is to perform a specific partition on an integer array nums into two contiguous subarrays, left and right. The partitioning must be done such that every member of left is less than or equal to each member of right, each subarray must contain at least one element, and left should be as small as possible in terms of length. The outcome needed is the size of the subarray left after making the optimal partition.

Examples

Example 1

Input:

nums = [5,0,3,8,6]

Output:

3

Explanation:

left = [5,0,3], right = [8,6]

Example 2

Input:

nums = [1,1,1,0,6,12]

Output:

4

Explanation:

left = [1,1,1,0], right = [6,12]

Constraints

• 2 <= nums.length <= 105
• 0 <= nums[i] <= 106
• There is at least one valid answer for the given input.

Approach and Intuition

The essence of this problem revolves around determining a point in the array where every element to the left does not exceed any element to the right. This requires both a keen understanding of array traversal and decision-making based on the properties encountered during this traversal. Let's break down the approach:

1. Traverse the array from right to left, calculating the minimum value (min_right[i]) from index i to n-1 (where n is the length of the array). This helps in identifying the smallest possible value to the right for each element.

2. Similarly, traverse the array from left to right to compute the maximum value (max_left[i]) for all elements from the start of the array to index i.

3. The partition point lies where max_left[i] is less than or equal to min_right[i+1] since this would be the smallest index which ensures all elements in left are necessarily less than or equal to elements in right.

4. Upon finding such a point, the size of left can simply be i + 1 because this ensures left includes elements from index 0 to i.

By following this strategy, one can determine the minimal size for left which satisfies the condition of each element in left being less than or equal to every element in right. This approach efficiently calculates the necessary partitioning point by leveraging the minima and maxima of subarrays—a classical example of using array preprocessing to simplify a complicated conditional partition problem.

Solutions

class Solution {
public:
    int findPartition(vector<int>& values) {
        int currentMaximum = values[0];
        int maxSoFar = values[0];
        int partitionIndex = 1;
            
        for (int idx = 1; idx < values.size(); ++idx) {
            if (values[idx] < currentMaximum) {
                partitionIndex = idx + 1;
                currentMaximum = maxSoFar;
            } else {
                maxSoFar = max(maxSoFar, values[idx]);
            }
        }
            
        return partitionIndex;
    }
};