Skip to main content
Talentd

Partition Array into Disjoint Intervals - Solution & Explanation

MediumArray16 min readAsked at: Microsoft, Google
Practice this problem

Problem Statement

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.

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.

The C solution uses two variables, maxLeft and maxSoFar, to track the maximum values during the iteration through the array. Whenever we encounter an element smaller than maxLeft, it updates the partition index to that position and sets maxLeft to maxSoFar. This ensures all conditions of the partition are maintained.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) - Linear scan of the array.
Space Complexity: O(1) - Only variables used for tracking, no extra storage required.

Try this approach in the editor →

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.

In this C solution, two arrays leftMax and rightMin are used to keep track of the maximum values up to an index and the minimum values from an index onward. By comparing elements from leftMax and rightMin, we determine the appropriate partition point.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) - Needs three linear passes through the array.
Space Complexity: O(n) - Additional space for two auxiliary arrays.

Try this approach in the editor →

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.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Prefix and Suffix Tracking

Time Complexity: O(n) - Linear scan of the array.
Space Complexity: O(1) - Only variables used for tracking, no extra storage required.

Two Array Auxiliary Tracking

Time Complexity: O(n) - Needs three linear passes through the array.
Space Complexity: O(n) - Additional space for two auxiliary arrays.

Prefix Maximum + Suffix Minimum—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Two Array Auxiliary TrackingO(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.

Video Solution

Partition Array Into Disjoint Intervals in O(n) Space | Leetcode 915 | Solution in Hindi • Pepcoding • 7,267 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Partition Array into Disjoint Intervals with our built-in code editor and test cases.

Practice on FleetCode
Previous

Maximum Strength of K Disjoint Subarrays

Next

Minimum Index of a Valid Split