Monotonicity: Find 1-3-2 Pattern
Given an array of numbers
A, find out whether it contains a 1-3-2 pattern. A 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 for 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²) by iterating over 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²). 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]}. Putting 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]. This is a contradiction.
Let the function be F(Interval) → Boolean, where the result of the function is true if and only if there is a Bronze-Gold-Silver pattern. The theorem says F is monotonic: for any interval, the function value of sub-intervals is no greater than the function value of the interval. How can we take advantage of this 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 exactly once. In the following algorithm, considering a number for Silver takes O(1) time. Therefore, we have an O(n) algorithm.
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 suitable 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