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.
This approach involves checking every possible way to partition the array into two non-empty contiguous subarrays. For each potential partition, we explicitly calculate the maximum of the left part and the minimum of the right part and see if the condition holds. Since we need the smallest left partition, we check the partitions in increasing order of their size.
Algorithm
- Iterate through all possible partition points
ifrom0ton-2, wherenis the length of the array. - For each
i, theleftsubarray isnums[0...i]and therightsubarray isnums[i+1...n-1]. - In an inner loop, find the maximum element
max_leftin theleftsubarray. - In another inner loop, find the minimum element
min_rightin therightsubarray. - Check if the condition
max_left <= min_rightis satisfied. - If it is, we have found the smallest possible
leftpartition because we are iteratingifrom the smallest possible value. Return the lengthi + 1immediately.
Walkthrough
We can iterate through all possible lengths of the left subarray, from 1 to n-1. Let the partition be after index i. The left subarray is nums[0...i] and the right is nums[i+1...n-1]. For each i, we find max_left, the maximum element in left, and min_right, the minimum element in right. If max_left <= min_right, we have found a valid partition. Since we are iterating i from 0 upwards, the first valid partition we find will correspond to the smallest possible left subarray. We can then return its length, which is i+1.
class Solution { public int partitionDisjoint(int[] nums) { int n = nums.length; for (int i = 0; i < n - 1; i++) { int maxLeft = 0; for (int j = 0; j <= i; j++) { maxLeft = Math.max(maxLeft, nums[j]); } int minRight = 1000001; // Constraints: 0 <= nums[i] <= 10^6 for (int k = i + 1; k < n; k++) { minRight = Math.min(minRight, nums[k]); } if (maxLeft <= minRight) { return i + 1; } } return -1; // Should not be reached as a solution is guaranteed }}Complexity
Time
O(N^2), where N is the length of `nums`. The outer loop runs N-1 times. Inside, we have two loops that in total scan the entire array, taking O(N) time for each outer loop iteration.
Space
O(1), as we only use a few variables to store the max and min values, not dependent on the input size.
Trade-offs
Pros
Simple to understand and implement.
Correct for small inputs.
Cons
Highly inefficient due to nested loops.
Will likely result in a 'Time Limit Exceeded' (TLE) error on platforms like LeetCode for larger inputs as per the constraints.
This is the most optimal approach, solving the problem in a single pass with constant extra space. The idea is to iterate through the array, maintaining a candidate left partition. We greedily extend this left partition whenever we encounter an element that violates the partition condition, ensuring that by the end, we have found the smallest possible valid partition.
Algorithm
- Initialize three variables:
partitionIdx = 0,leftMax = nums[0], andcurrentMax = nums[0]. partitionIdxwill store the end index of our candidateleftpartition.leftMaxwill store the maximum value within the candidateleftpartition (nums[0...partitionIdx])currentMaxwill track the maximum value seen so far as we iterate through the array.- Iterate through the array from the second element (
i = 1ton-1). - In each iteration, update
currentMax = max(currentMax, nums[i]). - Check if the current element
nums[i]is less thanleftMax. - If
nums[i] < leftMax, it means our current partition is invalid becausenums[i]must belong to theleftpart. To fix this, we must extend theleftpartition to includenums[i]. We do this by updatingpartitionIdx = iand also updatingleftMaxtocurrentMax, since the newleftpartition's maximum is now the maximum of all elements seen so far. - After the loop finishes,
partitionIdxholds the correct end index for the smallestleftpartition. ReturnpartitionIdx + 1.
Walkthrough
We can solve this problem by iterating through the array just once. We maintain three variables:
partitionIdx: The index where the currentleftpartition ends.leftMax: The maximum value in the currentleftpartition (nums[0...partitionIdx]).currentMax: The maximum value encountered so far as we iterate through the array (nums[0...i]).
We initialize partitionIdx = 0, leftMax = nums[0], and currentMax = nums[0]. Then, we iterate from i = 1 to N-1. In each step, we update currentMax. The key idea is that if we find an element nums[i] that is smaller than leftMax, it means our current partition is invalid. This nums[i] must belong to the left partition, otherwise, the condition max(left) <= min(right) would be violated (min(right) <= nums[i] < leftMax). Therefore, we must extend the left partition to include this element. We update partitionIdx to i. When we extend the partition, the new leftMax must be the maximum of all elements in the new left partition, which is currentMax. After iterating through the entire array, partitionIdx + 1 gives the length of the smallest valid left partition.
class Solution { public int partitionDisjoint(int[] nums) { int partitionIdx = 0; int leftMax = nums[0]; int currentMax = nums[0]; for (int i = 1; i < nums.length; i++) { currentMax = Math.max(currentMax, nums[i]); if (nums[i] < leftMax) { // This element must be in the left partition. // The partition must extend to at least this index. partitionIdx = i; // The new max for the left partition is the max // of all elements seen so far. leftMax = currentMax; } } return partitionIdx + 1; }}Complexity
Time
O(N), as we iterate through the array only once.
Space
O(1), as we only use a few constant extra variables regardless of the input size.
Trade-offs
Pros
Optimal solution with O(N) time complexity.
Extremely space-efficient with O(1) space complexity.
Solves the problem in a single pass over the data.
Cons
The logic can be less intuitive to come up with compared to the more straightforward brute-force or two-pass methods.
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; }}class Solution: def partitionDisjoint(self, nums: List[int]) -> int: n = len(nums) mi = [inf] * (n + 1) for i in range(n - 1, - 1, - 1): mi[i] = min(nums[i], mi[i + 1]) mx = 0 for i, v in enumerate(nums, 1): mx = max(mx, v) if mx <= mi[i]: return iclass Solution {public: int partitionDisjoint(vector<int> &nums) { int n = nums.size(); vector<int> mi(n + 1, INT_MAX); for (int i = n - 1; ~i; --i) mi[i] = min(nums[i], mi[i + 1]); int mx = 0; for (int i = 1; i <= n; ++i) { int v = nums[i - 1]; mx = 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.