456. 132 Pattern

MediumStackArrayBinary SearchOrdered SetMonotonic Stack
Leetcode Link

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.

  1. 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.

  2. Then, create an empty list stk which will act as a stack to store potential candidates for nums[j].

  3. 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].

  4. 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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

How does quick sort divide the problem into subproblems?

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:

  1. 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.

  2. An empty list stk is then created to function as our stack, which will store the potential candidates for the nums[j] values.

  3. The array nums is iterated in reverse order using for x in nums[::-1]:. Here, x acts as a candidate for our nums[i].

  4. 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.

  5. 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).

  6. 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.

  7. 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.

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

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

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.

  1. Initialize vk to negative infinity since we haven't yet begun iterating over nums.
  2. 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
Not Sure What to Study? Take the 2-min Quiz๏ผš

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

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.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following uses divide and conquer strategy?

Recommended Readings

Stack Intro

Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you

Binary Search Speedrun

Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at

Monotonic Stack/Queue Intro

Monotonic Stack Deque Intro If you'd prefer a video iframe width 560 height 315 src https www youtube com embed Dq_ObZwTY_Q title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe The word monotonic means a list or a

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ