Algorithm


Problem Name: 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

Code Examples

#1 Code Example with Java Programming

Code - Java Programming


class Solution {
  public boolean find132pattern(int[] nums) {
    if (nums.length < 3) {
      return false;
    }
    int[] minTillIndex = new int[nums.length];
    minTillIndex[0] = nums[0];
    for (int idx = 1; idx  <  nums.length; idx++) {
      minTillIndex[idx] = Math.min(minTillIndex[idx - 1], nums[idx]);
    }
    Stack < Integer> stack = new Stack<>();
    for (int idx = nums.length - 1; idx >= 0; idx--) {
      if (nums[idx] > minTillIndex[idx]) {
        while (!stack.isEmpty() && stack.peek()  < = minTillIndex[idx]) {
          stack.pop();
        }
        if (!stack.isEmpty() && stack.peek() < nums[idx]) {
          return true;
        }
        stack.push(nums[idx]);
      }
    }
    return false;
  }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
nums = [1,2,3,4]

Output

x
+
cmd
false

#2 Code Example with Javascript Programming

Code - Javascript Programming


const find132pattern = function(nums) {
  let [stack, s3] = [[], -Infinity]
  for (let i = nums.length - 1; i >= 0; i--) {
    if (nums[i] < s3) {
      return true
    }
    while (stack[stack.length - 1] < nums[i]) {
      s3 = stack.pop()
    }
    stack.push(nums[i])
  }
  return false
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
nums = [1,2,3,4]

Output

x
+
cmd
false

#3 Code Example with Python Programming

Code - Python Programming


class Solution:
    def find132pattern(self, nums):
        stack, s3 = [], -float("inf")
        for n in nums[::-1]:
            if n < s3: return True
            while stack and stack[-1] < n: s3 = stack.pop()
            stack.append(n)
        return False
Copy The Code & Try With Live Editor

Input

x
+
cmd
nums = [3,1,4,2]

Output

x
+
cmd
true
Advertisements

Demonstration


Previous
#455 Leetcode Assign Cookies Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#457 Leetcode Circular Array Loop Solution in C, C++, Java, JavaScript, Python, C# Leetcode