844. Does a 1-3-2 Pattern Exist
Read n values. Decide whether there are three positions i < j < k with
a[i] < a[k] < a[j]
that is, a low value, then a high value, then a middle value that sits strictly between them.
Print Yes or No.
1 2 3 4 -> No
3 1 4 2 -> Yes
-1 3 2 0 -> Yes
5 5 5 5 5 -> No
In 3 1 4 2 the triple is 1, 4, 2. In the last row every value is equal, and both inequalities
are strict, so nothing qualifies.
## Why the obvious loop is hopeless, and the obvious fix is not enough
Three nested loops are O(n^3). Fixing i as the running minimum so far cuts it to O(n^2),
but on 1 2 3 ... n that is still 2 * 10^10 at the limit.
## Scan from the RIGHT, and keep the best possible middle value
Walk from the right end towards the left. Maintain two things:
* a stack of values seen so far, kept DECREASING from the bottom up
* a single number third, the largest value that has ever been popped off that stack
The meaning of third is precise and is the whole trick. A value is popped when a strictly
larger value appears to its LEFT. So if third has a value at all, there is some position
j < k already scanned with a[j] > a[k] = third. In other words, third is the largest
middle value for which a valid high value already exists to its left.
So when the scan reaches position i, the only remaining question is whether a[i] < third. If
it is, the triple (i, j, k) is complete.
for i from n-1 down to 0:
if a[i] < third: answer Yes
while the stack is non-empty and its top < a[i]:
third = the popped value
push a[i]
## Why taking the LARGEST popped value is correct
third should be as large as possible, because a larger third is satisfied by more candidates
for a[i]. Since the stack decreases from the bottom up, the pops caused by one arrival come out
in increasing order, so assigning third on every pop leaves it holding the largest of them. And
third never needs to decrease later, since an old valid pair (j, k) stays valid forever.
## Why the stack must decrease
The stack holds candidates for the HIGH value a[j], and only values with nothing larger to their
right can ever serve: something larger to the right would have popped them and become a better
high value at the same time. That is the usual domination argument, and it is why one pop each is
enough.
## The comparison that decides the flat case
Pop on top < a[i], strictly, and compare a[i] < third, strictly. Both inequalities in the
problem are strict, so equal values must never qualify. 5 5 5 5 5 is the test that catches a
loosened operator.
## Related problems
Problem 154 is the same right-to-left decreasing stack, used to REPORT what popped rather than to remember the largest thing popped.
## Sizes and widths
Values reach 10^9 in absolute size and the output is a single word. Only comparisons happen, so
nothing can overflow and 32 bits is enough, but note that a careless sentinel of 0 for third
would be wrong on an all-negative row, which is a different bug wearing the same clothes.
## Cost
Time O(n), one pass with at most n pushes and n pops. Space O(n).
Constraints - `1 ≤ n ≤ 200000` - `-10^9 ≤ a[i] ≤ 10^9`
Input
The first line contains one integer n.
The second line contains n integers a[0] ... a[n-1].
Output
Print one line containing the single word Yes if three positions form the pattern, or No if they do not. Print no other words.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.