> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/strings-arrays-and-2-pointers/partition-array-into-disjoint-intervals.md).

# Partition Array into Disjoint Intervals

Given an array `A`, 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.  It is guaranteed that such a partitioning exists.

**Example 1:**

```
Input: [5,0,3,8,6]
Output: 3
Explanation: left = [5,0,3], right = [8,6]
```

**Example 2:**

```
Input: [1,1,1,0,6,12]
Output: 4
Explanation: left = [1,1,1,0], right = [6,12]
```

**Note:**

1. `2 <= A.length <= 30000`
2. `0 <= A[i] <= 10^6`
3. It is guaranteed there is at least one way to partition `A` as described.

```java
// We can easily do in O(N) space with leftMax & rightMin Arrays
class Solution {
    // https://drive.google.com/file/d/1_5oQ8U-yjScAZprd8W_sgjGK84MjZDRE/view?usp=sharing
    // O(1) space solution
    public int partitionDisjoint(int[] A) {
        // partition variables
        int currentMax = A[0], index = 0;
        // Overall variables
        int max = A[0];
        for (int i = 1; i < A.length; i++) {
            max = Math.max(max, A[i]);
            // If the current element does not violates our partition
            if (A[i] >= currentMax)
                continue;
            // Else we need to increase our partition upto this point
            else {
                currentMax = max;
                index = i;
            }
        }
        return index + 1;
    }
}
```