# Single pass C++ O(n) space and time solution (8 lines) with detailed explanation.

• 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:

1. 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`.
2. We keep track of the `maximum` of such `s3` (which is always the most recently `popped` number from the `stack`).
3. 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).

EXAMPLE:
`i = 6`, nums = [ 9, 11, 8, 9, 10, 7, `9` ], S1 candidate = `9`, S3 candidate = `None`, Stack = `Empty`
`i = 5`, nums = [ 9, 11, 8, 9, 10, `7`, 9 ], S1 candidate = `7`, S3 candidate = `None`, Stack = `[9]`
`i = 4`, nums = [ 9, 11, 8, 9, `10`, 7, 9 ], S1 candidate = `10`, S3 candidate = `None`, Stack = `[9,7]`
`i = 3`, nums = [ 9, 11, 8, `9`, 10, 7, 9 ], S1 candidate = `9`, S3 candidate = `9`, Stack = `[10]`
`i = 2`, nums = [ 9, 11, `8`, 9, 10, 7, 9 ], S1 candidate = `8`, S3 candidate = `9`, Stack = `[10,9]` We have `8<9`, sequence `(8,10,9)` found!

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.

``````    bool find132pattern(vector<int>& nums) {
int s3 = INT_MIN;
stack<int> st;
for( int i = nums.size()-1; i >= 0; i -- ){
if( nums[i] < s3 ) return true;
else while( !st.empty() && nums[i] > st.top() ){
s3 = st.top(); st.pop();
}
st.push(nums[i]);
}
return false;
}
``````

• Brilliant solution.

I wrote a Java version, just 5 lines

``````public boolean find132pattern(int[] nums) {
Stack<Integer> stack = new Stack<>();
for (int i = nums.length - 1, two = Integer.MIN_VALUE; i >= 0; stack.push(nums[i--]))
if (nums[i] < two) return true;
else for (; !stack.empty() && nums[i] > stack.peek(); two = Math.max(two, stack.pop()));
return false;
}``````

• Great solution. I realized that s3 (or k) should be actually the top of the stack since this stack is tracking all s3 (k) candidates.
I wrote it in Python here:

``````def find132pattern(self, nums):
k_stack = [- sys.maxint - 1]
for l in range(len(nums)-1, -1, -1):
if nums[l] < k_stack[-1]: return True
else:
while k_stack and nums[l] > k_stack[-1]:  v = k_stack.pop()
k_stack.append(nums[l])
k_stack.append(v)
return False
``````

• very beautiful!!

• @Pumpkin78 You do not need to push e3 back on to the stack. Here is a shorter version:

``````def find132pattern(self, nums):
e3, st = float('-inf'), []
for e in reversed(nums):
if e < e3: return True
while st and e > st[-1]: e3 = st.pop()
st.append(e)
return False
``````

• @dalwise Nice observation! I have added your suggestion to the code.

• @Pumpkin78 Good point!

• @wit : Nice. you could use ArrayDeque instead of Stack which is deprecated.

• This post is deleted!

• Nice solution! For the syntax "else while", is this a new thing from the latest C++?

• You also can just leverage the input array to simulate a stack, so no extra space is required:

``````    public boolean find132pattern(int[] nums) {
int two = Integer.MIN_VALUE;
int index = nums.length;
for (int i=nums.length-1; i>=0; i--) {
if (nums[i] < two) return true;
while (index < nums.length && nums[i] > nums[index]) {
two = nums[index++];
}
nums[--index] = nums[i];
}
return false;
}
``````

• @ye23 good point!

• What if `8, 10, 5, 6, 7, 8, 9`, the inner `while` loop will pop() n-2 times, and the time complexity should be O(n^2).

So I think the worst time complexity is O(n^2), did I miss something?

• @zhugejunwei Each num can be at most poshed and popped once, the inner `while` loop will pop n-2 times only if n-2 items are pushed, and later pop cannot pop these n-2 items again since they are gone, so it is O(2n) but not O(n^2)

• Nice solution! For the syntax "else while", is this a new thing from the latest C++?

Actually, `else while` is not a new syntax for C++. It was just written in the same line. C++ uses curly brackets `{}` as the delimiter to separate "logic blocks". However, the convenience is that if a "logic block" contains only a single statement, the delimiter `{}` can be dropped (which is an intuitive convention in my opinion).

For example, the following two lines are equivalent:

``````if (A == 1) { f1(); f2(); }
if (A == 1) f1(), f2();
``````

Note that `,` operator makes `f1(), f2()` as a single statement, so no `{}` is needed. Just like in the code where the `while` loop itself is a single statement. The original code could be made more compact as

``````    bool find132pattern(vector<int>& a) {
stack<int> st;
for(int i = a.size()-1, s3 = INT_MIN; i >= 0; st.push(a[i--]))
if( a[i] < s3 ) return true;
else while(!st.empty() && a[i] > st.top()) s3 = st.top(), st.pop();
return false;
}
``````

• Brilliant idea! Neat and efficient.

I think the key points are:

1. keep the value of s3 as big as possible
2. use a "sorted" stack to maintain the candidates of s2 and s3.

The numbers inside the stack are s2 and the number that popped out is the maximum s3. So the last thing to do is to maintain the order of the stack.

• I've struggled with this problem for two days...
Finally, I get this idea. This is so cool solution.
FYI, S3 here is actually the mid value. S2 is the high value.

• I think you need to prove the following thing is correct for this algorithm correctness.
how to make sure the max value nums[j] always is stored in s3 when you check nums[i], where nums[j] < nums[k], j,k both > i.

If you always store this max value in s3 when you check every nums[i], you can find out the solution.

I almost can prove it but can't strictly prove it.

Anyway, I think this algorithm is hard.

Appreciate someone can prove this.

• This post is deleted!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.