## 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.
{"ft_lang_label":"__label__en","ft_lang_prob":0.6228443,"math_prob":0.99911165,"size":1362,"snap":"2021-31-2021-39","text_gpt3_token_len":461,"char_repetition_ratio":0.12371134,"word_repetition_ratio":0.008298756,"special_character_ratio":0.38913363,"punctuation_ratio":0.27683616,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9984011,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-09-28T22:44:44Z\",\"WARC-Record-ID\":\"<urn:uuid:72f5a6fa-1112-41f4-bd7a-f24427cfeb14>\",\"Content-Length\":\"9886\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:65cd9aa4-d278-4fd4-9b4f-ace7e697e674>\",\"WARC-Concurrent-To\":\"<urn:uuid:79679cd8-f59f-44de-8979-caf39083a011>\",\"WARC-IP-Address\":\"35.188.52.69\",\"WARC-Target-URI\":\"https://rustgym.com/leetcode/915\",\"WARC-Payload-Digest\":\"sha1:XSYLCBP3OZ4BXSUEFKSLVJOUM2VWEGPF\",\"WARC-Block-Digest\":\"sha1:NVSGRC4VZTPVUJWDN2YUGMKYEBTDHEWN\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-39/CC-MAIN-2021-39_segments_1631780060908.47_warc_CC-MAIN-20210928214438-20210929004438-00632.warc.gz\"}"}