lib.rs

pub struct Solution {}

impl Solution {
    /// True if there is a 132 pattern in nums.
    ///
    /// A 132 pattern is a subsequence of three integers nums[i], nums[j] and nums[k]
    /// such that i < j < k and nums[i] < nums[k] < nums[j].
    ///
    pub fn find132pattern(nums: Vec<i32>) -> bool {
        // Loop invariants:
        //
        // -   `min` is the minimum value we've seen so far.
        //
        // -   The pairs in `stack` are exactly the open intervals into which a
        //     subsequent number must fall in order to form the third value of
        //     a 132 pattern, in combination with two values we've already seen.
        //
        // -   The ranges are non-overlapping and sorted in descending order.
        let mut stack: Vec<(i32, i32)> = vec![];
        let mut min = i32::MAX;
        for v in nums {
            if v <= min {
                // v is <= everything on the stack.
                min = v;
            } else {
                while let Some(last) = stack.last() {
                    if last.1 <= v {
                        stack.pop();
                    } else if last.0 < v {
                        return true;
                    } else {
                        break;
                    }
                }
                stack.push((min, v));
            }
        }
        false
    }
}

#[cfg(test)]
mod tests {
    use crate::Solution;

    #[track_caller]
    fn test_case(nums: &[i32], expected: bool) {
        assert_eq!(Solution::find132pattern(nums.to_owned()), expected);
    }
    
    #[test]
    fn test_examples() {
        test_case(&[1, 2, 3, 4], false);
        test_case(&[3, 1, 4, 2], true);
        test_case(&[-1, 3, 2, 0], true);

        test_case(&[0, 1], false);
        test_case(&[0, 1, -3, 0], false);

        // proptest found this after failing to find any bugs when vector
        // length was 1..=30000; changing to 1..=5 did the trick.
        test_case(&[380816930, 0, 1], false);

        test_case(&[0, 1, 0, 1, 1, 2, 0, 2, 0], false);
        test_case(&[0, 1, 0, 1, 1, 2, 0, 2, 0, 1], true);
    }

    fn reference_implementation(nums: &[i32]) -> bool {
        let n = nums.len();
        for k in 0..n {
            for j in 0..k {
                for i in 0..j {
                    if nums[i] < nums[k] && nums[k] < nums[j] {
                        return true;
                    }
                }
            }
        }
        false
    }

    use proptest::prelude::*;

    proptest! {
        #[test]
        fn test_arbitrary(nums in proptest::collection::vec(-10..=10, 1..=10000)) {
            let expected = reference_implementation(&nums);
            let actual = Solution::find132pattern(nums);
            assert_eq!(actual, expected);
        }
    }
}