Given an integer array nums, partition it into two (contiguous) subarrays left and right so that:
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 <= 1050 <= nums[i] <= 106Problem 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.
This approach involves maintaining a running maximum for the left subarray and a suffix minimum for the right subarray. By iterating through the array and comparing these values, we can determine the appropriate partition point where all conditions are satisfied.
The C solution uses two variables, maxLeft and maxSoFar, to track the maximum values during the iteration through the array. Whenever we encounter an element smaller than maxLeft, it updates the partition index to that position and sets maxLeft to maxSoFar. This ensures all conditions of the partition are maintained.
Time Complexity: O(n) - Linear scan of the array.
Space Complexity: O(1) - Only variables used for tracking, no extra storage required.
This approach involves using two additional arrays: one to track the maximum values until any index from the left and another to track minimum values from the right. These auxiliary arrays help determine where a valid partition can be made in the original array.
In this C solution, two arrays leftMax and rightMin are used to keep track of the maximum values up to an index and the minimum values from an index onward. By comparing elements from leftMax and rightMin, we determine the appropriate partition point.
Time Complexity: O(n) - Needs three linear passes through the array.
Space Complexity: O(n) - Additional space for two auxiliary arrays.
To satisfy the requirements of the problem after partitioning into two subarrays, we need to ensure that the "maximum value of the array prefix" is less than or equal to the "minimum value of the array suffix".
Therefore, we can first preprocess the minimum value of the array suffix and record it in the mi array.
Then, we traverse the array from front to back, maintaining the maximum value mx of the array prefix. When we traverse to a certain position, if the maximum value of the array prefix is less than or equal to the minimum value of the array suffix, then the current position is the dividing point of the partition, and we can return it directly.
The time complexity is O(n), and the space complexity is O(n). Where n is the length of the array nums.
| Approach | Complexity |
|---|---|
| Prefix and Suffix Tracking | Time Complexity: O(n) - Linear scan of the array. |
| Two Array Auxiliary Tracking | Time Complexity: O(n) - Needs three linear passes through the array. |
| Prefix Maximum + Suffix Minimum | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two Array Auxiliary Tracking | O(n) | O(n) | When clarity matters and preprocessing with prefix/suffix arrays is acceptable. |
| Prefix and Suffix Tracking (Optimized) | O(n) | O(1) | Best for interviews and production where constant extra memory is preferred. |
Partition Array Into Disjoint Intervals in O(n) Space | Leetcode 915 | Solution in Hindi • Pepcoding • 7,211 views views
Watch 9 more video solutions →Practice Partition Array into Disjoint Intervals with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor