In this guide, you will get 456. 132 Pattern LeetCode Solution with the best time and space complexity. The solution to Pattern problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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.length
1 <= n <= 2 * 105
-109 <= nums[i] <= 109
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
456. 132 Pattern LeetCode Solution in C++
class Solution {
public:
bool find132pattern(vector<int>& nums) {
stack<int> stack; // a decreasing stack
int ak = INT_MIN; // Find a seq, where ai < ak < aj.
for (int i = nums.size() - 1; i >= 0; --i) {
// If ai < ak, done because ai must < aj.
if (nums[i] < ak)
return true;
while (!stack.empty() && stack.top() < nums[i])
ak = stack.top(), stack.pop();
stack.push(nums[i]); // `nums[i]` is a candidate of aj.
}
return false;
}
}; /* code provided by PROGIEZ */
456. 132 Pattern LeetCode Solution in Java
class Solution {
public boolean find132pattern(int[] nums) {
Deque<Integer> stack = new ArrayDeque<>(); // a decreasing stack
int ak = Integer.MIN_VALUE; // Find a seq, where ai < ak < aj.
for (int i = nums.length - 1; i >= 0; --i) {
// ai < ak, done because ai must < aj.
if (nums[i] < ak)
return true;
while (!stack.isEmpty() && stack.peek() < nums[i])
ak = stack.pop();
stack.push(nums[i]); // `nums[i]` is a candidate of aj.
}
return false;
}
} // code provided by PROGIEZ
456. 132 Pattern LeetCode Solution in Python
class Solution:
def find132pattern(self, nums: list[int]) -> bool:
stack = [] # a decreasing stack
ak = -math.inf # Find a seq, where ai < ak < aj.
for num in reversed(nums):
# If ai < ak, done because ai must < aj.
if num < ak:
return True
while stack and stack[-1] < num:
ak = stack[-1]
stack.pop()
stack.append(num) # `nums[i]` is a candidate of aj.
return False # code by PROGIEZ
