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.
Example 1:
Input: nums = [1,2,3,4]
Output: false
Explanation: There is no 132 pattern in the sequence.
Example 2:
Input: nums = [3,1,4,2]
Output: true
Explanation: There is a 132 pattern in the sequence: [1, 4, 2].
Example 3:
Input: nums = [-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 <= 3 * 104
-109 <= nums[i] <= 109
Solution:
class Solution {
public boolean find132pattern(int[] nums) {
int n = nums.length;
int[] smallerInLeft = new int[n];
// 3 1 4 2
// - - 1 1
Arrays.fill(smallerInLeft, Integer.MAX_VALUE);
int minSoFar = Integer.MAX_VALUE;
for (int i = 0; i < n; i ++) {
int curr = nums[i];
if (minSoFar < curr) {
smallerInLeft[i] = minSoFar;
}
minSoFar = Math.min(minSoFar, curr);
}
// 3 1 4 2
// 2 - 2 -
int[] smallerInRight = new int[n];
Arrays.fill(smallerInRight, Integer.MIN_VALUE);
TreeSet<Integer> set = new TreeSet();
for (int i = n - 1; i >= 0; i --) {
int curr = nums[i];
Integer smaller = set.floor(curr - 1);
if (smaller != null) {
smallerInRight[i] = smaller;
}
set.add(curr);
}
// System.out.println(Arrays.toString(smallerInLeft));
// System.out.println(Arrays.toString(smallerInRight));
for (int i = 0; i < n; i ++) {
if (smallerInLeft[i] < smallerInRight[i]) {
return true;
}
}
return false;
}
}
QUESTION: To search for a subsequence (s1,s2,s3) such that s1 < s3 < s2.
INTUITION: Suppose we want to find a 123 sequence with s1 < s2 < s3, we just need to find s3, followed by s2 and s1. Now if we want to find a 132 sequence with s1 < s3 < s2, we need to switch up the order of searching. we want to first find s2, followed by s3, then s1.
DETECTION: More precisely, we keep track of highest value of s3 for each valid (s2 > s3) pair while searching for a valid s1 candidate to the left. Once we encounter any number on the left that is smaller than the largest s3 we have seen so far, we know we found a valid sequence, since s1 < s3 implies s1 < s2.
ALGORITHM: We can start from either side but I think starting from the right allow us to finish in a single pass. The idea is to start from end and search for valid (s2,s3) pairs, we just need to remember the largest valid s3 value, using a stack will be effective for this purpose. A number becomes a candidate for s3 if there is any number on the left bigger than it.
CORRECTNESS: As we scan from right to left, we can easily keep track of the largest s3 value of all (s2,s3) candidates encountered so far. Hence, each time we compare nums[i] with the largest candidate for s3 within the interval nums[i+1]...nums[n-1] we are effectively asking the question: Is there any 132 sequence with s1 = nums[i]? Therefore, if the function returns false, there must be no 132 sequence.
IMPLEMENTATION:
Have a stack, each time we store a new number, we first pop out all numbers that are smaller than that number. The numbers that are popped out becomes candidate for s3.
We keep track of the maximum of such s3 (which is always the most recently popped number from the stack).
Once we encounter any number smaller than s3, we know we found a valid sequence since s1 < s3 implies s1 < s2.
RUNTIME: Each item is pushed and popped once at most, the time complexity is therefore O(n).
EDIT: Thanks @Pumpkin78 and @dalwise for pointing out that the maximum candidate for s3 is always the recently popped number from the stack, because if we encounter any entry smaller than the current candidate, the function would already have returned. EDIT 2: Rephrased explanations and added a sketch of the correctness proof.
class Solution {
public boolean find132pattern(int[] nums) {
int s3 = Integer.MIN_VALUE;
Stack<Integer> stack = new Stack<Integer>();
for (int i = nums.length - 1; i >= 0; i--) {
if (nums[i] < s3) {
return true;
} else {
while (!stack.isEmpty() && nums[i] > stack.peek()) {
s3 = stack.pop();
}
stack.push(nums[i]);
}
}
return false;
}
}
The idea is the same as the problem "find next greater element", but here we change to find the next smaller. From end to start, if we find nums[i] is less than the maximum element that is smaller than another, then we can say we find the pattern. update @ 12/15/2019 For example [..., 4, 6, 1, 3, ...], when finding the 132 pattern from left to right, we need to find the target in the range (1, 3) and (4, 6), these are incontinuous intervals, but from right to left, we only need to check whether the number n is in range (-inf, 3), if yes, then [n, 4or6, 3] is in pattern 132.
[ 9, 11, 8, 9, 10, 7, 9 ]
class Solution {
public boolean find132pattern(int[] nums) {
Stack<Integer> maxStack = new Stack<>();
int second = Integer.MIN_VALUE;
for (int i = nums.length - 1; i >= 0; i--) {
while (!maxStack.isEmpty() && maxStack.peek() < nums[i]) {
second = maxStack.pop();
}
if (nums[i] > second) maxStack.push(nums[i]);
if (nums[i] < second) return true;
}
return false;
}
}