LeetCode: 132 Pattern

Posted on January 11, 2018July 26, 2020 by braindenny

Check whether 132 pattern exists in the given array

Similar Problems:

Given a sequence of n integers a1, a2, …, an, a 132 pattern is a subsequence ai, aj, ak such that i < j < k and 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].

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

// https://code.dennyzhang.com/132-pattern
// Basic Ideas: monotone stack
//
//  Evaluate each item as the candidacy as aj
//  ai should be the smallest value so far.
//  With ai and aj given, we need to figure out ak
//
//  When moving from right to left, the smallest value will keep increasing
//
//  Question: why elements in the stack keep decreasing?
//       Elements in stack are the candidates for ak
//       If it increase, we can drop previous candidates.
//
//  6, 12, 3, 4, 6, 11, 20
//  6,  6, 3, 3, 3,  3, 3
// result: 6, 12, 11
//
// Complexity: Time O(n), Space O(n)
func find132pattern(nums []int) bool {
    mins := make([]int, len(nums))
    min := 1<<31-1
    for i, v := range nums {
        if v < min {
            min = v
        }
        mins[i] = min
    }
    stack := []int{}
    for i:=len(nums)-1; i>=0; i-- {
        // skip the local min values
        if nums[i] == mins[i] { continue }
        // Treat ai: mins[i], aj: nums[i]. Now need to find ak
        // mins[i] will keep growing. So any stack elements no smaller than mins[i] should be removed.
        for len(stack)>0 && stack[len(stack)-1] <= mins[i] {
            stack = stack[0:len(stack)-1]
        }
        // not for this round
        if len(stack) == 0 || (len(stack)>0 && stack[len(stack)-1]>=nums[i]) {
            stack = append(stack, nums[i])
        }
        // find a match
        if len(stack) > 0 && stack[len(stack)-1]>mins[i] && stack[len(stack)-1]<nums[i] {
            return true
        }
    }
    return false
}

Post Views: 3