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.
1#include <stdbool.h>
2int has132Pattern(int* nums, int numsSize) {
3 for (int i = 0; i < numsSize - 2; ++i) {
4 for (int j = i + 1; j < numsSize - 1; ++j) {
5 for (int k = j + 1; k < numsSize; ++k) {
6 if (nums[i] < nums[k] && nums[k] < nums[j]) {
7 return true;
8 }
9 }
10 }
11 }
12 return false;
13}
14The 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.
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.
1function find132patternWith reverse traversal, the stack acts as a meter for potential '3', holding values descending from 'num3'. Successful '1' discovery confirms a '132' pattern.