LeetCode’s 132 Pattern Explained
2 min readJul 26, 2019
Given a sequence of n integers a1, a2, …, an, a 132 pattern is a subsequence ai, aj, ak such that i < j < k and ai < ak < aj. Design an algorithm that takes a list of n numbers as input and checks whether there is a 132 pattern in the list.
Note: n will be less than 15,000.
Example 1:
Input: [1, 2, 3, 4]Output: FalseExplanation: There is no 132 pattern in the sequence.
Example 2:
Input: [3, 1, 4, 2]Output: TrueExplanation: There is a 132 pattern in the sequence: [1, 4, 2].
Please try this on your own before reading ahead.
In the 132 pattern, we observe that the the numbers at index i, j and k… k is always more than both i and j. So one check we definitely need to do is:
ai < ak && aj < ak
Then let’s see if it makes sense to store a minimum array of the minimum number up till all indexes.
Input: [3, 1, 4, 2]minArr: [3, 1, 1, 1]At index 0, the minimum number is the only number 3.
At index 1, the minimum number is the minimum of minArr[0] and input[1]. Which is 1.
At index 2, the minimum number is the…
