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] <= 109The 132 Pattern problem asks whether there exists a subsequence nums[i] < nums[k] < nums[j] with i < j < k. A brute-force approach checks all triplets, but this leads to O(n^3) time and is impractical for large inputs. Instead, the key is to efficiently track possible candidates for the "1", "3", and "2" values.
A popular strategy uses a monotonic stack while scanning the array from right to left. The stack helps maintain potential "3" values while a variable tracks the best candidate for the "2" in the pattern. By ensuring the stack remains decreasing, we can quickly determine whether the current number can act as the "1" in a valid pattern.
Another conceptual approach uses ordered sets or binary search structures to maintain valid ranges for the middle value. However, the monotonic stack method is typically preferred due to its linear time complexity. With careful state tracking, the pattern can be detected in O(n) time with O(n) additional space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Monotonic Stack (Right-to-Left Scan) | O(n) | O(n) |
| Ordered Set / Binary Search Structure | O(n log n) | O(n) |
NeetCode
This 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.
Time complexity: O(n^3) because of the three nested loops.
Space complexity: O(1) since no additional data structures are used.
1def find132pattern(nums):
2 for i in range(len(nums) - 2):
3 for j in range(i + 1, len(nums) - 1):
4 for k in range(j + 1, len(nums)):
5 if nums[i] < nums[k] < nums[j]:
6 return True
7 return False
8This Python solution examines all potential triplets via triple nested loops and checks if they fulfill the 132 pattern.
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.
Time complexity: O(n) because each element is pushed and popped once.
Space complexity: O(n) for the stack.
1using System;
using System.Collections.Generic;
public class Solution {
public bool Find132pattern(int[] nums) {
Stack<int> stack = new Stack<int>();
int num3 = int.MinValue;
for (int i = nums.Length - 1; i >= 0; --i) {
if (nums[i] < num3) {
return true;
}
while (stack.Count > 0 && nums[i] > stack.Peek()) {
num3 = stack.Pop();
}
stack.Push(nums[i]);
}
return false;
}
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, the 132 Pattern problem or its variations are common in technical interviews at top tech companies. It tests understanding of stacks, array traversal strategies, and pattern detection in sequences.
The optimal approach uses a monotonic stack while scanning the array from right to left. This method efficiently tracks potential candidates for the 132 sequence and detects the pattern in linear time. It avoids checking every triplet by maintaining useful state information.
Yes, it can also be solved using ordered sets or balanced binary search trees. These structures help track possible middle values and search efficiently, but they usually result in O(n log n) time complexity, which is slower than the stack-based approach.
A monotonic stack is the most effective data structure for this problem. It helps maintain decreasing elements that can represent the '3' in the pattern while tracking a candidate for the '2'. This structure enables efficient pattern detection in O(n) time.
The stack stores elements greater than 'num3', representing possible '3' values. The algorithm iterates backwards to efficiently find '2' and '1'.