Partition Array into Disjoint Intervals: Finding the Split Point

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, and left has the smallest possible size. Return the length of left.

This is LeetCode 915: Partition Array into Disjoint Intervals, a medium problem that asks you to find the earliest split point in an array where two halves do not overlap in value. The trick is recognizing that the split condition depends on only two quantities: the maximum of the left side and the minimum of the right side.

The problem

You are looking for the smallest index i such that max(nums[0..i]) is less than or equal to min(nums[i+1..n-1]). The left partition is nums[0..i] and its length is i + 1.

The brute force approach

The most direct solution is to try every possible split point. For each candidate index i, compute the max of the left part and the min of the right part, then check if max(left) is at most min(right).

def partition_disjoint_brute(nums):
    n = len(nums)
    for i in range(1, n):
        left_max = max(nums[:i])
        right_min = min(nums[i:])
        if left_max <= right_min:
            return i
    return -1

This runs in O(n^2) time because for each of the n - 1 split candidates, you recompute the max and min from scratch. On large inputs (up to 3 * 10^4 elements), this can be too slow. The problem is that you are recalculating work you have already done at the previous split point.

The key insight

The prefix max array maxLeft[i] stores the maximum of nums[0..i]. The suffix min array minRight[i] stores the minimum of nums[i..n-1]. The valid partition point is the smallest i where maxLeft[i] is at most minRight[i + 1]. This works because maxLeft[i] captures the largest value in the left partition, and minRight[i + 1] captures the smallest value in the right partition.

Step-by-step walkthrough

The code

def partition_disjoint(nums):
    n = len(nums)
    max_left = [0] * n
    min_right = [0] * n

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

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

    for i in range(n - 1):
        if max_left[i] <= min_right[i + 1]:
            return i + 1

    return n

Here is what each piece does:

1. Build max_left by scanning left to right. At each index, take the max of the previous prefix max and the current element. After this pass, max_left[i] is the largest value in nums[0..i].
2. Build min_right by scanning right to left. At each index, take the min of the next suffix min and the current element. After this pass, min_right[i] is the smallest value in nums[i..n-1].
3. Find the split by scanning left to right. The first index i where max_left[i] is at most min_right[i + 1] is the answer. Return i + 1 because the problem asks for the length of the left partition, not the index.

Complexity analysis

You need to look at every element at least once, so O(n) time is optimal. The two auxiliary arrays cost O(n) space, which is acceptable for the problem constraints.

The building blocks

This problem is built on two reusable patterns that CodeBricks drills independently.

1. Prefix max / suffix min arrays

The pattern of precomputing a running aggregate from one direction so that range queries become O(1):

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

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

In this problem, the prefix max tells you the worst-case value in the left partition, and the suffix min tells you the best-case value in the right partition. In Trapping Rain Water, prefix max and suffix min give you the water level at each position. In Best Time to Buy and Sell Stock, a suffix max tracks the best future selling price. The skeleton is always the same: scan in one direction, carry forward an aggregate.

2. Split-point search

The pattern of scanning for the earliest index where a condition involving left-side and right-side summaries is satisfied:

for i in range(n - 1):
    if left_summary[i] meets_condition right_summary[i + 1]:
        return i + 1

In this problem, the condition is max_left[i] being at most min_right[i + 1]. In Product of Array Except Self, you combine prefix products and suffix products at each index. Any time you need to compare "everything to the left" with "everything to the right," precomputing both sides and scanning for the split is the standard approach.

Edge cases

Before submitting, make sure your solution handles these:

• Already sorted [1, 2, 3, 4]: the split happens at index 0, returning length 1. The first element alone forms a valid left partition.
• Two elements [1, 1]: max_left[0] = 1, min_right[1] = 1. Since 1 is at most 1, return 1.
• Descending then ascending [5, 0, 3, 8, 6]: the partition must include enough elements from the left so the max does not exceed the right's min. The answer is 3.
• All equal [3, 3, 3]: every split point works. The algorithm returns 1 (the smallest valid partition).
• Large spike at the start [10, 1, 2, 3, 11]: max_left stays at 10 until index 4. You need min_right[i + 1] to be at least 10, which happens when the right partition starts at index 4. Return 4.

From understanding to recall

You have read through the prefix max and suffix min approach and it makes sense. Two precomputation passes, one comparison scan. But can you write it from scratch in an interview without looking at it?

The details matter: initializing max_left[0] to nums[0] (not 0), building min_right from right to left starting at n - 1, and returning i + 1 instead of i. These are small but easy to get wrong under pressure if you have not practiced them from memory.

Spaced repetition closes that gap. You practice writing the prefix max and suffix min arrays from scratch at increasing intervals. After a few rounds, the pattern is automatic. You see "compare left side vs right side at every split point" and the code flows out without hesitation.

Related posts

• Best Time to Buy and Sell Stock - Uses a prefix min (or suffix max) to track the best price seen so far
• Product of Array Except Self - Combines prefix products and suffix products, the same two-pass precomputation idea
• Maximum Subarray - Kadane's algorithm uses a running aggregate to avoid recomputing subarray sums

CodeBricks breaks the partition array into disjoint intervals problem into its prefix max / suffix min and split-point search building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a two-pass precomputation question shows up in your interview, you do not think about it. You just write it.