Sponsored
Sponsored
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.
1function find132pattern(nums) {
2 for (let i = 0; i < nums.length - 2; i++) {
3 for (let j = i + 1; j < nums.length - 1; j++) {
4 for (let k = j + 1; k < nums.length; k++) {
5 if (nums[i] < nums[k] && nums[k] < nums[j]) {
6 return true;
7 }
8 }
9 }
10 }
11 return false;
12}
13The JavaScript solution uses three nested loops to exhaustively search for any 132 pattern in the given array.
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.
1#include <vector>
#include <stack>
#include <limits.h>
bool find132pattern(std::vector<int>& nums) {
std::stack<int> stk;
int num3 = INT_MIN;
for (int i = nums.size() - 1; i >= 0; --i) {
if (nums[i] < num3) {
return true;
}
while (!stk.empty() && nums[i] > stk.top()) {
num3 = stk.top();
stk.pop();
}
stk.push(nums[i]);
}
return false;
}By iterating backward, the stack keeps potential candidates for the most recent maximum '2'. The aim is to find a smaller element earlier to complete the '132' pattern.