LeetCode 915: Partition Array into Disjoint Intervals

Problem Restatement

We are given an integer array nums.

We need to split it into two contiguous non-empty parts:

left = nums[0:i]
right = nums[i:]

The split must satisfy:

max(left) <= min(right)

In words, every element in left must be less than or equal to every element in right.

Return the smallest possible length of left.

The problem guarantees that a valid partition exists.

Input and Output

Function shape:

def partitionDisjoint(nums: list[int]) -> int:
    ...

Examples

Example 1:

nums = [5, 0, 3, 8, 6]

A valid split is:

left = [5, 0, 3]
right = [8, 6]

The maximum value in left is:

5

The minimum value in right is:

6

Since:

5 <= 6

the split is valid.

Answer:

3

Example 2:

nums = [1, 1, 1, 0, 6, 12]

A valid split is:

left = [1, 1, 1, 0]
right = [6, 12]

Answer:

4

First Thought: Check Every Split

A direct approach is to try every possible split.

For each split point, compute:

max(left)
min(right)

If max(left) <= min(right), return the left length.

class Solution:
    def partitionDisjoint(self, nums: list[int]) -> int:
        n = len(nums)

        for split in range(1, n):
            left_max = max(nums[:split])
            right_min = min(nums[split:])

            if left_max <= right_min:
                return split

        return -1

This is correct, but slow.

Each split recomputes maximum and minimum values from scratch.

Problem With Brute Force

There are n - 1 possible split points.

For each split, computing max(left) and min(right) can take O(n) time.

So the total time can become:

O(n^2)

We need to reuse information between split points.

Key Insight

A split after index i is valid when:

max(nums[0:i + 1]) <= min(nums[i + 1:n])

So we can precompute:

Then each split can be checked in constant time.

For split after index i:

prefix_max[i] <= suffix_min[i + 1]

The first valid split gives the smallest possible left length.

Algorithm

1. Let n = len(nums).
2. Build suffix_min, where suffix_min[i] is the minimum value from i to the end.
3. Scan from left to right while maintaining left_max.
4. For each split after index i, check:

left_max <= suffix_min[i + 1]

5. Return i + 1 for the first valid split.

Correctness

For any split after index i, the left part is:

nums[0:i + 1]

and the right part is:

nums[i + 1:n]

The split is valid exactly when the maximum value in the left part is less than or equal to the minimum value in the right part.

The algorithm maintains left_max as the maximum value in nums[0:i + 1].

The precomputed suffix_min[i + 1] is the minimum value in nums[i + 1:n].

Therefore, the condition:

left_max <= suffix_min[i + 1]

is exactly the required partition condition.

The algorithm scans split points from left to right and returns the first valid one.

So the returned length is the smallest possible length of left.

Complexity

Implementation

class Solution:
    def partitionDisjoint(self, nums: list[int]) -> int:
        n = len(nums)

        suffix_min = [0] * n
        suffix_min[-1] = nums[-1]

        for i in range(n - 2, -1, -1):
            suffix_min[i] = min(nums[i], suffix_min[i + 1])

        left_max = nums[0]

        for i in range(n - 1):
            left_max = max(left_max, nums[i])

            if left_max <= suffix_min[i + 1]:
                return i + 1

        return n

Code Explanation

Create the suffix minimum array:

suffix_min = [0] * n
suffix_min[-1] = nums[-1]

Build it from right to left:

for i in range(n - 2, -1, -1):
    suffix_min[i] = min(nums[i], suffix_min[i + 1])

Now suffix_min[i] stores the smallest value from index i to the end.

Track the maximum value on the left side:

left_max = nums[0]

Try every split after index i:

for i in range(n - 1):

Update the maximum of the left side:

left_max = max(left_max, nums[i])

Check whether every left value is less than or equal to every right value:

if left_max <= suffix_min[i + 1]:
    return i + 1

The returned value is the length of left.

Testing

def run_tests():
    s = Solution()

    assert s.partitionDisjoint([5, 0, 3, 8, 6]) == 3
    assert s.partitionDisjoint([1, 1, 1, 0, 6, 12]) == 4
    assert s.partitionDisjoint([1, 2]) == 1
    assert s.partitionDisjoint([1, 1, 1]) == 1
    assert s.partitionDisjoint([3, 1, 2, 4]) == 3
    assert s.partitionDisjoint([2, 3, 1, 5, 6]) == 3

    print("all tests passed")

run_tests()

Test meaning: