[LeetCode][456. 132 Pattern] 6 Approaches: BF O(n^3), BF O(n^2), TreeMap, Monotonic Stack

By Long Luo

This article is the solution of Problem 456. 132 Pattern.

Here are 6 approaches to solve this problem in Java.

BF O(n^3)

It’s easy to use 3 loops to find 33 elements which is 132132 pattern, but the time complexity is O(n3)O(n^3), so it wouldn’t accepted as timeout.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public boolean find132pattern_bf(int[] nums) {
int len = nums.length;
if (len < 3) {
return false;
}

for (int i = 0; i < len - 2; i++) {
for (int j = i + 1; j < len - 1; j++) {
for (int k = j + 1; k < len; k++) {
if (nums[i] < nums[k] && nums[k] < nums[j]) {
return true;
}
}
}
}

return false;
}

Analysis

  • Time Complexity: O(n3)O(n^3).
  • Space Complexity: O(1)O(1).

BF O(n^2)

Noticed that nums[j]nums[j] is the peak of the 33 elements, suppose the current element is nums[j]nums[j], we have to find the element nums[k]nums[k] that is smaller than nums[j]nums[j] after jj, and the element nums[i]nums[i] that is smaller than nums[k]nums[k] before jj.

  1. Scan left from jj to 00, 0<=i<j0 <= i < j, whether there is num[i]<nums[j]num[i] < nums[j], update the mininum leftMinleftMin;

  2. Scan right from jj to the end, j+1<=k<lenj + 1 <= k < len, whether there is num[k]<nums[j]num[k] < nums[j], update the maxinum rightMaxrightMax;

  3. If exists and leftMin<rightMaxleftMin < rightMax, return truetrue.

Let’s coding it.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public boolean find132pattern_bf_opt(int[] nums) {
int len = nums.length;
if (len < 3) {
return false;
}

for (int j = 1; j < len - 1; j++) {
int leftMin = Integer.MAX_VALUE;
boolean leftFlag = false;
for (int i = j - 1; i >= 0; i--) {
if (nums[i] < nums[j]) {
leftFlag = true;
leftMin = Math.min(leftMin, nums[i]);
}
}

int rightMax = Integer.MIN_VALUE;
boolean rightFlag = false;
for (int k = j + 1; k < len; k++) {
if (nums[k] < nums[j]) {
rightFlag = true;
rightMax = Math.max(rightMax, nums[k]);
}
}

if (leftFlag && rightFlag && leftMin < rightMax) {
return true;
}
}

return false;
}

Analysis

  • Time Complexity: O(n2)O(n^2).
  • Space Complexity: O(1)O(1).

TreeMap

Method 2 is O(n2)O(n^2). With extra O(n)O(n) space to store the elements of the array, we can reduce the time complexity to O(n)O(n).

We have to maintain all the values of the array in the right of jj. As we have determined nums[i]nums[i] and nums[j]nums[j], we only need to query the smallest element nums[k]nums[k] in the sorted set which is strictly larger than nums[i]nums[i].

Then if nums[k]<nums[j]nums[k] < nums[j], which means we have found the 33 elements of 132132 pattern.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public static boolean find132pattern_map(int[] nums) {
int len = nums.length;
if (len < 3) {
return false;
}

TreeMap<Integer, Integer> rightMap = new TreeMap<>();
for (int i = 2; i < len; i++) {
rightMap.put(nums[i], rightMap.getOrDefault(nums[i], 0) + 1);
}

int leftMin = nums[0];
for (int j = 1; j < len - 1; j++) {
if (leftMin < nums[j]) {
Integer numK = rightMap.ceilingKey(leftMin + 1);
if (numK != null && numK < nums[j]) {
return true;
}
}

leftMin = Math.min(leftMin, nums[j]);
rightMap.put(nums[j + 1], rightMap.get(nums[j + 1]) - 1);
if (rightMap.get(nums[j + 1]) == 0) {
rightMap.remove(nums[j + 1]);
}
}

return false;
}

Analysis

  • Time Complexity: O(nlogn)O(nlogn).
  • Space Complexity: O(n)O(n).

Monotonic Stack

We can use a stack to store the element of the array from the back to front, find nums[k]nums[k] in the stack, and then continue to scan forward to find nums[i]nums[i].

The stack must store elements with a larger index and a smaller value than nums[j]nums[j].

The process is like this:

  1. Scanning from the back to the front, if the current element nums[i]nums[i] is larger than the top of the stack, which means nums[i]nums[i] may be the nums[j]nums[j] we are looking for;

  2. Pop all the elements in the stack that are smaller than it. These elements are the the nums[k]nums[k], and the last pop-up is the maximum qualified nums[k]nums[k].

  3. If this num[k]num[k] is larger than the nums[i]nums[i] scanned forward, we find the answer.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public boolean find132pattern_stack(int[] nums) {
int len = nums.length;
if (len < 3) {
return false;
}

Deque<Integer> stk = new ArrayDeque<>();
int k = -1;
for (int i = len - 1; i >= 0; i--) {
if (k > -1 && nums[k] > nums[i]) {
return true;
}

while (!stk.isEmpty() && nums[i] > nums[stk.peek()]) {
k = stk.pop();
}

stk.push(i);
}

return false;
}

Analysis

  • Time Complexity: O(n)O(n).
  • Space Complexity: O(n)O(n).

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗