Leetcode 456 - 132 Pattern

Note:

  • For every i, need to find a pair after i that i < k < j.
  • We have to iterate backwards cuz j and k appear after i.
  • What kind of data structure do we need?
    • It should store all 3s (j).
    • All 2s (k) that are smaller than 3s should be popped out.
    • We need to know the max of 2s to make sure 2 > 1.
  • Yes, it’s monotonic stack in non-increasing order.
  • Everytime we pop out a num, compare it with k to keep max.
  • Once k > nums[i], it means there are js in the stack that are bigger than i and k. Return true.

Question:

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
2
3
Input: nums = [3,1,4,2]
Output: true
Explanation: There is a 132 pattern in the sequence: [1, 4, 2].

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
* @param {number[]} nums
* @return {boolean}
*/
var find132pattern = function(nums) {
let stack = [];
let k = Number.MIN_SAFE_INTEGER;
for (let i = nums.length - 1; i >= 0; i--) {
if (k > nums[i]) return true;
// Cannot use `<=` to compare the top of the stack vs nums[i] cuz it's possbile that `k === j` after popping.
while (stack.length > 0 && stack[stack.length - 1] < nums[i]) {
k = Math.max(stack.pop(), k);
}
stack.push(nums[i]);
}
return false;
};