Partition Array into Disjoint Intervals solution and explanation
Google
9 more videos on this problem
Partition Array Into Disjoint Intervals in O(n) Space | Leetcode 915 | Solution in HindiPepcoding · 19:40 · 7K views
Partition Array into Disjoint Intervals | Leetcode 915 | Live coding session 🔥🔥🔥Coding Decoded · 12:45 · 3K views
Partition Array into Disjoint Intervals | LeetCode 915 | C++, Java, PythonKnowledge Center · 20:13 · 2K views
Partition Array into Disjoint Intervals | Leetcode 915 | C++ | Python | Medium | Approach + CodeAyushi Sharma · 15:25 · 1K views
Partition Array into Disjoint Intervals | Leetcode 915 | Array | MicrosoftNaresh Gupta · 14:10 · 1K views
Partition Array into Disjoint Intervals | LeetCode 915 | Theory + PythonSai Anish Malla · 17:10 · 523 views
Partition Array into Disjoint Intervals | LeetCode 915 | Coders CampCoders Camp · 13:54 · 398 views
Daily Leetcode #478: Jul 22, 2021 - 915. Partition Array into Disjoint IntervalsProgramming Live with Larry · 7:19 · 365 views
Partition Array into Disjoint Intervals (LeetCode 915) - with codeCODING HEIST · 6:28 · 257 views
No Sound Leetcode 915: Partition Array into Disjoint IntervalsExtremeProgrammer · 1:55 · 56 views
The problem
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.
Approach overview
Problem Overview: You are given an integer array nums. Split it into two non-empty parts left and right such that every element in left is less than or equal to every element in right. Return the smallest possible size of the left partition.
The constraint forces a clear ordering rule: max(left) ≤ min(right). The challenge is finding the earliest index where this condition holds while scanning the array efficiently. Since the input size can be large, the goal is an O(n) scan using simple array operations.
Approach 1: Two Array Auxiliary Tracking (O(n) time, O(n) space)
Precompute two helper arrays: prefixMax and suffixMin. The prefixMax[i] stores the maximum value from index 0 to i, while suffixMin[i] stores the minimum value from i to the end. Once these arrays are built, iterate through possible partition points and check whether prefixMax[i] ≤ suffixMin[i + 1]. The first index satisfying this condition gives the smallest valid partition. This method is straightforward and easy to reason about, making it a good first implementation when practicing array preprocessing patterns.
Approach 2: Prefix and Suffix Tracking (O(n) time, O(1) space)
The auxiliary arrays can be eliminated by tracking only the values needed during iteration. Maintain two variables: leftMax (maximum value in the current left partition) and globalMax (maximum value seen so far while scanning). Iterate through the array once. If the current value is smaller than leftMax, the partition must extend to this index because the right side cannot contain smaller elements. Update the partition index and set leftMax = globalMax. Otherwise, update globalMax if needed. This greedy-style scan works because the moment a violation appears, the partition boundary must expand to include that value. The approach achieves optimal O(n) time with constant extra space and relies purely on sequential array traversal and simple comparisons.
Recommended for interviews: The prefix/suffix auxiliary array method shows clear understanding of the condition max(left) ≤ min(right). However, most interviewers expect the optimized single-pass solution with O(1) space. Demonstrating both approaches signals strong problem-solving ability: start with the intuitive preprocessing method, then refine it to the constant-space greedy scan.
Approach 1: Prefix and Suffix Tracking
This approach involves maintaining a running maximum for the left subarray and a suffix minimum for the right subarray. By iterating through the array and comparing these values, we can determine the appropriate partition point where all conditions are satisfied.
def partitionDisjoint(nums):
max_left = nums[0]
max_so_far = nums[0]
partition_idx = 0
for i in range(1, len(nums)):
if nums[i] < max_left:
max_left = max_so_far
partition_idx = i
else:
max_so_far = max(max_so_far, nums[i])
return partition_idx + 1
print(partitionDisjoint([5, 0, 3, 8, 6])) # Output: 3public class PartitionArray {
public static int partitionDisjoint(int[] nums) {
int maxLeft = nums[0], maxSoFar = nums[0], partitionIdx = 0;
for (int i = 1; i < nums.length; i++) {
if (nums[i] < maxLeft) {
maxLeft = maxSoFar;
partitionIdx = i;
} else if (nums[i] > maxSoFar) {
maxSoFar = nums[i];
}
}
return partitionIdx + 1;
}
public static void main(String[] args) {
int[] nums = {5, 0, 3, 8, 6};
System.out.println(partitionDisjoint(nums)); // Output: 3
}
}#include <iostream>
#include <vector>
using namespace std;
int partitionDisjoint(vector<int>& nums) {
int maxLeft = nums[0], maxSoFar = nums[0], partitionIdx = 0;
for (int i = 1; i < nums.size(); ++i) {
if (nums[i] < maxLeft) {
maxLeft = maxSoFar;
partitionIdx = i;
} else if (nums[i] > maxSoFar) {
maxSoFar = nums[i];
}
}
return partitionIdx + 1;
}
int main() {
vector<int> nums = {5, 0, 3, 8, 6};
cout << partitionDisjoint(nums) << endl; // Output: 3
return 0;
}function partitionDisjoint(nums) {
let maxLeft = nums[0];
let maxSoFar = nums[0];
let partitionIdx = 0;
for (let i = 1; i < nums.length; i++) {
if (nums[i] < maxLeft) {
maxLeft = maxSoFar;
partitionIdx = i;
} else {
maxSoFar = Math.max(maxSoFar, nums[i]);
}
}
return partitionIdx + 1;
}
console.log(partitionDisjoint([5, 0, 3, 8, 6])); // Output: 3#include <stdio.h>
int partitionDisjoint(int* nums, int numsSize) {
int maxLeft = nums[0];
int partitionIdx = 0;
int maxSoFar = nums[0];
for (int i = 1; i < numsSize; i++) {
if (nums[i] < maxLeft) {
partitionIdx = i;
maxLeft = maxSoFar;
} else {
if (nums[i] > maxSoFar) {
maxSoFar = nums[i];
}
}
}
return partitionIdx + 1;
}
int main() {
int nums[] = {5, 0, 3, 8, 6};
int result = partitionDisjoint(nums, 5);
printf("%d\n", result); // Output: 3
return 0;
}using System;
public class PartitionArray {
public static int PartitionDisjoint(int[] nums) {
int maxLeft = nums[0];
int maxSoFar = nums[0];
int partitionIdx = 0;
for (int i = 1; i < nums.Length; i++) {
if (nums[i] < maxLeft) {
maxLeft = maxSoFar;
partitionIdx = i;
} else if (nums[i] > maxSoFar) {
maxSoFar = nums[i];
}
}
return partitionIdx + 1;
}
public static void Main() {
int[] nums = {5, 0, 3, 8, 6};
Console.WriteLine(PartitionDisjoint(nums)); // Output: 3
}
}The Python solution achieves the partitioning by maintaining current maximums within the loop as it traverses the array. The partition index is adjusted whenever an element smaller than max_left is found, ensuring a valid disjoint partition is maintained.
Time Complexity: O(n) - A single traversal of the array suffices.
Space Complexity: O(1) - Constant space requirement for variables.
Approach 2: Two Array Auxiliary Tracking
This approach involves using two additional arrays: one to track the maximum values until any index from the left and another to track minimum values from the right. These auxiliary arrays help determine where a valid partition can be made in the original array.
def partitionDisjoint(nums):
n = len(nums)
left_max = [0] * n
right_min = [0] * n
left_max[0] = nums[0]
for i in range(1, n):
left_max[i] = max(nums[i], left_max[i - 1])
right_min[n - 1] = nums[n - 1]
for i in range(n - 2, -1, -1):
right_min[i] = min(nums[i], right_min[i + 1])
for i in range(n - 1):
if left_max[i] <= right_min[i + 1]:
return i + 1
print(partitionDisjoint([5, 0, 3, 8, 6])) # Output: 3import java.util.*;
public class PartitionArray {
public int partitionDisjoint(int[] nums) {
int n = nums.length;
int[] leftMax = new int[n];
int[] rightMin = new int[n];
leftMax[0] = nums[0];
for (int i = 1; i < n; i++) {
leftMax[i] = Math.max(nums[i], leftMax[i - 1]);
}
rightMin[n - 1] = nums[n - 1];
for (int i = n - 2; i >= 0; i--) {
rightMin[i] = Math.min(nums[i], rightMin[i + 1]);
}
for (int i = 0; i < n - 1; i++) {
if (leftMax[i] <= rightMin[i + 1]) {
return i + 1;
}
}
return n; // placeholder, assuming problem constraints are met.
}
public static void main(String[] args) {
int[] nums = {5, 0, 3, 8, 6};
PartitionArray solution = new PartitionArray();
System.out.println(solution.partitionDisjoint(nums)); // Output: 3
}
}#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int partitionDisjoint(vector<int>& nums) {
int n = nums.size();
vector<int> leftMax(n), rightMin(n);
leftMax[0] = nums[0];
for (int i = 1; i < n; ++i) {
leftMax[i] = max(nums[i], leftMax[i - 1]);
}
rightMin[n - 1] = nums[n - 1];
for (int i = n - 2; i >= 0; --i) {
rightMin[i] = min(nums[i], rightMin[i + 1]);
}
for (int i = 0; i < n - 1; ++i) {
if (leftMax[i] <= rightMin[i + 1]) {
return i + 1;
}
}
return n;
}
int main() {
vector<int> nums = {5, 0, 3, 8, 6};
cout << partitionDisjoint(nums) << endl; // Output: 3
return 0;
}function partitionDisjoint(nums) {
const n = nums.length;
const leftMax = Array(n).fill(0);
const rightMin = Array(n).fill(0);
leftMax[0] = nums[0];
for (let i = 1; i < n; i++) {
leftMax[i] = Math.max(nums[i], leftMax[i - 1]);
}
rightMin[n - 1] = nums[n - 1];
for (let i = n - 2; i >= 0; i--) {
rightMin[i] = Math.min(nums[i], rightMin[i + 1]);
}
for (let i = 0; i < n - 1; i++) {
if (leftMax[i] <= rightMin[i + 1]) {
return i + 1;
}
}
return n; // placeholder
}
console.log(partitionDisjoint([5, 0, 3, 8, 6])); // Output: 3#include <stdio.h>
#include <limits.h>
int partitionDisjoint(int* nums, int numsSize) {
int leftMax[numsSize];
int rightMin[numsSize];
leftMax[0] = nums[0];
for (int i = 1; i < numsSize; ++i) {
leftMax[i] = (nums[i] > leftMax[i - 1]) ? nums[i] : leftMax[i - 1];
}
rightMin[numsSize - 1] = nums[numsSize - 1];
for (int i = numsSize - 2; i >= 0; --i) {
rightMin[i] = (nums[i] < rightMin[i + 1]) ? nums[i] : rightMin[i + 1];
}
for (int i = 0; i < numsSize - 1; ++i) {
if (leftMax[i] <= rightMin[i + 1])
return i + 1;
}
return numsSize; // Default return, problem guarantees an answer exists
}
int main() {
int nums[] = {5, 0, 3, 8, 6};
printf("%d\n", partitionDisjoint(nums, 5)); // Output: 3
return 0;
}using System;
public class PartitionArray {
public static int PartitionDisjoint(int[] nums) {
int n = nums.Length;
int[] leftMax = new int[n];
int[] rightMin = new int[n];
leftMax[0] = nums[0];
for (int i = 1; i < n; i++) {
leftMax[i] = Math.Max(nums[i], leftMax[i - 1]);
}
rightMin[n - 1] = nums[n - 1];
for (int i = n - 2; i >= 0; i--) {
rightMin[i] = Math.Min(nums[i], rightMin[i + 1]);
}
for (int i = 0; i < n - 1; i++) {
if (leftMax[i] <= rightMin[i + 1]) {
return i + 1;
}
}
return n;
}
public static void Main() {
int[] nums = { 5, 0, 3, 8, 6 };
Console.WriteLine(PartitionDisjoint(nums)); // Output: 3
}
}The Python solution applies two auxiliary arrays for managing maximum and minimum requirements for partitions, making it simple to compute the correct partition index.
Time Complexity: O(n) for running through the lists.
Space Complexity: O(n), owing to additional arrays used.
Approach 3: Prefix Maximum + Suffix Minimum
To satisfy the requirements of the problem after partitioning into two subarrays, we need to ensure that the "maximum value of the array prefix" is less than or equal to the "minimum value of the array suffix".
Therefore, we can first preprocess the minimum value of the array suffix and record it in the mi array.
Then, we traverse the array from front to back, maintaining the maximum value mx of the array prefix. When we traverse to a certain position, if the maximum value of the array prefix is less than or equal to the minimum value of the array suffix, then the current position is the dividing point of the partition, and we can return it directly.
The time complexity is O(n), and the space complexity is O(n). Where n is the length of the array nums.
func partitionDisjoint(nums []int) int {
n := len(nums)
mi := make([]int, n+1)
mi[n] = nums[n-1]
for i := n - 1; i >= 0; i-- {
mi[i] = min(nums[i], mi[i+1])
}
mx := 0
for i := 1; ; i++ {
v := nums[i-1]
mx = max(mx, v)
if mx <= mi[i] {
return i
}
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Prefix and Suffix Tracking | Time Complexity: O(n) - A single traversal of the array suffices. |
| Two Array Auxiliary Tracking | Time Complexity: O(n) for running through the lists. |
| Prefix Maximum + Suffix Minimum | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two Array Auxiliary Tracking | O(n) | O(n) | When clarity matters and preprocessing with prefix/suffix arrays is acceptable. |
| Prefix and Suffix Tracking (Optimized) | O(n) | O(1) | Best for interviews and production where constant extra memory is preferred. |
Frequently asked questions
Is Partition Array into Disjoint Intervals easy or hard?
LeetCode classifies this problem as Medium difficulty. The main challenge is recognizing the condition max(left) ≤ min(right) and translating it into prefix/suffix tracking or a constant-space greedy scan.
Partition Array into Disjoint Intervals Python/Java solution
Both Python and Java implementations follow the same logic. Either compute prefixMax and suffixMin arrays and find the first valid split, or implement the optimized single-pass scan with two variables tracking the left partition maximum and the global maximum.
How to solve Partition Array into Disjoint Intervals in O(n)?
Track two values while iterating: the maximum of the left partition and the maximum value seen globally. If the current element is smaller than the left maximum, extend the partition boundary to the current index and update the left maximum using the global maximum. This ensures the left side always satisfies max(left) ≤ min(right).
What is the best approach for Partition Array into Disjoint Intervals?
The optimal approach is a single-pass prefix tracking method with O(n) time and O(1) space. Maintain the maximum value in the current left partition and the global maximum seen so far. If a smaller element appears, extend the partition boundary and update the left maximum. This avoids building auxiliary arrays while still scanning the array only once.
Is Partition Array into Disjoint Intervals asked at Google/Amazon/Meta?
Partition-based array problems are common in interviews at large tech companies such as Amazon, Google, and Meta. This problem specifically tests reasoning about prefix maximums, suffix minimums, and greedy partition logic using linear scans.
What data structure is used in Partition Array into Disjoint Intervals?
The problem primarily uses arrays and simple scalar variables. One approach builds prefix maximum and suffix minimum arrays, while the optimized solution tracks values during a single pass without extra data structures.
What is the time complexity of Partition Array into Disjoint Intervals?
The optimal solution runs in O(n) time because the array is scanned once while maintaining a few running values. A simpler version using prefix maximum and suffix minimum arrays also runs in O(n) time but requires O(n) additional space for the helper arrays.