915. Partition Array into Disjoint Intervals LeetCode Solution
In this guide, you will get 915. Partition Array into Disjoint Intervals LeetCode Solution with the best time and space complexity. The solution to Partition Array into Disjoint Intervals problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Partition Array into Disjoint Intervals
Given an integer array nums, partition it into two (contiguous) subarrays left and right so that:
Every element in 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 <= 105
0 <= nums[i] <= 106
There is at least one valid answer for the given input.
Complexity Analysis
Time Complexity:
Space Complexity:
915. Partition Array into Disjoint Intervals LeetCode Solution in C++
class Solution {
public:
int partitionDisjoint(vector<int>& nums) {
const int n = nums.size();
vector<int> mn(n);
mn[n - 1] = nums[n - 1];
int mx = INT_MIN;
for (int i = n - 2; i >= 0; --i)
mn[i] = min(mn[i + 1], nums[i]);
for (int i = 0; i < n; ++i) {
mx = max(mx, nums[i]);
if (mx <= mn[i + 1])
return i + 1;
}
throw;
}
}; /* code provided by PROGIEZ */
915. Partition Array into Disjoint Intervals LeetCode Solution in Java
class Solution {
public int partitionDisjoint(int[] nums) {
final int n = nums.length;
int[] mn = new int[n];
mn[n - 1] = nums[n - 1];
int mx = Integer.MIN_VALUE;
for (int i = n - 2; i >= 0; --i)
mn[i] = Math.min(mn[i + 1], nums[i]);
for (int i = 0; i < n; ++i) {
mx = Math.max(mx, nums[i]);
if (mx <= mn[i + 1])
return i + 1;
}
throw new IllegalArgumentException();
}
} // code provided by PROGIEZ
915. Partition Array into Disjoint Intervals LeetCode Solution in Python
class Solution:
def partitionDisjoint(self, nums: list[int]) -> int:
n = len(nums)
mn = [0] * (n - 1) + [nums[-1]]
mx = -math.inf
for i in range(n - 2, - 1, -1):
mn[i] = min(mn[i + 1], nums[i])
for i, num in enumerate(nums):
mx = max(mx, num)
if mx <= mn[i + 1]:
return i + 1 # code by PROGIEZ
