Skip to content

456. 132 Pattern 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
 public:
  bool find132pattern(vector<int>& nums) {
    stack<int> stack;  // a decreasing stack
    int ak = INT_MIN;  // Find a seq, where ai < ak < aj.

    for (int i = nums.size() - 1; i >= 0; --i) {
      // If ai < ak, done because ai must < aj.
      if (nums[i] < ak)
        return true;
      while (!stack.empty() && stack.top() < nums[i])
        ak = stack.top(), stack.pop();
      stack.push(nums[i]);  // `nums[i]` is a candidate of aj.
    }

    return false;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
  public boolean find132pattern(int[] nums) {
    Deque<Integer> stack = new ArrayDeque<>(); // a decreasing stack
    int ak = Integer.MIN_VALUE;                // Find a seq, where ai < ak < aj.

    for (int i = nums.length - 1; i >= 0; --i) {
      // ai < ak, done because ai must < aj.
      if (nums[i] < ak)
        return true;
      while (!stack.isEmpty() && stack.peek() < nums[i])
        ak = stack.pop();
      stack.push(nums[i]); // `nums[i]` is a candidate of aj.
    }

    return false;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
  def find132pattern(self, nums: list[int]) -> bool:
    stack = []  # a decreasing stack
    ak = -math.inf  # Find a seq, where ai < ak < aj.

    for num in reversed(nums):
      # If ai < ak, done because ai must < aj.
      if num < ak:
        return True
      while stack and stack[-1] < num:
        ak = stack[-1]
        stack.pop()
      stack.append(num)  # `nums[i]` is a candidate of aj.

    return False