All problems

132 Pattern

Medium · stack

You are given a list of integers nums.

A 132 pattern is three positions i < j < k (in that order from left to right) whose values satisfy nums[i] < nums[k] < nums[j]. In words: a low value, then a high value, then a value that lies strictly between the low one and the high one. The name comes from the ranks of the three values: smallest first, largest second, middle third.

Return true if the list contains at least one 132 pattern, and false otherwise. The three positions do not have to be next to each other, and values may repeat.

Examples

Example 1

Input: nums = [5, 1, 8, 6]

Output: true

Take the values 1, 8 and 6 at positions 1, 2 and 3: 1 < 6 < 8.

Example 2

Input: nums = [1, 2, 3, 4]

Output: false

The list only goes up, so a later value is never smaller than an earlier one.

Example 3

Input: nums = [6, 5, 4, 7, 1, 3]

Output: false

After the 7 only 1 and 3 follow, and neither is above any value that sits before the 7.

Constraints