456. 132 Pattern #

Problem #

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].

Problem Statement #

Given an integer sequence: a1, a2, …, an, a subsequence ai, aj, ak of the 132 pattern is defined as: when i < j < k, ai < ak < aj. Design an algorithm that, given a sequence of n numbers, checks whether the sequence contains a subsequence of the 132 pattern. Note: the value of n is less than 15000.

Solution Approach #

• A brute-force solution for this problem will definitely time out
• This problem is a classic monotonic stack solution. You can consider scanning forward from the end of the array while maintaining a decreasing sequence

Code #

package leetcode

import (
	"math"
)

// Solution 1: Monotonic stack
func find132pattern(nums []int) bool {
	if len(nums) < 3 {
		return false
	}
	num3, stack := math.MinInt64, []int{}
	for i := len(nums) - 1; i >= 0; i-- {
		if nums[i] < num3 {
			return true
		}
		for len(stack) != 0 && nums[i] > stack[len(stack)-1] {
			num3 = stack[len(stack)-1]
			stack = stack[:len(stack)-1]
		}
		stack = append(stack, nums[i])
	}
	return false
}

// Solution 2: Brute-force solution, times out!
func find132pattern1(nums []int) bool {
	if len(nums) < 3 {
		return false
	}
	for j := 0; j < len(nums); j++ {
		stack := []int{}
		for i := j; i < len(nums); i++ {
			if len(stack) == 0 || (len(stack) > 0 && nums[i] > nums[stack[len(stack)-1]]) {
				stack = append(stack, i)
			} else if nums[i] < nums[stack[len(stack)-1]] {
				index := len(stack) - 1
				for ; index >= 0; index-- {
					if nums[stack[index]] < nums[i] {
						return true
					}
				}
			}
		}
	}
	return false
}