By Long Luo

This article is the solution 4 Approaches: BF O(n^3), BF O(n^2), TreeMap, Monotonic Stack of Problem 456. 132 Pattern.

Here are 4 approaches to solve this problem in Java: BF \(O(n^3)\), BF \(O(n^2)\), TreeMap, Monotonic Stack.

BF O(n^3)

It’s easy to use 3 loops to find \(3\) elements which is \(132\) pattern, but the time complexity is \(O(n^3)\), so it wouldn’t accepted as TLE!

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(n^3)\).
• Space Complexity: \(O(1)\).

BF O(n^2)

Noticed that \(\textit{nums}[j]\) is the peak of the \(3\) elements, suppose the current element is \(\textit{nums}[j]\), we have to find the element \(\textit{nums}[k]\) that is smaller than \(\textit{nums}[j]\) after \(j\), and the element \(\textit{nums}[i]\) that is smaller than \(\textit{nums}[k]\) before \(j\).

1. Scan left from \(j\) to \(0\), \(0 \le i \lt j\), whether there is \(\textit{nums}[i] < \textit{nums}[j]\), update the mininum \(\textit{leftMin}\);

2. Scan right from \(j\) to the end, \(j + 1 \le k \lt len\), whether there is \(\textit{nums}[k] < \textit{nums}[j]\), update the maxinum \(\textit{rightMax}\);

3. If exists and \(\textit{leftMin} < \textit{rightMax}\), return true.

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(n^2)\).
• Space Complexity: \(O(1)\).

TreeMap

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

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

Then if \(\textit{nums}[k] < \textit{nums}[j]\), which means we have found the \(3\) elements of \(132\) 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)\).
• Space Complexity: \(O(n)\).

Monotonic Stack

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

The stack must store elements with a larger index and a smaller value than \(\textit{nums}[j]\).

The process is like this:

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

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

3. If this \(\textit{nums}[k]\) is larger than the \(\textit{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)\).
• Space Complexity: \(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. 😉😃💗