# Python O(n) Solution

• Just as jade86, we named ai, aj, ak as s1, s2, s3.

Use a stack to keep track of an increasing sequence, if a number is in the range of this increasing sequence (exclusive), then it is a valid s3. When we meet a number smaller than the top of the stack, we need to start with a new increasing sequence, and we use lo and hi to keep track of previous stacks ranges. If we can find a number within the range (lo, hi), it is also a valid s3.

PS: I was trying to use a list to keep track of the ranges of all increasing equences, but got TLE for TestCase 92/95. Then I found we can merge these ranges, and make it easier and faster.

For example, nums = [8, 10, 4, 6, 2, 3, 5], when we traverse to 5, we would have 3 increasing sequence [8, 10], [4, 6], [2, 3], a number falls into any of these ranges would be a valid s3. To make the comparison easy, we merge these 3 ranges to [3, 10], so we only need to check if a number is within [3, 10], and 5 is the s3 we need.

class Solution(object):
def find132pattern(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
stack = []
lo = float('inf')
hi = float('-inf')
for num in nums:
if len(stack) >= 2 and stack[0] < num < stack[-1]:
return True

if lo < num < hi:
return True

if stack and num < stack[-1]:
if len(stack) >= 2:
lo = min(lo, stack[0])
hi = max(hi, stack[-1])
stack = []
stack.append(num)

return False

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.