456. 132 Pattern

Tags: [stack]

Link: https://leetcode.com/problems/132-pattern/?tab=Description

Given a sequence of n integers a1, a2, ..., an, a 132 pattern is a subsequence ai, aj, aksuch thati<j<kand ai< ak< aj. Design an algorithm that takes a list of n numbers as input and checks whether there is a 132 pattern in the list.

Note:n will be less than 15,000.

Example 1:

Input:
 [1, 2, 3, 4]

Output:
 False

Explanation:
 There is no 132 pattern in the sequence.

Example 2:

Input:
 [3, 1, 4, 2]

Output:
 True

Explanation:
 There is a 132 pattern in the sequence: [1, 4, 2].

Example 3:

Input:
 [-1, 3, 2, 0]

Output:
 True

Explanation:
 There are three 132 patterns in the sequence: [-1, 3, 2], [-1, 3, 0] and [-1, 2, 0].

Solution: Stack

class Pair(object):
    def __init__(self, min, max):
        self.min = min
        self.max = max


class Solution(object):
    def find132pattern(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        if not nums or len(nums) < 3:
            return False

        stack = []
        for num in nums:
            if not stack:
                stack.append(Pair(num, num))
            else:
                if num < stack[-1].min:
                    # Since
                    stack.append(Pair(num, num))
                elif num > stack[-1].min:
                    last = stack.pop()
                    if num < last.max:
                        return True
                    else:
                        last.max = num
                        while stack and num >= stack[-1].max:
                            stack.pop()

                        # At this moment, num < stack[-1].max
                        if stack and stack[-1].min < num:
                            return True

                        stack.append(last)

        return False

Revelation:

• When the elements' order in the sequence cannot be changed, and we think this problem may be solved in T = O(n), we can think about using stack to solve this problem.

Note:

Time complexity = O(n), n is the number of the given numbers.

Time Limited Exceeded

class Solution(object):
    def find132pattern(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        if not nums or len(nums) < 3:
            return False

        nums_len = len(nums)
        for i in xrange(nums_len - 2):
            for j in xrange(i + 1, nums_len - 1):
                for k in xrange(j + 1, nums_len):
                    if nums[i] < nums[k] < nums[j]:
                        return True

        return False

Note:

• Time complexity = O(n^3), n is the number of the given numbers.