Given an array of n integers nums, a 132 pattern is a subsequence of three integers nums[i], nums[j] and nums[k] such that i < j < k and nums[i] < nums[k] < nums[j].
Return true if there is a 132 pattern in nums, otherwise, return false.
Example 1:
Input: nums = [1,2,3,4] Output: false Explanation: There is no 132 pattern in the sequence.
Example 2:
Input: nums = [3,1,4,2] Output: true Explanation: There is a 132 pattern in the sequence: [1, 4, 2].
Example 3:
Input: nums = [-1,3,2,0] Output: true Explanation: There are three 132 patterns in the sequence: [-1, 3, 2], [-1, 3, 0] and [-1, 2, 0].
Constraints:
n == nums.length1 <= n <= 2 * 105-109 <= nums[i] <= 109This approach checks all possible triples (i, j, k) to determine if they form a 132 pattern. While straightforward, its complexity can be high for larger arrays due to the triple nested loop structure.
The code iterates over all possible triplets to check if the condition nums[i] < nums[k] < nums[j] holds. If such a triplet is found, it returns true. Otherwise, after all checks, it returns false.
C++
Java
Python
C#
JavaScript
Time complexity: O(n^3) because of the three nested loops.
Space complexity: O(1) since no additional data structures are used.
This approach uses a clever stack-based strategy by scanning the array from right to left. It keeps track of potential '2' and '3' candidates using a stack and a variable, optimizing the search for the '132' pattern.
Iterate from the end of the array to the beginning. The stack is used to keep track of elements greater than a possible '2' in the pattern. 'num3' holds the maximum candidate for '2'.
C++
Java
Python
C#
JavaScript
Time complexity: O(n) because each element is pushed and popped once.
Space complexity: O(n) for the stack.
| Approach | Complexity |
|---|---|
| Approach 1: Brute Force | Time complexity: O(n^3) because of the three nested loops. |
| Approach 2: Stack Optimization | Time complexity: O(n) because each element is pushed and popped once. |
132 Pattern - Leetcode 456 - Python • NeetCode • 68,601 views views
Watch 9 more video solutions →Practice 132 Pattern with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor