Welcome to Subscribe On Youtube

456. 132 Pattern

Description

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

• Java
• C++
• Python
• Go
• TypeScript
• RenderScript

• class Solution {
      public boolean find132pattern(int[] nums) {
          int vk = -(1 << 30);
          Deque<Integer> stk = new ArrayDeque<>();
          for (int i = nums.length - 1; i >= 0; --i) {
              if (nums[i] < vk) {
                  return true;
              }
              while (!stk.isEmpty() && stk.peek() < nums[i]) {
                  vk = stk.pop();
              }
              stk.push(nums[i]);
          }
          return false;
      }
  }
  

• class Solution {
  public:
      bool find132pattern(vector<int>& nums) {
          int vk = INT_MIN;
          stack<int> stk;
          for (int i = nums.size() - 1; ~i; --i) {
              if (nums[i] < vk) {
                  return true;
              }
              while (!stk.empty() && stk.top() < nums[i]) {
                  vk = stk.top();
                  stk.pop();
              }
              stk.push(nums[i]);
          }
          return false;
      }
  };
  

• class Solution:
      def find132pattern(self, nums: List[int]) -> bool:
          vk = -inf
          stk = []
          for x in nums[::-1]:
              if x < vk:
                  return True
              while stk and stk[-1] < x:
                  vk = stk.pop()
              stk.append(x)
          return False
  
  

• func find132pattern(nums []int) bool {
  	vk := -(1 << 30)
  	stk := []int{}
  	for i := len(nums) - 1; i >= 0; i-- {
  		if nums[i] < vk {
  			return true
  		}
  		for len(stk) > 0 && stk[len(stk)-1] < nums[i] {
  			vk = stk[len(stk)-1]
  			stk = stk[:len(stk)-1]
  		}
  		stk = append(stk, nums[i])
  	}
  	return false
  }
  

• function find132pattern(nums: number[]): boolean {
      let vk = -Infinity;
      const stk: number[] = [];
      for (let i = nums.length - 1; i >= 0; --i) {
          if (nums[i] < vk) {
              return true;
          }
          while (stk.length && stk[stk.length - 1] < nums[i]) {
              vk = stk.pop()!;
          }
          stk.push(nums[i]);
      }
      return false;
  }
  
  

• impl Solution {
      pub fn find132pattern(nums: Vec<i32>) -> bool {
          let n = nums.len();
          let mut vk = i32::MIN;
          let mut stk = vec![];
          for i in (0..n).rev() {
              if nums[i] < vk {
                  return true;
              }
              while !stk.is_empty() && stk.last().unwrap() < &nums[i] {
                  vk = stk.pop().unwrap();
              }
              stk.push(nums[i]);
          }
          false
      }
  }
  
  

All Problems

All Solutions