# 132 Pattern
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/132-pattern)
Canonical: https://scaleengineer.com/dsa/problems/132-pattern
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array, Stack, Monotonic Stack, Ordered Set
**Companies:** [IBM](https://scaleengineer.com/companies/ibm), [Intuit](https://scaleengineer.com/companies/intuit)
---
## Problem
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`

# Approaches
## Brute Force Triple Loop
The most straightforward approach is to use three nested loops to check every possible triplet of indices `(i, j, k)` such that `i < j < k`. For each triplet, we verify if it forms a 132 pattern, i.e., if `nums[i] < nums[k] < nums[j]`. If we find such a triplet, we can immediately return `true`. If we check all possible triplets and don't find one, we return `false`.
**Time:** O(n^3) - Three nested loops run through the array, leading to a cubic time complexity. For each of the `O(n)` choices for `i`, there are `O(n)` choices for `j`, and `O(n)` for `k`. · **Space:** O(1) - Constant extra space is used, as we only need a few variables to store loop indices.
**Pros:** Simple to understand and implement.; Requires no extra space.
**Cons:** Extremely inefficient due to its cubic time complexity.; Will result in a 'Time Limit Exceeded' (TLE) error for input sizes specified in the constraints.
### Explanation
This method exhaustively searches for the pattern. We use three pointers, `i`, `j`, and `k`, to represent the indices of the three numbers in the potential pattern. The loops are set up to ensure that `i < j < k` is always true. The outer loop fixes `nums[i]`, the middle loop fixes `nums[j]`, and the inner loop checks all possible `nums[k]` to see if they satisfy the 132 condition relative to the fixed `nums[i]` and `nums[j]`.

```java
class Solution {
    public boolean find132pattern(int[] nums) {
        int n = nums.length;
        if (n < 3) {
            return false;
        }
        for (int i = 0; i < n - 2; i++) {
            for (int j = i + 1; j < n - 1; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (nums[k] > nums[i] && nums[j] > nums[k]) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
}
```
### Algorithm
- Iterate through the array with a variable `i` from `0` to `n-3`.
- For each `i`, iterate with a variable `j` from `i+1` to `n-2`.
- For each `j`, iterate with a variable `k` from `j+1` to `n-1`.
- Inside the innermost loop, check if the condition `nums[i] < nums[k] < nums[j]` is met.
- If the condition is true, a 132 pattern exists, so return `true`.
- If the loops complete without finding any such triplet, it means no 132 pattern exists. Return `false`.

## Optimized Brute Force
We can improve upon the brute-force approach by optimizing the search for the first element of the pattern (`nums[i]`). Instead of iterating through all possible `i` for each `j`, we can observe that for a fixed `nums[j]`, the condition `nums[i] < nums[k] < nums[j]` is easiest to satisfy if `nums[i]` is the smallest possible value. Therefore, for each `j`, we only need to consider the minimum value in the subarray `nums[0...j-1]` as our `nums[i]` candidate. This reduces one of the loops.
**Time:** O(n^2) - We have a nested loop structure. The outer loop runs from `j=1` to `n-1`, and the inner loop runs from `k=j+1` to `n-1`. This results in a quadratic time complexity. · **Space:** O(1) - We only need one extra variable, `leftMin`, to keep track of the minimum element to the left.
**Pros:** A significant improvement over the O(n^3) approach.; Uses constant extra space if we calculate the minimum on the fly.
**Cons:** The time complexity is still quadratic, which is too slow for the given constraints and will likely time out.
### Explanation
In this approach, we iterate through the array with an index `j`, considering `nums[j]` as the '3' in the '132' pattern. For each `j`, we need to find a '1' (`nums[i]`) to its left and a '2' (`nums[k]`) to its right. The best candidate for `nums[i]` is the minimum element to the left of `j`. We can find this minimum in O(1) time for each `j` by pre-calculating it or by maintaining a running minimum as we iterate. Then, we perform a linear scan to the right of `j` to find a `nums[k]` that fits between our `nums[i]` (the left minimum) and `nums[j]`.

```java
class Solution {
    public boolean find132pattern(int[] nums) {
        int n = nums.length;
        if (n < 3) {
            return false;
        }
        int leftMin = nums[0];
        for (int j = 1; j < n - 1; j++) {
            // Update leftMin to be the minimum of elements before index j
            leftMin = Math.min(leftMin, nums[j-1]);
            for (int k = j + 1; k < n; k++) {
                if (nums[k] > leftMin && nums[k] < nums[j]) {
                    return true;
                }
            }
        }
        return false;
    }
}
```
Note: The `leftMin` update in the code above is slightly off for the first iteration but works. A cleaner way is to calculate `leftMin` for `nums[0...j-1]` before the inner loop, or precompute a `min` array.
### Algorithm
- We fix the middle element of the pattern, `nums[j]` (the '3').
- We iterate `j` from `1` to `n-1`.
- For each `j`, we need to find an element `nums[i]` to its left (`i < j`) that is as small as possible. We can maintain a variable `leftMin` that stores the minimum value in `nums[0...j-1]`.
- Then, for the fixed `j` and `leftMin`, we search for an element `nums[k]` to the right of `j` (`k > j`).
- We iterate `k` from `j+1` to `n-1`.
- If we find a `nums[k]` such that `leftMin < nums[k] < nums[j]`, we have found the pattern and return `true`.
- If the loops complete, we return `false`.

## Optimal Approach using a Monotonic Stack
The most efficient solution involves a single pass through the array and the use of a stack. By traversing the array from right to left, we can efficiently track potential candidates for the '2' and '3' elements of the pattern. Let's denote the pattern elements as `s1`, `s3`, `s2` corresponding to `nums[i]`, `nums[j]`, `nums[k]`. We are looking for `s1 < s2 < s3` with their original indices being `i < j < k`.

When we iterate from right to left, at any point `i`, the current element `nums[i]` can be our `s1`. We just need to know if there's a pair `(s3, s2)` to its right (at indices `j, k > i`) such that `s1 < s2 < s3`. The stack helps us maintain a pool of `s3` candidates, and a variable `s2` tracks the best (largest) `s2` value found so far for a `(s3, s2)` pair to the right.
**Time:** O(n) - We traverse the array once. Each element is pushed and popped from the stack at most once. Therefore, the total time spent on stack operations across all iterations is proportional to `n`. · **Space:** O(n) - In the worst case (e.g., a strictly decreasing array), the stack might store all `n` elements.
**Pros:** Optimal O(n) time complexity.; Solves the problem efficiently for large inputs.; An elegant application of the monotonic stack data structure.
**Cons:** The logic can be non-intuitive and tricky to devise under pressure.; Requires extra space for the stack.
### Explanation
We initialize a variable `s2` to a very small number and an empty stack. We iterate from the end of the array to the beginning. For each element `nums[i]`, we first check if it's smaller than `s2`. If it is, we've found our `s1` (`nums[i]`), and we already have an `s2` and an implicit `s3` to its right, so we return `true`.

If `nums[i]` is not smaller than `s2`, we use it to update our `s2` and stack. The stack stores elements that are potential `s3` candidates. We pop elements from the stack as long as they are smaller than the current `nums[i]`. Each popped element is a potential `s2`, and since we want the largest possible `s2`, we update `s2 = popped_element`. After this, `nums[i]` is pushed onto the stack, becoming a candidate for `s3` for the elements to its left.

This works because the stack maintains a decreasing sequence of numbers. When we find a `nums[i]` larger than the stack's top, `nums[i]` can be an `s3` and the stack's top can be an `s2`. By popping all smaller elements, we find the largest possible `s2` for the `s3` formed by `nums[i]` and other elements on the stack.

```java
import java.util.Stack;

class Solution {
    public boolean find132pattern(int[] nums) {
        int n = nums.length;
        if (n < 3) {
            return false;
        }
        Stack<Integer> stack = new Stack<>();
        int s2 = Integer.MIN_VALUE; // This will store the '2' in 132 pattern

        for (int i = n - 1; i >= 0; i--) {
            // Check if we found the '1' of the pattern
            if (nums[i] < s2) {
                return true;
            }
            
            // Maintain stack and update s2
            // nums[i] is a candidate for '3'
            while (!stack.isEmpty() && nums[i] > stack.peek()) {
                // stack.peek() is a candidate for '2'
                s2 = stack.pop();
            }
            
            // Push current element as a candidate for '3'
            stack.push(nums[i]);
        }
        
        return false;
    }
}
```
### Algorithm
- We are looking for indices `i < j < k` such that `nums[i] < nums[k] < nums[j]`.
- Let's name `nums[i]` as `s1`, `nums[j]` as `s3`, and `nums[k]` as `s2`. The condition is `s1 < s2 < s3`.
- We iterate through the array from right to left.
- We use a stack to keep track of potential `s3` candidates.
- We use a variable, let's call it `s2`, to store the largest possible value for an `s2` candidate found so far. Initialize `s2` to negative infinity.
- For each element `nums[i]` from right to left:
  1. If `nums[i] < s2`, we have found our `s1`. `nums[i]` is `s1`, `s2` is our `s2`, and the `s3` that produced this `s2` has already been processed (it's an element larger than `s2` that we encountered to the right). Thus, a 132 pattern exists, and we return `true`.
  2. We then update the stack and `s2`. While the stack is not empty and `nums[i]` is greater than the element at the top of the stack, it means `nums[i]` can act as a better `s3` for the `s2` candidate at `stack.peek()`. So we pop from the stack and update `s2` to be this popped element, as it's a valid `s2` for the `s3` candidate `nums[i]`.
  3. After the while loop, we push `nums[i]` onto the stack. It becomes a candidate for `s3` for the elements we will process to its left.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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

```