Monotonicity: Find 1-3-2 Pattern
Given an array of numbers
A, find out whether it contains a 1-3-2 pattern. An 1-3-2 pattern is a subsequence of three numbers, A[i], A[j] and A[k] such that i<j<k and A[i] < A[k] < A[j].
For clarity, let's call the 1-3-2 pattern the Bronze-Gold-Silver pattern. If A[j] is Gold, then we should consider the minimum number from A[0:j) to be Bronze, because it gives us the largest range of picking Silver. Once we have Bronze and Gold, we can iterate over A[j+1:n) to find Silver. With this observation, we can find the pattern in O(n^2) by iterating Gold. We can improve the algorithm by preprocessing f[i]=min{A[0:i)} in linear time. However, the time complexity is still O(n^2). Can we find the pattern in O(n)?
The monotonic function
Theorem: Consider any interval A[i:j], if there is no pattern when choosing Bronze and Gold from the interval, then for every sub-interval A[i':j'] where i<=i'<=j'<=j, there is no pattern when choosing Bronze and Gold from the sub-interval.
Proof by contradiction. Let A[k] be the Silver of any 1-3-2 pattern when choosing Bronze and Gold from A[i':j']. Then, we have max{A[i':j']} > A[k]>min{A[i':j']} by definition. Because A[i':j'] is a sub-interval of A[i:j], we have min{A[i':j']} > min{A[i:j]} and max{A[i':j:]} < max{A[i:j]}. Put these inequalities together, we have max{A[i:j]} > A[k] > min{A[i:j]}, which means, there is a pattern when choosing Bronze and Gold from A[i:j]. Contradiction.
Let the function be F(Interval) -> Boolean, where the result of the function is true iff there is a Bronze-Gold-Silver pattern. The theorem says F is monotonic: for any interval, the function value of sub-intervals is no more than the function value of interval. How can we take advantage of the monotonicity?
Consider each number as Silver for the largest possible interval, if there is no pattern, then we don't need to consider the number again for all sub-intervals. We'll start with the largest interval, A[0:n-1) and shrink the interval one by one from the right side. This way, each number is considered for Silver at once. In the following algorithm, the consideration of a number for Silver is O(1). Therefore, we have an algorithm in O(n).
1func find132pattern(a []int) bool {
2 n := len(a)
3 // f[i] = min{A[0:i]}
4 f := make([]int, n)
5 f[0] = a[0]
6 for i := 1; i < n; i++ {
7 f[i] = min(f[i-1], a[i])
8 }
9 // candidates for silver.
10 var s []int
11 // enumerate candidates for Gold
12 for i := n - 1; i >= 1; i-- {
13 // a[i] is not fit for Gold nor Silver
14 if a[i] <= f[i] {
15 continue
16 }
17 // check each silver candidate
18 for len(s) > 0 && s[len(s)-1] <= f[i] {
19 s = s[:len(s)-1]
20 }
21 // found it!
22 if len(s) > 0 && s[len(s)-1] < a[i] {
23 return true
24 }
25 // a[i] cannot be Gold, but it could be Silver
26 s = append(s, a[i])
27 }
28 return false
29}
You can practice the problem at LeetCode 456