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

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!

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.

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.

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.

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. 😉😃💗