Leetcode 915. Partition Array into Disjoint Intervals
Problem Explanation
The problem statement asks to partition a given array into two subarrays such that each element in the first array is less or equal than each element in the second array. The first array should be as small as possible, but at least one element needs to be included. The output should be the length of the first array.
In simpler terms, we can say we need to split the array into two partitions such that all the elements in the left partition are smaller than or equal to the elements in the right partition. We also need to make the left partition as small as possible without being empty.
For example, consider an array [1, 1, 1, 0, 6, 12], here, the left partition could be [1, 1, 1, 0] and the right partition could be [6, 12].
Solution Explanation
To solve this problem, we use a simple approach that involves a single pass through the array.
We initialize variables min
and max
. min
is an array of the same size as the input array and max
is initialized to the smallest possible integer. min
keeps track of the minimum element in the array from the current position to the end of the array. max
keeps track of the maximum element seen so far.
We first fill the min
array in reverse order, with each position holding the minimum number among the current array's element and the next position in the min
array. That way, for each index i in min
, it'll hold the smallest element from i to the end of the array.
Next, we iterate over the input array from left to right. For each element in the input array, we update max
to the maximum of the current max
and the current element. Then, we check if max
is less than or equal to the next element in our min
array. If so, we've found our partition point as we're assured all numbers to the right of our current position are larger or equal max
. We return the current position + 1 as the length of the left partition.
Code Explanation (using C++)
1
2c++
3// Adding necessary libraries
4#include <vector> // For std::vector
5#include <algorithm> // For std::min and std::max
6
7class Solution {
8public:
9 int partitionDisjoint(vector<int>& nums) {
10 int n = nums.size(); // number of elements in the given array
11 vector<int> min(n); // Define vector min with size n
12 min[n - 1] = nums[n - 1]; // Set last element of min as last element of array
13 int max = INT_MIN; // Set max to the smallest possible int
14
15 // Populate the min array
16 for (int i = n - 2; i >= 0; --i)
17 min[i] = std::min(min[i + 1], nums[i]);
18
19 // Find where to partition our array
20 for (int i = 0; i < n; ++i) {
21 max = std::max(max, nums[i]);
22 // Check if max is less or equal to next min,
23 // If true we found our partition point
24 if (max <= min[i + 1])
25 return i + 1;
26 }
27
28 // This will never be reached due to problem constraints, but we need to satisfy the compiler
29 throw;
30 }
31};
This solution ensures that we find the smallest possible left partition while also guaranteeing that each element in the left partition is less than or equal to each element in the right partition.# Python Solution
1
2python
3def partitionDisjoint(nums):
4 n = len(nums)
5 min = [0] * n
6 min[n - 1] = nums[n - 1]
7 max_ = float('-inf')
8
9 for i in range(n - 2, -1, -1):
10 min[i] = min(min[i + 1], nums[i])
11
12 for i in range(n):
13 max_ = max(max_, nums[i])
14 if max_ <= min[i + 1]:
15 return i + 1
JavaScript Solution
1 2javascript 3var partitionDisjoint = function(nums) { 4 let n = nums.length; 5 let min = new Array(n); 6 min[n - 1] = nums[n - 1]; 7 let max = Number.MIN_SAFE_INTEGER; 8 9 for (let i = n - 2; i >= 0; --i){ 10 min[i] = Math.min(min[i + 1], nums[i]); 11 } 12 13 for (let i = 0; i < n; i++){ 14 max = Math.max(max, nums[i]); 15 if (max <= min[i + 1]){ 16 return i + 1; 17 } 18 } 19};
Java Solution
1 2java 3class Solution { 4 public int partitionDisjoint(int[] nums) { 5 int n = nums.length; 6 int[] min = new int[n]; 7 min[n - 1] = nums[n - 1]; 8 int max = Integer.MIN_VALUE; 9 10 for (int i = n - 2; i >= 0; i--){ 11 min[i] = Math.min(min[i + 1], nums[i]); 12 } 13 14 for (int i = 0; i < n; i++){ 15 max = Math.max(max, nums[i]); 16 if (max <= min[i + 1]){ 17 return i + 1; 18 } 19 } 20 21 throw new IllegalArgumentException("No solution exists"); 22 } 23}
These Python, JavaScript, and Java solutions also include the creation of a min array and a max value. These approaches follow the same logic, building a min array from right to left and then checking the condition from left to right, returning the partition point when the condition is met. They have a time complexity of O(n) and a space complexity of O(n), where n is size of array.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.