Partition Array into Disjoint Intervals - Video Solutions

Problem Overview: You are given an integer array nums. Split it into two non-empty parts left and right such that every element in left is less than or equal to every element in right. Return the smallest possible size of the left partition.

The constraint forces a clear ordering rule: max(left) ≤ min(right). The challenge is finding the earliest index where this condition holds while scanning the array efficiently. Since the input size can be large, the goal is an O(n) scan using simple array operations.

Approach 1: Two Array Auxiliary Tracking (O(n) time, O(n) space)

Precompute two helper arrays: prefixMax and suffixMin. The prefixMax[i] stores the maximum value from index 0 to i, while suffixMin[i] stores the minimum value from i to the end. Once these arrays are built, iterate through possible partition points and check whether prefixMax[i] ≤ suffixMin[i + 1]. The first index satisfying this condition gives the smallest valid partition. This method is straightforward and easy to reason about, making it a good first implementation when practicing array preprocessing patterns.

Approach 2: Prefix and Suffix Tracking (O(n) time, O(1) space)

The auxiliary arrays can be eliminated by tracking only the values needed during iteration. Maintain two variables: leftMax (maximum value in the current left partition) and globalMax (maximum value seen so far while scanning). Iterate through the array once. If the current value is smaller than leftMax, the partition must extend to this index because the right side cannot contain smaller elements. Update the partition index and set leftMax = globalMax. Otherwise, update globalMax if needed. This greedy-style scan works because the moment a violation appears, the partition boundary must expand to include that value. The approach achieves optimal O(n) time with constant extra space and relies purely on sequential array traversal and simple comparisons.

Recommended for interviews: The prefix/suffix auxiliary array method shows clear understanding of the condition max(left) ≤ min(right). However, most interviewers expect the optimized single-pass solution with O(1) space. Demonstrating both approaches signals strong problem-solving ability: start with the intuitive preprocessing method, then refine it to the constant-space greedy scan.