Detect a Strict 132 Pattern
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Detect a Strict 132 Pattern
Given an integer array `nums`, determine whether it contains three indices `i < j < k` such that:
```text
nums[i] < nums[k] < nums[j]
```
The three selected values form a **132 pattern**: the first is smallest, the second is largest, and the third lies strictly between them. The selected positions do not need to be adjacent, but their order in the array must be preserved.
Return `true` if such a triple exists; otherwise return `false`.
### Function Interface
```cpp
class Solution {
public:
bool find132pattern(vector<int>& nums);
};
```
### Examples
**Example 1**
```text
Input: nums = [2,8,5,1]
Output: true
```
Choose indices `0, 1, 2`. Their values are `2, 8, 5`, and `2 < 5 < 8`.
**Example 2**
```text
Input: nums = [1,2,2,3]
Output: false
```
No later value is strictly between an earlier value and an intervening larger value. The two equal values of `2` cannot satisfy a strict inequality.
### Constraints
- `1 <= nums.size() <= 200000`.
- `-1000000000 <= nums[i] <= 1000000000`.
### Clarifications
- All three indices must be distinct and satisfy `i < j < k`.
- Both value comparisons are strict; equality does not count.
- Negative values are allowed.
- Arrays with fewer than three elements return `false`.
- Return only whether a pattern exists, not its indices or values.
### What a Strong Answer Covers
- Correct index order and both strict inequalities for any reported pattern.
- A justification that a `false` result rules out every eligible triple.
- Handling of repeated and negative values, with resource costs suitable for `200000` elements.
Overview: Determine whether three array positions form a strict 132 pattern while preserving index order, including repeated and negative values.
