915. Partition Array into Disjoint Intervals

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.

Test cases are generated such that partitioning exists.
 

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<=10^5$
• $0<=nums[i]<=10^6$
• There is at least one valid answer for the given input.

From: LeetCode
Link: 915. Partition Array into Disjoint Intervals

Solution:

Ideas:

• Time: O(n) single pass

• Space: O(1)

• Why it works: Whenever an element in the right candidate is < leftMax, the partition is invalid; we extend left to include it and update leftMax to the best max seen so far (curMax), restoring the invariant that all in left ≤ all in future right.

Code:

int partitionDisjoint(int* nums, int numsSize) {
    // Invariants:
    // left = [0 .. idx], right = [idx+1 .. end)
    // leftMax = max(nums[0..idx])
    // curMax  = max(nums[0..i]) while scanning
    int idx = 0;
    int leftMax = nums[0];
    int curMax  = nums[0];

    for (int i = 1; i < numsSize; ++i) {
        if (nums[i] < leftMax) {
            // Need to extend left to include i
            idx = i;
            leftMax = curMax;   // new leftMax becomes the best we've seen so far
        } else if (nums[i] > curMax) {
            curMax = nums[i];
        }
    }
    return idx + 1; // length of left
}