Leetcode 456. 132 Pattern

Problem Explanation

Given a sequence of n integers, a "132 pattern" is a subsequence of 3 integers a[i], a[j], a[k], with i < j < k and a[i] < a[k] < a[j]. The task is to develop an algorithm that checks whether there is a 132 pattern in the input list.

For example, consider the sequence [6, 2, 3, 1, 4]. There is no 132 pattern in this sequence. However, in the sequence [3, 1, 4, 2], there does exist a 132 pattern, which is [1,4,2].

Algorithm Explanation

The solution applies a stack-based approach to check for the 132 pattern in the list. The stack will keep decreasing order numbers. The variable ak is the potential middle element of the 132 pattern.

The algorithm scans the list from right to left and for each element nums[i], checks if it is less than ak. If it is, it returns true, since there exists a 132 pattern. If not, it pops all the elements from the stack which are less than nums[i] and assigns the last popped element to ak, and then it pushes nums[i] into the stack.

Python Solution

1
2python
3class Solution:
4    def find132pattern(self, nums):
5        n = len(nums)
6        stack = []
7        ak = float('-inf')
8        for i in range(n-1, -1, -1):
9            if nums[i] < ak:
10                return True
11            while stack and stack[-1] < nums[i]:
12                ak = stack.pop()
13            stack.append(nums[i])
14        return False

Java Solution

1
2java
3import java.util.*;
4import java.lang.*;
5
6class Solution {
7    public boolean find132pattern(int[] nums) {
8        Stack < Integer > stack = new Stack < > ();
9        int ak = Integer.MIN_VALUE;
10        for (int i = nums.length - 1; i >= 0; i--) {
11            if (nums[i] < ak)
12                return true;
13            while (!stack.isEmpty() && stack.peek() < nums[i])
14                ak = stack.pop();
15            stack.push(nums[i]);
16        }
17        return false;
18    }
19}

JavaScript Solution

1
2javascript
3var find132pattern = function(nums) {
4    let ak = Number.MIN_SAFE_INTEGER;
5    let stack = [];
6    for(let i =nums.length - 1; i >=0; i--) {
7        if(nums[i] < ak) return true;
8        while(stack.length !=0 && stack[stack.length-1] < nums[i]) {
9            ak = stack.pop();
10        }
11        stack.push(nums[i]);
12    }
13    return false;
14};

C++ Solution

1
2cpp
3#include<stack>
4#include<vector>
5using namespace std;
6class Solution {
7public:
8    bool find132pattern(vector<int>& nums) {
9        stack<int> sts;
10        int ak = INT_MIN;
11        for(int i=nums.size()-1; i>=0; --i){
12            if(nums[i] < ak) return true;
13            while(!sts.empty() && sts.top() < nums[i]) {
14                ak = sts.top();
15                sts.pop();
16            }
17            sts.push(nums[i]);
18        }
19        return false;
20    }
21};

C# Solution

1
2csharp
3public class Solution {
4    public bool Find132pattern(int[] nums) {
5        Stack<int> stack = new Stack<int>();
6        int ak = int.MinValue;
7        for(int i = nums.Length - 1; i >= 0; --i) {
8            if(nums[i] < ak) return true;
9            while(stack.Count > 0 && stack.Peek() < nums[i]) {
10                ak = stack.Pop();
11            }
12            stack.Push(nums[i]);
13        }
14        
15        return false;
16    }
17}

In all above solutions, we scan the array from right to left and use a stack to keep track of numbers that might be a[j] and a[k] in the 132pattern and maintain the invariant that the elements in the stack are in descending order. We use ak to keep track of the maximum a[k] we've seen so far. If we find a number that is smaller than ak, we know we found a 1,3,2 pattern.Overall, the time complexity of this algorithm is O(n), where n is the length of the array. This is because we iterate through the list of numbers only once. The space complexity is also O(n), due to the usage of a stack to store potential values for a[k].

These solutions are applicable in almost any programming language that supports stack data structure and iteration over arrays. Understanding this problem includes mastering stack usage and array manipulation, which is essential for solving other algorithmic problems in computer science and coding interviews.

In conclusion, the key to finding the 132 pattern is to iterate through the array backwards while maintaining a stack of potential a[k]s. By continuously updating our potential a[k] with the highest value we find that is still smaller than our current a[j], we ensure that we are always looking for the smallest a[i] possible while still maintaining the condition that a[i] < a[k] < a[j].

Ultimately, this problem serves as a good introduction to the more general topic of subsequence problems; it is a common pattern to use data structures like stacks to store and compare elements in non-trivial ways. Mastering both the data structures and the problem-solving strategies involved in this pattern can enable you to tackle much more complex problems. So, keep practicing to improve your problem-solving skills!