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

  • 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