LeetCode 915 - Partition Array into Disjoint Intervals

The problem asks us to split an array into two contiguous parts, left and right, such that every value in left is less than or equal to every value in right. Among all valid partitions, we must return the smallest possible size of left.

leetcodemediumarray

LeetCode Problem 915

Difficulty: 🟡 Medium
Topics: Array

Solution

Problem Understanding

The problem asks us to split an array into two contiguous parts, left and right, such that every value in left is less than or equal to every value in right. Among all valid partitions, we must return the smallest possible size of left.

A contiguous partition means we choose a single index and split the array there. For example, if the partition point is at index k, then:

  • left = nums[0:k+1]
  • right = nums[k+1:]

Both subarrays must contain at least one element, so the split point cannot be at the very beginning or the very end.

The key condition is:

max(left) <= min(right)

The output is not the subarray itself, but the length of the left partition.

The constraints are important:

  • The array can contain up to 10^5 elements.
  • Values can be as large as 10^6.

These constraints immediately suggest that quadratic solutions will likely time out. An O(n^2) algorithm would perform up to 10^10 operations in the worst case, which is far too slow. We need a linear or near-linear solution.

Several edge cases are important:

  • Arrays with many duplicate values, where equality must still satisfy the condition.
  • Arrays where the valid partition occurs very late.
  • Arrays where the first valid partition is also the optimal one.
  • Arrays containing decreasing segments that force the left partition to expand.
  • Cases where the smallest element appears in the middle of the array.

The problem guarantees that at least one valid partition always exists, which simplifies the implementation because we do not need to handle failure cases.

Approaches

Brute Force Approach

A straightforward solution is to try every possible partition point.

For each split index i, we compute:

  • The maximum value in nums[0:i+1]
  • The minimum value in nums[i+1:]

If:

max(left) <= min(right)

then the partition is valid, and since we check from left to right, the first valid partition is the smallest possible one.

This approach is correct because it explicitly verifies the exact condition required by the problem. However, repeatedly scanning subarrays is expensive.

For every partition index, computing a maximum and minimum requires O(n) work, and there are O(n) possible partitions. This leads to O(n^2) time complexity.

With n = 100000, this approach is too slow.

Optimal Approach

The important observation is that the partition condition depends only on:

  • The maximum value seen on the left side
  • The minimum value remaining on the right side

Instead of recomputing these values repeatedly, we can preprocess them.

We build a suffix minimum array where:

suffix_min[i] = minimum value from nums[i] to nums[n-1]

Then, while scanning from left to right, we maintain:

left_max = maximum value in nums[0:i]

At each position i, we check:

left_max <= suffix_min[i + 1]

If true, then every element in the left partition is less than or equal to every element in the right partition.

Because we scan from left to right, the first valid split automatically gives the smallest possible left partition.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Recomputes max and min for every partition
Optimal O(n) O(n) Uses suffix minimum preprocessing

Algorithm Walkthrough

  1. Create a suffix minimum array called suffix_min.

The purpose of this array is to quickly answer the question:

What is the minimum value to the right of index i?

We initialize:

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

Then fill the array backward:

suffix_min[i] = min(nums[i], suffix_min[i + 1])

After preprocessing, suffix_min[i] stores the minimum element from index i to the end. 2. Initialize left_max.

This variable tracks the maximum value in the current left partition.

Initially:

left_max = nums[0]
  1. Scan the array from left to right.

For each possible partition ending at index i:

  • Update the maximum value in the left partition.
  • Compare it with the minimum value in the right partition.

Specifically:

left_max = max(left_max, nums[i])

Then check:

left_max <= suffix_min[i + 1]
  1. Return the first valid partition size.

If the condition is true, then:

  • Every value in left is less than or equal to every value in right.
  • Since we scan left to right, this is the smallest valid left partition.

Therefore, return:

i + 1

Why it works

The algorithm maintains two critical properties:

  • left_max is the maximum value in the proposed left partition.
  • suffix_min[i + 1] is the minimum value in the proposed right partition.

If:

left_max <= suffix_min[i + 1]

then every element in the left partition is guaranteed to be less than or equal to every element in the right partition.

Because the scan proceeds from left to right, the first valid split necessarily produces the smallest possible left partition.

Python Solution

from typing import List

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

        suffix_min = [0] * n
        suffix_min[n - 1] = nums[n - 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

The implementation starts by constructing the suffix_min array. Each position stores the minimum value from that index to the end of the array. This preprocessing allows constant-time access to the smallest value in the future right partition.

Next, the algorithm scans from left to right while maintaining left_max, which represents the largest value encountered so far in the left partition.

At each position, the algorithm checks whether the largest value on the left is less than or equal to the smallest value on the right. If this condition holds, the current partition is valid, and because the scan proceeds in increasing order, it is also the smallest valid partition.

The final return n statement is technically unnecessary because the problem guarantees a valid answer exists, but it keeps the function structurally complete.

Go Solution

func partitionDisjoint(nums []int) int {
    n := len(nums)

    suffixMin := make([]int, n)
    suffixMin[n-1] = nums[n-1]

    for i := n - 2; i >= 0; i-- {
        if nums[i] < suffixMin[i+1] {
            suffixMin[i] = nums[i]
        } else {
            suffixMin[i] = suffixMin[i+1]
        }
    }

    leftMax := nums[0]

    for i := 0; i < n-1; i++ {
        if nums[i] > leftMax {
            leftMax = nums[i]
        }

        if leftMax <= suffixMin[i+1] {
            return i + 1
        }
    }

    return n
}

The Go implementation follows the same algorithmic structure as the Python solution. Since Go does not provide built-in min and max functions for integers, explicit comparisons are used instead.

Slices are used for the suffix minimum array, and integer overflow is not a concern because the constraints are well within Go's integer range.

The function assumes the input array is non-empty, which is guaranteed by the problem constraints.

Worked Examples

Example 1

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

First compute the suffix minimum array.

Index nums[i] suffix_min[i]
4 6 6
3 8 6
2 3 3
1 0 0
0 5 0

So:

suffix_min = [0,0,3,6,6]

Now scan from left to right.

i nums[i] left_max suffix_min[i+1] Valid?
0 5 5 0 No
1 0 5 3 No
2 3 5 6 Yes

At i = 2:

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

Result:

3

Example 2

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

Compute suffix minimums.

Index nums[i] suffix_min[i]
5 12 12
4 6 6
3 0 0
2 1 0
1 1 0
0 1 0

So:

suffix_min = [0,0,0,0,6,12]

Now scan.

i nums[i] left_max suffix_min[i+1] Valid?
0 1 1 0 No
1 1 1 0 No
2 1 1 0 No
3 0 1 6 Yes

At i = 3:

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

Result:

4

Complexity Analysis

Measure Complexity Explanation
Time O(n) One pass to build suffix minimums and one pass to find the partition
Space O(n) The suffix minimum array stores one value per element

The algorithm performs two linear scans of the array. Each operation inside the loops is constant time, so the total runtime is linear.

The additional memory usage comes from the suffix minimum array, which stores n integers.

Test Cases

from typing import List

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

        suffix_min = [0] * n
        suffix_min[n - 1] = nums[n - 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

sol = Solution()

assert sol.partitionDisjoint([5, 0, 3, 8, 6]) == 3  # provided example 1
assert sol.partitionDisjoint([1, 1, 1, 0, 6, 12]) == 4  # provided example 2

assert sol.partitionDisjoint([1, 2]) == 1  # smallest valid array
assert sol.partitionDisjoint([1, 1]) == 1  # equal elements

assert sol.partitionDisjoint([1, 2, 3, 4, 5]) == 1  # already sorted increasing
assert sol.partitionDisjoint([5, 4, 3, 2, 6]) == 4  # partition forced late

assert sol.partitionDisjoint([1, 0, 2, 3, 4]) == 2  # small inversion near front
assert sol.partitionDisjoint([2, 2, 2, 2]) == 1  # all equal values

assert sol.partitionDisjoint([3, 1, 2, 4, 5]) == 3  # left must absorb disorder
assert sol.partitionDisjoint([0, 0, 0, 1]) == 1  # many duplicates before larger value
Test Why
[5,0,3,8,6] Validates standard partition behavior
[1,1,1,0,6,12] Tests duplicates and delayed partition
[1,2] Smallest possible input size
[1,1] Ensures equality is handled correctly
[1,2,3,4,5] Already sorted increasing array
[5,4,3,2,6] Forces partition near the end
[1,0,2,3,4] Tests early inversion handling
[2,2,2,2] All elements identical
[3,1,2,4,5] Left partition must expand to include disorder
[0,0,0,1] Duplicate minimum values

Edge Cases

One important edge case is when all values are equal. For example:

[2,2,2,2]

A common mistake is using a strict inequality instead of allowing equality. The problem requires:

left <= right

not strictly less than. The implementation correctly uses:

left_max <= suffix_min[i + 1]

so equal values are handled properly.

Another important edge case occurs when the partition must extend very far into the array. Consider:

[5,4,3,2,6]

A naive implementation might incorrectly partition too early if it only compares local neighbors instead of global maximums and minimums. The algorithm avoids this by maintaining the maximum value of the entire left partition and comparing it against the minimum value of the entire remaining right partition.

A third important case is when a very small value appears after several larger values:

[1,1,1,0,6,12]

The 0 forces the left partition to expand because every element in the left partition must remain less than or equal to every element in the right partition. The algorithm correctly handles this because left_max preserves the largest value seen so far, even after encountering smaller values later.

A final edge case is the smallest allowed input size:

[1,2]

Since both partitions must be non-empty, there is only one possible split. The implementation naturally handles this because the loop only checks valid partition boundaries before the last element.