# LeetCode 456: 132 Pattern

## Problem Restatement

We are given an integer array `nums`.

We need to determine whether there exists a subsequence of three elements:

```python
nums[i], nums[j], nums[k]
```

such that:

```python
i < j < k
```

and:

```python
nums[i] < nums[k] < nums[j]
```

This is called a `132 pattern`.

The order of indices is `1 -> 3 -> 2`.

The values must look like:

```python
small < middle < large
```

but they appear in the array as:

```python
small, large, middle
```

The official statement defines a 132 pattern exactly as a subsequence `nums[i]`, `nums[j]`, `nums[k]` with `i < j < k` and `nums[i] < nums[k] < nums[j]`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | An integer array `nums` |
| Output | `True` if a 132 pattern exists, otherwise `False` |
| Pattern | `nums[i] < nums[k] < nums[j]` |
| Index order | `i < j < k` |

Function shape:

```python
def find132pattern(nums: list[int]) -> bool:
    ...
```

## Examples

Example 1:

```python
nums = [1, 2, 3, 4]
```

The numbers are increasing.

There is no way to choose `i < j < k` such that the third chosen value lies between the first and second chosen values.

Answer:

```python
False
```

Example 2:

```python
nums = [3, 1, 4, 2]
```

Choose:

```python
nums[1] = 1
nums[2] = 4
nums[3] = 2
```

The indices satisfy:

```python
1 < 2 < 3
```

The values satisfy:

```python
1 < 2 < 4
```

So the array contains a 132 pattern.

Answer:

```python
True
```

Example 3:

```python
nums = [-1, 3, 2, 0]
```

One valid pattern is:

```python
nums[0] = -1
nums[1] = 3
nums[2] = 2
```

The values satisfy:

```python
-1 < 2 < 3
```

Answer:

```python
True
```

## First Thought: Brute Force

The most direct solution is to check every triplet.

```python
class Solution:
    def find132pattern(self, nums: list[int]) -> bool:
        n = len(nums)

        for i in range(n):
            for j in range(i + 1, n):
                for k in range(j + 1, n):
                    if nums[i] < nums[k] < nums[j]:
                        return True

        return False
```

This is correct because it checks every possible choice of `i`, `j`, and `k`.

## Problem With Brute Force

The brute force solution has three nested loops.

If `n = len(nums)`, the time complexity is:

```python
O(n^3)
```

This is too slow for large inputs.

We need to avoid testing every triplet directly.

## Key Insight

The pattern is:

```python
nums[i] < nums[k] < nums[j]
```

Think of the three values as:

| Pattern part | Value role |
|---|---|
| `nums[i]` | small value, the `1` |
| `nums[j]` | large value, the `3` |
| `nums[k]` | middle value, the `2` |

The hard part is preserving the index order:

```python
i < j < k
```

A clean way is to scan from right to left.

When scanning from right to left, we can maintain information about values to the right of the current index.

The algorithm keeps:

```python
third
```

where `third` means the best candidate for `nums[k]`, the `2` in the 132 pattern.

It also keeps a decreasing stack of possible `nums[j]` values, the `3` in the pattern.

If we later find a number smaller than `third`, then we have:

```python
nums[i] < nums[k] < nums[j]
```

and the index order is correct because `nums[i]` is to the left of both values that created `third`.

## Algorithm

Initialize:

```python
third = float("-inf")
stack = []
```

Scan `nums` from right to left.

For each number `x`:

1. If `x < third`, return `True`.

   This means `x` can be the `1`, and `third` can be the `2`.

2. While the stack is not empty and the top of the stack is smaller than `x`, pop it.

   Each popped value can be a valid `2`, because it is smaller than `x`.

3. Update `third` to the popped value.

4. Push `x` onto the stack as a possible future `3`.

If the loop finishes, return `False`.

## Walkthrough

Use:

```python
nums = [3, 1, 4, 2]
```

Start:

```python
third = -inf
stack = []
```

Scan from right to left.

First, `x = 2`.

There is no smaller stack value to pop.

Push `2`.

```python
third = -inf
stack = [2]
```

Next, `x = 4`.

The stack top `2` is smaller than `4`, so pop it.

Now `2` becomes a candidate for the `2` in the 132 pattern:

```python
third = 2
stack = []
```

Push `4` as a possible `3`.

```python
third = 2
stack = [4]
```

Next, `x = 1`.

Now:

```python
x < third
1 < 2
```

So we found:

```python
1 < 2 < 4
```

The pattern exists.

Return:

```python
True
```

## Correctness

The stack stores possible `nums[j]` values from the right side of the current scan position.

When processing a value `x`, every stack value smaller than `x` can serve as `nums[k]` with `x` serving as `nums[j]`, because that popped value appears to the right of `x` and is smaller than `x`.

The variable `third` stores the largest popped value seen so far. This gives the strongest possible candidate for `nums[k]`, because a larger `nums[k]` makes it easier to find a smaller `nums[i]`.

If at some later point we find a value `x` such that:

```python
x < third
```

then `x` appears to the left of the `nums[j]` and `nums[k]` pair that created `third`.

So the indices satisfy:

```python
i < j < k
```

and the values satisfy:

```python
nums[i] < nums[k] < nums[j]
```

Therefore, a valid 132 pattern exists.

If the algorithm never finds `x < third`, then no value to the left can complete any valid `nums[j], nums[k]` pair. Thus no 132 pattern exists.

## Complexity

Let `n = len(nums)`.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | Each element is pushed and popped at most once |
| Space | `O(n)` | The stack may store up to `n` elements |

## Implementation

```python
class Solution:
    def find132pattern(self, nums: list[int]) -> bool:
        third = float("-inf")
        stack = []

        for x in reversed(nums):
            if x < third:
                return True

            while stack and stack[-1] < x:
                third = stack.pop()

            stack.append(x)

        return False
```

## Code Explanation

We use:

```python
third = float("-inf")
```

This stores the best known candidate for `nums[k]`, the middle value in the 132 pattern.

At the start, we have not found any candidate, so it is negative infinity.

The stack stores possible `nums[j]` values:

```python
stack = []
```

Then we scan from right to left:

```python
for x in reversed(nums):
```

If:

```python
if x < third:
```

then `x` can be `nums[i]`, and `third` can be `nums[k]`.

Since `third` was created by popping a value below some larger `nums[j]`, we already know there is a valid `nums[j]` to complete the pattern.

The loop:

```python
while stack and stack[-1] < x:
    third = stack.pop()
```

means that every smaller value to the right of `x` can become the `2` in the pattern, while `x` becomes the `3`.

Finally:

```python
stack.append(x)
```

adds `x` as a possible future `3`.

If no pattern is found:

```python
return False
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.find132pattern([1, 2, 3, 4]) is False
    assert s.find132pattern([3, 1, 4, 2]) is True
    assert s.find132pattern([-1, 3, 2, 0]) is True
    assert s.find132pattern([1, 0, 1, -4, -3]) is False
    assert s.find132pattern([3, 5, 0, 3, 4]) is True
    assert s.find132pattern([1, 2]) is False
    assert s.find132pattern([1, 4, 0, -1, -2, -3, -1, -2]) is True

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[1,2,3,4]` | Increasing array has no 132 pattern |
| `[3,1,4,2]` | Standard positive case |
| `[-1,3,2,0]` | Multiple valid patterns |
| `[1,0,1,-4,-3]` | No valid pattern despite rises and drops |
| `[3,5,0,3,4]` | Pattern appears after earlier noise |
| `[1,2]` | Fewer than three elements |
| `[1,4,0,-1,-2,-3,-1,-2]` | Negative values and late pattern |