Partition Array into Disjoint Intervals
MedPrompt
Given an integer array nums, partition it into two (contiguous) subarrays left and right so that:
- Every element in
leftis less than or equal to every element inright. leftandrightare non-empty.lefthas 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] <= 106- There is at least one valid answer for the given input.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach improves upon the brute-force method by pre-calculating the necessary maximums and minimums to avoid redundant computations. We use two auxiliary arrays: one to store the running maximum from the left and another to store the running minimum from the right. This allows us to check the partition condition for any split point in constant time.
Algorithm
- Create an integer array
maxLeftof sizeN. - Traverse
numsfrom left to right to populatemaxLeft, wheremaxLeft[i]will store the maximum value innums[0...i]. - Create another integer array
minRightof sizeN. - Traverse
numsfrom right to left to populateminRight, whereminRight[i]will store the minimum value innums[i...N-1]. - Finally, iterate from
i = 0toN-2. - For each
i, check ifmaxLeft[i] <= minRight[i+1]. This is the partition conditionmax(left) <= min(right). - The first index
ithat satisfies this condition gives the smallestleftpartition. Returni + 1.
Walkthrough
The core condition is max(nums[0...i]) <= min(nums[i+1...N-1]). Instead of recalculating these values in each iteration, we can precompute them.
- Create an array
maxLeftwheremaxLeft[i]stores the maximum value in the subarraynums[0...i]. This can be computed in a single pass from left to right. - Create an array
minRightwhereminRight[i]stores the minimum value in the subarraynums[i...N-1]. This can be computed in a single pass from right to left. - With these arrays, we can check the condition for each
iin O(1) time. We iterate fromi = 0toN-2and check ifmaxLeft[i] <= minRight[i+1]. The firstithat satisfies this gives the smallestleftpartition of lengthi+1.
class Solution { public int partitionDisjoint(int[] nums) { int n = nums.length; int[] maxLeft = new int[n]; maxLeft[0] = nums[0]; for (int i = 1; i < n; i++) { maxLeft[i] = Math.max(maxLeft[i - 1], nums[i]); } int[] minRight = new int[n]; minRight[n - 1] = nums[n - 1]; for (int i = n - 2; i >= 0; i--) { minRight[i] = Math.min(minRight[i + 1], nums[i]); } for (int i = 0; i < n - 1; i++) { if (maxLeft[i] <= minRight[i + 1]) { return i + 1; } } return -1; // Should not be reached }}Complexity
Time
O(N). We make three separate passes through the array (one for `maxLeft`, one for `minRight`, and one for the final check), each taking O(N) time. This simplifies to O(N).
Space
O(N), as we use two auxiliary arrays, `maxLeft` and `minRight`, each of size N.
Trade-offs
Pros
Significantly more efficient than the brute-force approach with linear time complexity.
Guaranteed to pass within the time limits for the given constraints.
Cons
Uses extra space proportional to the input size, which might be a concern for very large arrays in a memory-constrained environment.
Solutions
Solution
class Solution {public int partitionDisjoint(int[] nums) { int n = nums.length; int[] mi = new int[n + 1]; mi[n] = nums[n - 1]; for (int i = n - 1; i >= 0; --i) { mi[i] = Math.min(nums[i], mi[i + 1]); } int mx = 0; for (int i = 1; i <= n; ++i) { int v = nums[i - 1]; mx = Math.max(mx, v); if (mx <= mi[i]) { return i; } } return 0; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.