## 915. 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.

## Rust Solution

``````struct Solution;

impl Solution {
fn partition_disjoint(a: Vec<i32>) -> i32 {
let n = a.len();
let mut left = vec![0; n];
let mut right = vec![0; n];
let mut min = std::i32::MAX;
let mut max = std::i32::MIN;
for i in (0..n).rev() {
min = min.min(a[i]);
right[i] = min;
}

for i in 0..n {
max = max.max(a[i]);
left[i] = max;
}
for i in 1..n {
if right[i] >= left[i - 1] {
return i as i32;
}
}
0
}
}

#[test]
fn test() {
let a = vec![5, 0, 3, 8, 6];
let res = 3;
assert_eq!(Solution::partition_disjoint(a), res);
let a = vec![1, 1, 1, 0, 6, 12];
let res = 4;
assert_eq!(Solution::partition_disjoint(a), res);
}
``````

Having problems with this solution? Click here to submit an issue on github.