456. 132 Pattern

MediumStackArrayBinary SearchOrdered SetMonotonic Stack

Problem Description

The problem requires us to check if there is a specific pattern, called the "132 pattern", within an array of integers, nums. This pattern is defined by finding three numbers in the sequence that can be indexed with i, j, and k such that i < j < k. These three numbers must satisfy the criteria that nums[i] < nums[k] < nums[j].

In other words, amongst the three numbers forming this subsequence pattern, the first number should be the smallest and the last number should be in the middle—not as high as the second number but higher than the first. This pattern does not need to be consecutive but must maintain the order.

The objective is to return true if at least one occurrence of the "132 pattern" is found in the given array, and false otherwise.

Intuition

The solution exploits the property of a stack data structure to keep track of potential candidates for nums[k] and nums[j] from right to left.

Initialize a variable vk as negative infinity to represent a potential candidate for nums[k] which is the middle element in our "132 pattern". We initially set it to negative infinity because we're looking for a value that is greater than the smallest value found so far as we scan the array from right to left.
Then, create an empty list stk which will act as a stack to store potential candidates for nums[j].
Reverse iterate over the array. For each element x (acting as nums[i]):
- First, check if x is less than vk. If so, we have found a valid "132 pattern" because we have ensured earlier that any value in vk must be greater than the smallest value found and less than some value that came after it (acting as nums[j]). Therefore, we return true.
- If not, then we pop elements from stk which are less than x and update vk with those values. The popping continues until we find an element greater than or equal to x or until stk is empty. This ensures that vk is always the greatest possible value just smaller than our current nums[j] candidate (the top of the stack) while being greater than the smallest value found so far.
- Finally, push x onto the stk to consider it for the future nums[j].
If the loop completes without finding the "132 pattern", return false.

This approach effectively finds the "132 pattern" by ensuring that for any given element, if it is a potential candidate for nums[i], there is an already established candidate for nums[k] (vk) which is less than a potential candidate for nums[j] (top of the stack) and greater than the nums[i]. By scanning from right to left, we are efficiently maintaining candidates for nums[j] and nums[k] while looking for a valid nums[i].

Learn more about Stack, Binary Search and Monotonic Stack patterns.

Solution Approach

The implementation of the solution utilizes a stack data structure for its ability to operate in a last-in-first-out manner. This approach allows us to keep track of potential nums[j] elements and efficiently update the candidate for nums[k].

The algorithm follows these steps:

We start by initializing a variable vk to negative infinity (-inf). This variable will hold the potential candidate for the middle value nums[k] in the "132 pattern" as we traverse through the array.
An empty list stk is then created to function as our stack, which will store the potential candidates for the nums[j] values.
The array nums is iterated in reverse order using for x in nums[::-1]:. Here, x acts as a candidate for our nums[i].
Inside the loop, we perform a check: if x < vk: return True. This is the condition that confirms the presence of the "132 pattern". Since vk is always chosen to be less than a previously encountered element (which would be nums[j]), finding an x that is even lesser confirms our sequence.
If the current element x doesn't validate the pattern, we handle the stack stk. With while stk and stk[-1] < x:, we pop elements from the stack that are less than x, updating vk to stk.pop(). Each popped value is a new candidate for nums[k] since it satisfies both being less than our nums[j] (which x could potentially be) and greater than the smallest element encountered (since it was added to the stack after that element).
After the above operation, regardless of whether we popped from the stack or not, we append the current element x to the stack with stk.append(x). This step considers x for a future nums[j] candidate.
If the entire array is traversed without returning True, the function concludes with return False, indicating that no "132 pattern" was found.

The elegance in this solution lies in the efficiency with which it maintains the candidates for nums[j] and nums[k], thus drastically reducing the time complexity compared to a naive triple-nested loop approach which would check all possible combinations of i, j, and k.

Thanks to the stack, we keep the order of elements in such a way that at any given moment, the top of the stack (stk[-1]) is our best guess for nums[j], and vk is our best guess for nums[k]. This method ensures that we never miss a valid pattern and negate the need to check every possible subsequence explicitly.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider the array nums = [3, 1, 4, 2] and walk through the solution approach to determine if a "132 pattern" exists.

Initialize vk to negative infinity since we haven't yet begun iterating over nums.
Create an empty stack stk to store potential candidates for nums[j].

Now, we iterate over nums in reverse:

Start with x = 2 (nums[k]). Push x onto stk, vk is unchanged. Stack stk = [2].
Next, x = 4 (nums[j]). Since stk is not empty and 2 < 4, pop 2 from stk and update vk to 2. Now stk = [] and vk = 2. Push 4 onto stk, stk becomes [4].
Then, x = 1 (nums[i]). Check if x < vk. It is not since 1 < 2 is false, so we push 1 to stk, which becomes [4, 1].
Lastly, x = 3 (nums[i]). Check if 3 < vk (2). It is false. Pop 1 from stk as long as 1 < 3. Update vk to 1. Now we check again if x < vk. Since 3 < 4 is true and vk(1) < x(3) is also true, we have found our "132" pattern where nums[i] = 1, nums[k] = 3, and nums[j] = 4.

Because we successfully found a "132" pattern, we can return true.

This example demonstrates how the stack and the vk variable are updated throughout the process while confirming the pattern as soon as the conditions are met without having to finish iterating through the entire array. This makes the approach efficient and effective at identifying the presence of a "132 pattern".

Solution Implementation

1class Solution:
2    def find132pattern(self, nums: List[int]) -> bool:
3        # Initialize the third value in the pattern to negative infinity
4        third_value = float('-inf')
5        # Initialize an empty stack to store elements of the nums list
6        stack = []
7        # Traverse the nums list in reverse order
8        for number in reversed(nums):
9            # If the current number is less than the third_value, a 132 pattern is found
10            if number < third_value:
11                return True
12            # While there's an element in the stack and it's less than the current number
13            while stack and stack[-1] < number:
14                # Update the third_value to the last element in the stack
15                third_value = stack.pop()
16            # Push the current number onto the stack
17            stack.append(number)
18        # Return False if no 132 pattern is found
19        return False
20

1class Solution {
2    public boolean find132pattern(int[] nums) {
3        // Initialize vk with the smallest possible integer value using bitwise shift
4        int potentialMidVal = Integer.MIN_VALUE;
5        Deque<Integer> stack = new ArrayDeque<>(); // Create a stack to store the elements
6
7        // Iterate from the end to the start of the array
8        for (int i = nums.length - 1; i >= 0; --i) {
9            // If the current element is less than the potential middle value of the 132 pattern,
10            // this means we have found a 132 pattern.
11            if (nums[i] < potentialMidVal) {
12                return true;
13            }
14            // While the stack is not empty and the top element is less than the current number,
15            // update the potential middle value to be the new top of the stack
16            while (!stack.isEmpty() && stack.peek() < nums[i]) {
17                potentialMidVal = stack.pop();
18            }
19            // Push the current number onto the stack
20            stack.push(nums[i]);
21        }
22        // If the loop completes without finding a 132 pattern, return false
23        return false;
24    }
25}
26

1#include <vector>
2#include <stack>
3#include <climits>
4
5class Solution {
6public:
7    // This function checks if there is a 132 pattern in the input vector "nums".
8    // A 132 pattern is a subsequence of three integers where the first is smaller than the third and both are smaller than the second.
9    bool find132pattern(vector<int>& nums) {
10        // Initialize the variable to hold the value of the third element in the 132 pattern, initialized to the minimum integer value.
11        int thirdValue = INT_MIN;
12      
13        // Use a stack to help find potential candidates for the second element in the 132 pattern.
14        stack<int> candidates;
15      
16        // Iterate through the input array backwards.
17        for (int i = nums.size() - 1; i >= 0; --i) {
18            // Check if we have achieved the 132 pattern
19            if (nums[i] < thirdValue) {
20                // we found a valid 132 pattern
21                return true;
22            }
23            // While we have candidates and the current number is greater than the candidate at the top of the stack
24            while (!candidates.empty() && candidates.top() < nums[i]) {
25                // The candidate could potentially be the third value in the pattern, so we update the thirdValue.
26                thirdValue = candidates.top();
27                candidates.pop(); // Remove the candidate as it has been used
28            }
29            // Push the current number onto the stack to be a candidate for the second position in the 132 pattern.
30            candidates.push(nums[i]);
31        }
32      
33        // If we reach this point, no 132 pattern has been found.
34        return false;
35    }
36};
37

1function find132pattern(nums: number[]): boolean {
2    // Initialize the variable to represent the 'k' element of the 132 pattern and set it to negative infinity.
3    let patternK = -Infinity;
4
5    // Initialize an empty stack to use as an auxiliary data structure.
6    const stack: number[] = [];
7
8    // Iterate through the given array from the end towards the beginning.
9    for (let i = nums.length - 1; i >= 0; --i) {
10        // If the current element is smaller than the 'k' element of the pattern, a 132 pattern is found.
11        if (nums[i] < patternK) {
12            return true;
13        }
14
15        // While there are elements on the stack and the top of the stack is smaller than the current element,
16        // update the 'k' element with the values popped from the stack.
17        while (stack.length && stack[stack.length - 1] < nums[i]) {
18            patternK = stack.pop()!;
19        }
20
21        // Push the current element onto the stack.
22        stack.push(nums[i]);
23    }
24
25    // If no 132 pattern is found, return false.
26    return false;
27}
28

Time and Space Complexity

Time Complexity

The given algorithm iterates through the input array nums once in reverse order. The outer loop has a worst-case scenario of O(n) where n is the length of nums. For each element, the algorithm performs operations involving a stack stk. In the worst case, for each element of the array, the algorithm might push and pop on the order of O(n) times collectively over the entire run of the algorithm due to the nature of maintaining a stack for the pattern. However, an important property of the stack operations is that each element is pushed and popped at most once, leading to amortized O(1) time per element. Therefore, the total time complexity of the algorithm is O(n).

Space Complexity

The space complexity of the algorithm is determined by the additional space used by the stack stk. In the worst case, the stack could grow to have all elements of nums if the array is strictly decreasing, leading to a space complexity of O(n). Otherwise, the stack will contain fewer elements. So the worst-case space complexity is O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Optimal substructure

Overlapping subproblems

Non-overlapping subproblems

Constant time subproblems