# Partition Array into Disjoint Intervals
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/partition-array-into-disjoint-intervals)
Canonical: https://scaleengineer.com/dsa/problems/partition-array-into-disjoint-intervals
**Data structures:** Array
---
## Problem
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.

# Approaches
## Brute Force Iteration
This approach involves checking every possible way to partition the array into two non-empty contiguous subarrays. For each potential partition, we explicitly calculate the maximum of the `left` part and the minimum of the `right` part and see if the condition holds. Since we need the smallest `left` partition, we check the partitions in increasing order of their size.
**Time:** O(N^2), where N is the length of `nums`. The outer loop runs N-1 times. Inside, we have two loops that in total scan the entire array, taking O(N) time for each outer loop iteration. · **Space:** O(1), as we only use a few variables to store the max and min values, not dependent on the input size.
**Pros:** Simple to understand and implement.; Correct for small inputs.
**Cons:** Highly inefficient due to nested loops.; Will likely result in a 'Time Limit Exceeded' (TLE) error on platforms like LeetCode for larger inputs as per the constraints.
### Explanation
We can iterate through all possible lengths of the `left` subarray, from 1 to `n-1`. Let the partition be after index `i`. The `left` subarray is `nums[0...i]` and the `right` is `nums[i+1...n-1]`. For each `i`, we find `max_left`, the maximum element in `left`, and `min_right`, the minimum element in `right`. If `max_left <= min_right`, we have found a valid partition. Since we are iterating `i` from `0` upwards, the first valid partition we find will correspond to the smallest possible `left` subarray. We can then return its length, which is `i+1`.

```java
class Solution {
    public int partitionDisjoint(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n - 1; i++) {
            int maxLeft = 0;
            for (int j = 0; j <= i; j++) {
                maxLeft = Math.max(maxLeft, nums[j]);
            }

            int minRight = 1000001; // Constraints: 0 <= nums[i] <= 10^6
            for (int k = i + 1; k < n; k++) {
                minRight = Math.min(minRight, nums[k]);
            }

            if (maxLeft <= minRight) {
                return i + 1;
            }
        }
        return -1; // Should not be reached as a solution is guaranteed
    }
}
```
### Algorithm
- Iterate through all possible partition points `i` from `0` to `n-2`, where `n` is the length of the array.
- For each `i`, the `left` subarray is `nums[0...i]` and the `right` subarray is `nums[i+1...n-1]`.
- In an inner loop, find the maximum element `max_left` in the `left` subarray.
- In another inner loop, find the minimum element `min_right` in the `right` subarray.
- Check if the condition `max_left <= min_right` is satisfied.
- If it is, we have found the smallest possible `left` partition because we are iterating `i` from the smallest possible value. Return the length `i + 1` immediately.

## Two-Pass with Auxiliary Arrays
This approach improves upon the brute-force method by pre-calculating the necessary maximums and minimums to avoid redundant computations. We use two auxiliary arrays: one to store the running maximum from the left and another to store the running minimum from the right. This allows us to check the partition condition for any split point in constant time.
**Time:** O(N). We make three separate passes through the array (one for `maxLeft`, one for `minRight`, and one for the final check), each taking O(N) time. This simplifies to O(N). · **Space:** O(N), as we use two auxiliary arrays, `maxLeft` and `minRight`, each of size N.
**Pros:** Significantly more efficient than the brute-force approach with linear time complexity.; Guaranteed to pass within the time limits for the given constraints.
**Cons:** Uses extra space proportional to the input size, which might be a concern for very large arrays in a memory-constrained environment.
### Explanation
The core condition is `max(nums[0...i]) <= min(nums[i+1...N-1])`. Instead of recalculating these values in each iteration, we can precompute them.
1. Create an array `maxLeft` where `maxLeft[i]` stores the maximum value in the subarray `nums[0...i]`. This can be computed in a single pass from left to right.
2. Create an array `minRight` where `minRight[i]` stores the minimum value in the subarray `nums[i...N-1]`. This can be computed in a single pass from right to left.
3. With these arrays, we can check the condition for each `i` in O(1) time. We iterate from `i = 0` to `N-2` and check if `maxLeft[i] <= minRight[i+1]`. The first `i` that satisfies this gives the smallest `left` partition of length `i+1`.

```java
class Solution {
    public int partitionDisjoint(int[] nums) {
        int n = nums.length;
        int[] maxLeft = new int[n];
        maxLeft[0] = nums[0];
        for (int i = 1; i < n; i++) {
            maxLeft[i] = Math.max(maxLeft[i - 1], nums[i]);
        }

        int[] minRight = new int[n];
        minRight[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            minRight[i] = Math.min(minRight[i + 1], nums[i]);
        }

        for (int i = 0; i < n - 1; i++) {
            if (maxLeft[i] <= minRight[i + 1]) {
                return i + 1;
            }
        }
        return -1; // Should not be reached
    }
}
```
### Algorithm
- Create an integer array `maxLeft` of size `N`.
- Traverse `nums` from left to right to populate `maxLeft`, where `maxLeft[i]` will store the maximum value in `nums[0...i]`.
- Create another integer array `minRight` of size `N`.
- Traverse `nums` from right to left to populate `minRight`, where `minRight[i]` will store the minimum value in `nums[i...N-1]`.
- Finally, iterate from `i = 0` to `N-2`.
- For each `i`, check if `maxLeft[i] <= minRight[i+1]`. This is the partition condition `max(left) <= min(right)`.
- The first index `i` that satisfies this condition gives the smallest `left` partition. Return `i + 1`.

## One-Pass Greedy Approach
This is the most optimal approach, solving the problem in a single pass with constant extra space. The idea is to iterate through the array, maintaining a candidate `left` partition. We greedily extend this `left` partition whenever we encounter an element that violates the partition condition, ensuring that by the end, we have found the smallest possible valid partition.
**Time:** O(N), as we iterate through the array only once. · **Space:** O(1), as we only use a few constant extra variables regardless of the input size.
**Pros:** Optimal solution with O(N) time complexity.; Extremely space-efficient with O(1) space complexity.; Solves the problem in a single pass over the data.
**Cons:** The logic can be less intuitive to come up with compared to the more straightforward brute-force or two-pass methods.
### Explanation
We can solve this problem by iterating through the array just once. We maintain three variables:
- `partitionIdx`: The index where the current `left` partition ends.
- `leftMax`: The maximum value in the current `left` partition (`nums[0...partitionIdx]`).
- `currentMax`: The maximum value encountered so far as we iterate through the array (`nums[0...i]`).

We initialize `partitionIdx = 0`, `leftMax = nums[0]`, and `currentMax = nums[0]`. Then, we iterate from `i = 1` to `N-1`. In each step, we update `currentMax`. The key idea is that if we find an element `nums[i]` that is smaller than `leftMax`, it means our current partition is invalid. This `nums[i]` must belong to the `left` partition, otherwise, the condition `max(left) <= min(right)` would be violated (`min(right) <= nums[i] < leftMax`). Therefore, we must extend the `left` partition to include this element. We update `partitionIdx` to `i`. When we extend the partition, the new `leftMax` must be the maximum of all elements in the new `left` partition, which is `currentMax`. After iterating through the entire array, `partitionIdx + 1` gives the length of the smallest valid `left` partition.

```java
class Solution {
    public int partitionDisjoint(int[] nums) {
        int partitionIdx = 0;
        int leftMax = nums[0];
        int currentMax = nums[0];
        
        for (int i = 1; i < nums.length; i++) {
            currentMax = Math.max(currentMax, nums[i]);
            if (nums[i] < leftMax) {
                // This element must be in the left partition.
                // The partition must extend to at least this index.
                partitionIdx = i;
                // The new max for the left partition is the max
                // of all elements seen so far.
                leftMax = currentMax;
            }
        }
        
        return partitionIdx + 1;
    }
}
```
### Algorithm
- Initialize three variables: `partitionIdx = 0`, `leftMax = nums[0]`, and `currentMax = nums[0]`.
- `partitionIdx` will store the end index of our candidate `left` partition.
- `leftMax` will store the maximum value within the candidate `left` partition (`nums[0...partitionIdx]`)
- `currentMax` will track the maximum value seen so far as we iterate through the array.
- Iterate through the array from the second element (`i = 1` to `n-1`).
- In each iteration, update `currentMax = max(currentMax, nums[i])`.
- Check if the current element `nums[i]` is less than `leftMax`.
- If `nums[i] < leftMax`, it means our current partition is invalid because `nums[i]` must belong to the `left` part. To fix this, we must extend the `left` partition to include `nums[i]`. We do this by updating `partitionIdx = i` and also updating `leftMax` to `currentMax`, since the new `left` partition's maximum is now the maximum of all elements seen so far.
- After the loop finishes, `partitionIdx` holds the correct end index for the smallest `left` partition. Return `partitionIdx + 1`.

# Solutions
### Java

```java
class Solution {
public
  int partitionDisjoint(int[] nums) {
    int n = nums.length;
    int[] mi = new int[n + 1];
    mi[n] = nums[n - 1];
    for (int i = n - 1; i >= 0; --i) {
      mi[i] = Math.min(nums[i], mi[i + 1]);
    }
    int mx = 0;
    for (int i = 1; i <= n; ++i) {
      int v = nums[i - 1];
      mx = Math.max(mx, v);
      if (mx <= mi[i]) {
        return i;
      }
    }
    return 0;
  }
}

```

### Python

```python
class Solution:
    def partitionDisjoint(self, nums: List[int]) -> int: n = len(nums) mi = [inf] * (n + 1) for i in range(n - 1, - 1, - 1): mi[i] = min(nums[i], mi[i + 1]) mx = 0 for i, v in enumerate(nums, 1): mx = max(mx, v) if mx <= mi[i]: return i

```

### CPP

```cpp
class Solution {
public:
  int partitionDisjoint(vector<int> &nums) {
    int n = nums.size();
    vector<int> mi(n + 1, INT_MAX);
    for (int i = n - 1; ~i; --i)
      mi[i] = min(nums[i], mi[i + 1]);
    int mx = 0;
    for (int i = 1; i <= n; ++i) {
      int v = nums[i - 1];
      mx = max(mx, v);
      if (mx <= mi[i])
        return i;
    }
    return 0;
  }
};

```