Partition Array into Disjoint Intervals — Problem & Solution
Partition Array into Disjoint Intervals solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Partition Array into Disjoint Intervals is a medium coding problem on arrays and greedy, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Medium
- Topics: Arrays, Greedy
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an integer array nums, split it into two contiguous parts left and right so that:
- every element of
leftis less than or equal to every element ofright; - both parts are non-empty;
leftis as short as possible.
Return the length of left. A valid split is guaranteed to exist.
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
Example 3
Input: nums = [1,2]
Output: 1
Constraints
2 <= nums.length <= 400 <= nums[i] <= 1000A valid partition exists.
Hints for Partition Array into Disjoint Intervals
Hint 1
Track two maxima: the maximum of the committed left part, and the maximum seen so far overall.
Hint 2
Any element smaller than the left maximum forces the cut to move past it.
Hint 3
When that happens, the left part absorbs everything up to here, so its maximum becomes the running overall maximum.
How to solve Partition Array into Disjoint Intervals
Track the max of the committed left part and the max seen so far; any element smaller than the left max forces the cut past it, at which point the left max becomes the overall max.
Approach
- Start
leftMax = curMax = nums[0],cut = 1. - For each
i: updatecurMax; ifnums[i] < leftMax, setleftMax = curMaxandcut = i + 1. - Return
cut.
Why it works
The cut must be after every element smaller than something before it; when such an element is found, everything up to it joins the left part, whose max is then the running max. The last such event fixes the shortest valid left.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- The alternative uses prefix-max and suffix-min arrays and returns the first
iwithprefixMax[i] <= suffixMin[i+1].
Reference solution
Python
def partitionDisjoint(nums) -> int:
left_max = cur_max = nums[0]
cut = 1
for i in range(1, len(nums)):
cur_max = max(cur_max, nums[i])
if nums[i] < left_max:
left_max = cur_max
cut = i + 1
return cutJava
public static int partitionDisjoint(int[] nums) {
int leftMax = nums[0], curMax = nums[0], cut = 1;
for (int i = 1; i < nums.length; i++) {
curMax = Math.max(curMax, nums[i]);
if (nums[i] < leftMax) {
leftMax = curMax;
cut = i + 1;
}
}
return cut;
}C++
int partitionDisjoint(vector<int>& nums) {
int leftMax = nums[0], curMax = nums[0], cut = 1;
for (int i = 1; i < (int) nums.size(); i++) {
curMax = max(curMax, nums[i]);
if (nums[i] < leftMax) {
leftMax = curMax;
cut = i + 1;
}
}
return cut;
}JavaScript
var partitionDisjoint = function(nums) {
let leftMax = nums[0], curMax = nums[0], cut = 1;
for (let i = 1; i < nums.length; i++) {
if (nums[i] > curMax) curMax = nums[i];
if (nums[i] < leftMax) {
leftMax = curMax;
cut = i + 1;
}
}
return cut;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Greedy Algorithms