132 Pattern

Intuition

Solution

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

        prev_min = nums[0]
        stack = []
        for num in nums:
            if num <= prev_min:
                prev_min = num
                continue
            while stack:
                small, big = stack[-1]
                if small < num < big:
                    return True
                elif num <= small:
                    break
                else:
                    stack.pop()
            stack.append((prev_min, num))
        return False


# Test Code

import unittest


class TestSolution(unittest.TestCase):
    def test_solution(self):
        cases = [
            ([4,1,3,-1,0,1], False),
            ([1, 2, 3, 4], False),
            ([-1, 3, 2, 0], True)
        ]
        for case, target in cases:
            self.assertEqual(Solution().find132pattern(case), target)


if __name__ == '__main__':
    unittest.main()