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.
1public class Solution {
2 public boolean find132pattern(int[] nums) {
3 int n = nums.length;
4 for (int i = 0; i < n - 2; i++) {
5 for (int j = i + 1; j < n - 1; j++) {
6 for (int k = j + 1; k < n; k++) {
7 if (nums[i] < nums[k] && nums[k] < nums[j]) {
8 return true;
9 }
10 }
11 }
12 }
13 return false;
14 }
15}
16This Java solution employs triple nested loops to check for a 132 pattern among elements of the 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.
1using System;
2using 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;
}
}The stack stores elements greater than 'num3', representing possible '3' values. The algorithm iterates backwards to efficiently find '2' and '1'.