Check whether 132 pattern exists in the given array
Similar Problems:
- Split Array into Consecutive Subsequences
- Leetcode: Beautiful Array
- CheatSheet: Leetcode For Code Interview
- Tag: #subsequence, #inspiring, #stack, #wiggle
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
}
