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.