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.
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.
1defIterating over the reversed list, the stack is used to check the '132' pattern. The 'num3' variable tracks the most recent valid '2'.