[LC 456]. 132 Pattern

Given a sequence of n integers a1, a2, …, an, a 132 pattern is a subsequence ai, aj, ak such that i < j < k and ai < ak < aj. Design an algorithm that takes a list of n numbers as input and checks whether there is a 132 pattern in the list. Note: n will be less than 15,000. Example: Input: [-1, 3, 2, 0] Output: True Explanation: There are three 132 patterns in the sequence: [-1, 3, 2], [-1, 3, 0] and [-1, 2, 0].

Example [9, 11, 8, 9, 10]

Step 1 — stack is empty, save pair (9,9)

Step 2 — 11 > stack.peek().min, last pair = stack.pop(), 11 > last.max, last = (9,11), stack is empty, save pair (9,11)

Step 3 — 8 < stack.peek().min, save (8,8)

Step 4 — 9 > stack.peek().min, last = stack.pop(), 9 > last.max, last = (8,9) and does not cover or overlap with stack.peek(), which is (9,11), save (8,9). Stack is now [(9,11), (8,9)]

Step 5 — 10 > stack.peek().min, last = (8,9), 10 > last.max, last = (8,10) and does not cover stack.peek(), which is (9,11). But 10 is in (9,11), return true.

public class Solution {
    public boolean find132pattern(int[] nums) {
        Stack<Pair> stack = new Stack();
        for (int n : nums) {
            if (stack.isEmpty() || n < stack.peek().min) {                 stack.push(new Pair(n,n));             } else if (n > stack.peek().min) {
                Pair last = stack.pop();
                if (n < last.max) return true;
                else {
                    last.max = n;
                    while (!stack.isEmpty() && last.min <= stack.peek().min && last.max >= stack.peek().max) stack.pop(); // cover previous pair
                    if (!stack.isEmpty() && last.max < stack.peek().max && last.max > stack.peek().min) return true; // overlap with previous pair
                    stack.push(last);
                }
            }
        }

        return false;
    }
}
class Pair {
    int min;
    int max;
    public Pair(int min, int max) {
        this.min = min;
        this.max = max;
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s