132 Pattern

Photo by Alexandru Acea on Unsplash

In this post, I would like to give the detailed thinking process that can lead you to the one pass O(N) stack solution.

It may be a little bit detailed as a post, but this is how we can come up with a solution. For problems like this one, we need to examine different test cases and think of a generalized algorithm that takes them all into account. This is programming in fact.

Problem:

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.

Source : Leetcode 456

ak is the last value we encounter to say if the pattern is a solution or not. The smaller ai is and the greater aj is, the more likely we will find an ak between them. The extreme theoretical case is ai = -infinity and aj = +infinity, any new value will be between them and we will have a 132 pattern.

Let’s look at this example [5, 3, 7, 4] and write down some first notices:

• The first element of the array can only be a candidate of ai.
• For each number, it can be either a new ai, a new aj, or an ak. If it is an ak (smaller than current aj and greater than current ai) we have found a pattern.
• A new ai can only be less than the current ai because we are looking for the smallest possible value of ai.
• A new aj can only be higher than the current aj because we are looking for the highest possible value of aj.

First Try : Let’s see if we can only use two variables ai and aj that we update while iterating over the array.

For the example above, we may do the following:

• Initialize ai=+infinity, aj = -infinity
• For the first element 5, it will be the current ai.
• The second element is 3 it is less than 5, we update ai=3.
• The third element is 7, it is higher than aj, so we update aj = 7
• The forth element 4 is between ai=3 and aj=7, so we found the pattern.

Ok, for this example, two variables were sufficient. Let’s slightly modify the previous example and see if it is going to work : [5, 3, 7, 0, 2, 1]

In this example we remove the last value 4 from the previous array and add 0, 2, 1 in order to see whether we are able to detect the new pattern 0, 2, 1.

• At the forth value 0, it is smaller than ai=3, can we directly update ai ? No, if we do so we will have ai=0, and aj is still equal to 7. However we never had 0 before 7 in the array.
• Ok, can we just ignore the previous (ai, aj), take ai=0 and reset aj=-infinity?
  No, if we have [5, 3, 7, 0, 4] then 3, 7, 4 is the pattern. Ignoring the couple (3, 7) we won’t be able to detect the pattern and 0 didn’t help for this example.
• Ok, Can we ignore 0 ?
  No, if we have [5, 3, 7, 0, 2, 1] (which is the current example), then 0, 2, 1 is the pattern. We must not ignore the 0 as well !

Conclusion of First Try
It looks like we can’t work with only one couple (ai,aj)

• For [5, 3, 7, 0, 2], if we have 4 afterwards, 3, 7, 4 will be the pattern. If we have 1 afterwards 0, 2, 1 will be the pattern.

Second Try: Work with 2 couples (ai, aj)?

Let’s think about a counter-example. If there is no such an example, we will go ahead with the implementation.

Take this one [8, 10, 5, 7, 2, 4]

For this example we have 3 intervals : (8, 10), (5, 7) and (2, 4).
- If we have 9 afterwards then the first interval gives the pattern
- If we have 6 afterwards, it’s the second interval that gives the solution.
- Same for the third interval if we have 3 afterwards.

Conclusion of Second Try
We definitely need a list of intervals !

Now, how can we maintain this list, meaning how can we update / insert / delete intervals from it ?

Let’s Take an example [3, 5, 0, 2, 8]:
When we are at 2, we have two intervals (3, 5) and (0, 2).

For 8, it does not fall in any interval, so we haven’t yet found a pattern. And because 8 comes after 0 in the array, we can take just this as a new interval. We don’t need the other elements.

This suggests that there are some cases in which we need to merge some intervals.

If we had:

If the next element is 6 we will need to merge the first two intervals:

So it is more clear now that we need an array of ordered intervals. If the current value falls in any interval, we found the pattern, otherwise we need to eventually merge some intervals.

Merging intervals will be done by removing the first interval while its end is smaller than the current element. And then insert the merged interval at the head of the array.

Each deletion/insertion of the first element of an array has O(N) time complexity (because of left shifting next elements).

In worst case we have O(N) deletions/insertions, so the total time complexity will be O(N²).

Think a little bit more …

You will find out that any merge you are doing is between the first interval and an interval from the middle. So why not just invert the order and delete the last element instead of the first element of the array.

The array of intervals for our example will look like this [[7, 8], [3, 5], [0, 2]]. When we have 6 afterwards we delete the last interval while 6 is greater than the end of the interval. and then insert [0, 6] => [[7, 8], [0, 6]].

Take a step back. What are the operations we are doing here ?

• Delete the last element
• Insert at the end of the array

So this becomes a stack in fact ! And because deletion and insertion at the top of the stack takes O(1) time, the total time complexity is O(N) !

Once you have these key elements, the code is easy. It will look like this:

class Solution:
   def find132pattern(self, nums):
      stack = []
      for num in nums:
         if not stack or num < stack[-1][0]:
             stack.append([num, num]) 
         else:
             mini = stack[-1][0]
             while stack and stack[-1][1] < num:
                stack.pop()
             if stack and stack[-1][0] < num and stack[-1][1] > num:
                return True
             else:
                stack.append([mini, num])
      return False

This line:

if not stack or num < stack[-1][0]:
   stack.append([num, num])

handles the case when we have a new small element. We store it as an interval that we will update afterwards.

Takeaways:

• Test cases are the best friend to dive more into the problem
• One of the trickiest part was inverting the order of the list to have a linear time solution. We managed to think about it when we noticed that we are only deleting the first elements.

Hope it helped !