Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

456. 132 Pattern

Time: $O(n)$

Space: $O(n)$

			


class Solution {
 public:
  bool find132pattern(vector<int>& nums) {
    stack<int> stack;  // Max stack
    int ak = INT_MIN;  // We want to find a seq ai < ak < aj

    for (int i = nums.size() - 1; i >= 0; --i) {
      // Ai < ak, we're done because ai must also smaller than 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;
  }
};




			


class Solution {
  public boolean find132pattern(int[] nums) {
    Deque<Integer> stack = new ArrayDeque<>(); // Max stack
    int ak = Integer.MIN_VALUE;                // We want to find a seq ai < ak < aj

    for (int i = nums.length - 1; i >= 0; --i) {
      if (nums[i] < ak) // Ai < ak, we're done because ai must also smaller than aj
        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;
  }
}