456. 132 Pattern

LeetCode 456. 132 Pattern****

Description

Given an array of n integers nums, a 132 pattern is a subsequence of three integers nums[i], nums[j] and nums[k] such that i < j < k and nums[i] < nums[k] < nums[j].

Return true if there is a 132 pattern in nums, otherwise, return false.

Follow up: The O(n^2) is trivial, could you come up with the O(n logn) or the O(n) solution?

Example 1:

Input: [1, 2, 3, 4]

Output: False

Explanation: There is no 132 pattern in the sequence.

Example 2:

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

Constraints:

• n == nums.length

• 1 <= n <= 10^4

• -10^9 <= nums[i] <= 10^9

Tags

Stack

Solution

基础思想是对于每一个已确定的nums[j]，我们先在j之前找出最小的nums[i]，以保证区间[nums[i], nums[j]]足够大，才更有可能找到符合要求的nums[k]。

我们可以先构建一个数组mins，有mins[i]=min(nums[:i-1])。然后倒序遍历nums，用一个单调栈维护所有可能的元素nums[k]。在循环中，如果有mins[i] ≥ nums[i]则跳过本次循环。当栈不为空时，先持续出栈直至栈顶元素不再小于等于mins[i]，然后检查这时的栈顶元素是否小于nums[i]，如果是则说明找到这个pattern，返回true。循环结束时总是把nums[i]入栈。最后返回false。

The basic idea is that, for a particular number nums[j], we can find the smallest nums[i] where i<j, to maximize the interval [nums[i], nums[j]], so that it is more likely to find a required nums[k].

We first maintain all the smallest nums[i] in a min array, where requires mins[i]=min(nums[:i-1]). Then we traverse nums in a descending order and use a stack to keep track of all potential nums[k]. In the loop, we continue to check i-1 if mins[i] ≥ nums[i]. We always push to nums[i] the stack when a loop ends. When the stack is not empty, we keep on popping elements from the stack until stack[top] ≤ min[k]. Then check that if the statement stack[top] < nums[i] is satisfied we can return a true value. In the end, we return a false value due to no elements in the stack satisfing the 132 pattern.

Complexity

• Time complexity: $O(n)$. You may notice there is a nested for-loop in the second part. But we can note that atmost n elements can be pushed and popped off the stack in total. Thus the second traversal requires only $O(2n)=O(n)$ time.

• Space complexity: $O(n)$

Code

func find132pattern(nums []int) bool {
	if len(nums) < 3 {
		return false
	}
	mins, stack := make([]int, len(nums)), make([]int, 0, len(nums))
	mins[0] = nums[0]
	for i := 1; i < len(nums); i++ {
		mins[i] = min(mins[i-1], nums[i])
	}
	for i := len(nums) - 1; i >= 0; i-- {
		if mins[i] >= nums[i] {
			continue
		}
		for len(stack) > 0 && stack[len(stack)-1] <= mins[i] {
			stack = stack[:len(stack)-1]
		}
		if len(stack) > 0 && stack[len(stack)-1] < nums[i] {
			return true
		}
		stack = append(stack, nums[i])
	}
	return false
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

Reference

1. https://leetcode.com/problems/132-pattern/solution/