# 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:

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

The split must satisfy:

```python
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

| Item | Meaning |
|---|---|
| Input | Integer array `nums` |
| Output | Smallest valid length of `left` |
| Partition rule | `left` and `right` are contiguous |
| Non-empty rule | Both parts must contain at least one element |
| Validity rule | Every value in `left` is `<=` every value in `right` |

Function shape:

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

## Examples

Example 1:

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

A valid split is:

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

The maximum value in `left` is:

```python
5
```

The minimum value in `right` is:

```python
6
```

Since:

```python
5 <= 6
```

the split is valid.

Answer:

```python
3
```

Example 2:

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

A valid split is:

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

Answer:

```python
4
```

## First Thought: Check Every Split

A direct approach is to try every possible split.

For each split point, compute:

```python
max(left)
min(right)
```

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

```python
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:

```python
O(n^2)
```

We need to reuse information between split points.

## Key Insight

A split after index `i` is valid when:

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

So we can precompute:

| Array | Meaning |
|---|---|
| `prefix_max[i]` | Maximum value from `nums[0]` through `nums[i]` |
| `suffix_min[i]` | Minimum value from `nums[i]` through `nums[n - 1]` |

Then each split can be checked in constant time.

For split after index `i`:

```python
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:

```python
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:

```python
nums[0:i + 1]
```

and the right part is:

```python
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:

```python
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

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | One pass builds suffix minimums and one pass finds the split |
| Space | `O(n)` | The suffix minimum array stores one value per index |

## Implementation

```python
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:

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

Build it from right to left:

```python
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:

```python
left_max = nums[0]
```

Try every split after index `i`:

```python
for i in range(n - 1):
```

Update the maximum of the left side:

```python
left_max = max(left_max, nums[i])
```

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

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

The returned value is the length of `left`.

## Testing

```python
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:

| Test | Why |
|---|---|
| `[5, 0, 3, 8, 6]` | Main example |
| `[1, 1, 1, 0, 6, 12]` | Left must include a later small value |
| `[1, 2]` | Smallest valid size |
| `[1, 1, 1]` | Equal values are allowed |
| `[3, 1, 2, 4]` | Split near the end |
| `[2, 3, 1, 5, 6]` | Prefix maximum blocks early splits |