Partition Array into Disjoint Intervals

medium array prefix max partition

Problem

Given an integer array nums, partition it into two contiguous parts left and right so that every element in left is less than or equal to every element in right, and left is as small as possible. Both parts must be non-empty. Return the length of left. A valid partition is guaranteed to exist.

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

Output3

left = [5, 0, 3], right = [8, 6]. Every left value (max 5) is ≤ every right value (min 6).

nums (comma-separated)

def partition_disjoint(nums):
    left_max = cur_max = nums[0]
    length = 1
    for i in range(1, len(nums)):
        if nums[i] < left_max:
            length = i + 1
            left_max = cur_max
        else:
            cur_max = max(cur_max, nums[i])
    return length

function partitionDisjoint(nums) {
  let leftMax = nums[0], curMax = nums[0];
  let length = 1;
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] < leftMax) {
      length = i + 1;
      leftMax = curMax;
    } else {
      curMax = Math.max(curMax, nums[i]);
    }
  }
  return length;
}

class Solution {
    public int partitionDisjoint(int[] nums) {
        int leftMax = nums[0], curMax = nums[0];
        int length = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < leftMax) {
                length = i + 1;
                leftMax = curMax;
            } else {
                curMax = Math.max(curMax, nums[i]);
            }
        }
        return length;
    }
}

int partitionDisjoint(vector<int>& nums) {
    int leftMax = nums[0], curMax = nums[0];
    int length = 1;
    for (int i = 1; i < (int)nums.size(); i++) {
        if (nums[i] < leftMax) {
            length = i + 1;
            leftMax = curMax;
        } else {
            curMax = max(curMax, nums[i]);
        }
    }
    return length;
}

Explanation

We want the shortest possible left part such that every left value is at most every right value. The key realization is that this holds exactly when the maximum of the left part is no bigger than every element still on the right.

We track two maxes in a single pass. leftMax is the maximum of the part we have committed to the left, and curMax is the maximum of everything seen so far (which may eventually be pulled into the left).

For each element: if it is smaller than leftMax, it cannot sit on the right, so the left part must stretch to include it. We extend length to i + 1 and raise leftMax to curMax, since everything up to here is now part of the left. Otherwise the element can stay on the right, and we just update curMax.

Example: nums = [5, 0, 3, 8, 6]. The 0 and 3 are below leftMax = 5, forcing them left, so length becomes 3. The 8 and 6 are both at least 5 and stay right. The answer is left length 3.

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