Python O(n) Solution


  • 0
    N

    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
    

Log in to reply
 

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