Skip to content

Files

Latest commit

45a5687 · Jan 17, 2024

History

History

0456-132 Pattern

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
Jan 17, 2024
Jan 17, 2024
Jan 17, 2024

456. 132 Pattern

Given an array of n integers 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].

Return true if there is a 132 pattern in nums, otherwise, return false.

Example 1:

Input: nums = [1,2,3,4]
Output: false
Explanation: There is no 132 pattern in the sequence.

Example 2:

Input: nums = [3,1,4,2]
Output: true
Explanation: There is a 132 pattern in the sequence: [1, 4, 2].

Example 3:

Input: nums = [-1,3,2,0]
Output: true
Explanation: There are three 132 patterns in the sequence: [-1, 3, 2], [-1, 3, 0] and [-1, 2, 0].

Constraints:

  • n == nums.length
  • 1 <= n <= 2 * 105
  • -109 <= nums[i] <= 109

Solutions (Rust)

1. Solution

impl Solution {
    pub fn find132pattern(nums: Vec<i32>) -> bool {
        let mut stack = vec![];
        let mut min_num = i32::MAX;

        for k in 0..nums.len() {
            while let Some(&(numsi, numsj)) = stack.last() {
                if numsi < nums[k] && nums[k] < numsj {
                    return true;
                } else if nums[k] >= numsj {
                    stack.pop();
                } else {
                    break;
                }
            }

            stack.push((min_num, nums[k]));
            min_num = min_num.min(nums[k]);
        }

        false
    }
}