Single pass C++ O(n) space and time solution (8 lines) with detailed explanation.


  • 87
    J

    QUESTION: To search for a subsequence (s1,s2,s3) such that s1 < s3 < s2.

    INTUITION: Suppose we want to find a 123 sequence with s1 < s2 < s3, we just need to find s3, followed by s2 and s1. Now if we want to find a 132 sequence with s1 < s3 < s2, we need to switch up the order of searching. we want to first find s2, followed by s3, then s1.

    DETECTION: More precisely, we keep track of highest value of s3 for each valid (s2 > s3) pair while searching for a valid s1 candidate to the left. Once we encounter any number on the left that is smaller than the largest s3 we have seen so far, we know we found a valid sequence, since s1 < s3 implies s1 < s2.

    ALGORITHM: We can start from either side but I think starting from the right allow us to finish in a single pass. The idea is to start from end and search for valid (s2,s3) pairs, we just need to remember the largest valid s3 value, using a stack will be effective for this purpose. A number becomes a candidate for s3 if there is any number on the left bigger than it.

    CORRECTNESS: As we scan from right to left, we can easily keep track of the largest s3 value of all (s2,s3) candidates encountered so far. Hence, each time we compare nums[i] with the largest candidate for s3 within the interval nums[i+1]...nums[n-1] we are effectively asking the question: Is there any 132 sequence with s1 = nums[i]? Therefore, if the function returns false, there must be no 132 sequence.

    IMPLEMENTATION:

    1. Have a stack, each time we store a new number, we first pop out all numbers that are smaller than that number. The numbers that are popped out becomes candidate for s3.
    2. We keep track of the maximum of such s3 (which is always the most recently popped number from the stack).
    3. Once we encounter any number smaller than s3, we know we found a valid sequence since s1 < s3 implies s1 < s2.

    RUNTIME: Each item is pushed and popped once at most, the time complexity is therefore O(n).

    EXAMPLE:
    i = 6, nums = [ 9, 11, 8, 9, 10, 7, 9 ], S1 candidate = 9, S3 candidate = None, Stack = Empty
    i = 5, nums = [ 9, 11, 8, 9, 10, 7, 9 ], S1 candidate = 7, S3 candidate = None, Stack = [9]
    i = 4, nums = [ 9, 11, 8, 9, 10, 7, 9 ], S1 candidate = 10, S3 candidate = None, Stack = [9,7]
    i = 3, nums = [ 9, 11, 8, 9, 10, 7, 9 ], S1 candidate = 9, S3 candidate = 9, Stack = [10]
    i = 2, nums = [ 9, 11, 8, 9, 10, 7, 9 ], S1 candidate = 8, S3 candidate = 9, Stack = [10,9] We have 8<9, sequence (8,10,9) found!

    EDIT: Thanks @Pumpkin78 and @dalwise for pointing out that the maximum candidate for s3 is always the recently popped number from the stack, because if we encounter any entry smaller than the current candidate, the function would already have returned.
    EDIT 2: Rephrased explanations and added a sketch of the correctness proof.

        bool find132pattern(vector<int>& nums) {
            int s3 = INT_MIN;
            stack<int> st;
            for( int i = nums.size()-1; i >= 0; i -- ){
                if( nums[i] < s3 ) return true;
                else while( !st.empty() && nums[i] > st.top() ){ 
                  s3 = st.top(); st.pop(); 
                }
                st.push(nums[i]);
            }
            return false;
        }
    

  • 3
    K

    Brilliant solution.


  • -1
    W

    Nice Answer!
    I wrote a Java version, just 5 lines

    public boolean find132pattern(int[] nums) {
        Stack<Integer> stack = new Stack<>();
        for (int i = nums.length - 1, two = Integer.MIN_VALUE; i >= 0; stack.push(nums[i--]))
            if (nums[i] < two) return true;
            else for (; !stack.empty() && nums[i] > stack.peek(); two = Math.max(two, stack.pop()));
        return false;
    }

  • 3
    P

    Great solution. I realized that s3 (or k) should be actually the top of the stack since this stack is tracking all s3 (k) candidates.
    I wrote it in Python here:

    def find132pattern(self, nums):
            k_stack = [- sys.maxint - 1]
            for l in range(len(nums)-1, -1, -1):
                if nums[l] < k_stack[-1]: return True
                else:
                    while k_stack and nums[l] > k_stack[-1]:  v = k_stack.pop()
                    k_stack.append(nums[l])
                    k_stack.append(v)
            return False
    

  • 0
    T

    very beautiful!!


  • 4

    @Pumpkin78 You do not need to push e3 back on to the stack. Here is a shorter version:

    def find132pattern(self, nums):
        e3, st = float('-inf'), []
        for e in reversed(nums):
            if e < e3: return True
            while st and e > st[-1]: e3 = st.pop()
            st.append(e)
        return False
    

  • 0
    J

    @dalwise Nice observation! I have added your suggestion to the code.


  • 0
    J

    @Pumpkin78 Good point!


  • 0
    M

    @wit : Nice. you could use ArrayDeque instead of Stack which is deprecated.


  • 0
    This post is deleted!

  • 0
    D

    Nice solution! For the syntax "else while", is this a new thing from the latest C++?


  • 5
    Y

    You also can just leverage the input array to simulate a stack, so no extra space is required:

        public boolean find132pattern(int[] nums) {
            int two = Integer.MIN_VALUE;
            int index = nums.length;
            for (int i=nums.length-1; i>=0; i--) {
                if (nums[i] < two) return true;
                while (index < nums.length && nums[i] > nums[index]) {
                    two = nums[index++];
                }
                nums[--index] = nums[i];
            }
            return false;
        }
    

  • 0
    J

    @ye23 good point!


  • 0

    What if 8, 10, 5, 6, 7, 8, 9, the inner while loop will pop() n-2 times, and the time complexity should be O(n^2).

    So I think the worst time complexity is O(n^2), did I miss something?


  • 0
    Y

    @zhugejunwei Each num can be at most poshed and popped once, the inner while loop will pop n-2 times only if n-2 items are pushed, and later pop cannot pop these n-2 items again since they are gone, so it is O(2n) but not O(n^2)


  • 2

    @DragonJ said in Single pass C++ O(n) space and time solution (8 lines) with detailed explanation.:

    Nice solution! For the syntax "else while", is this a new thing from the latest C++?

    Actually, else while is not a new syntax for C++. It was just written in the same line. C++ uses curly brackets {} as the delimiter to separate "logic blocks". However, the convenience is that if a "logic block" contains only a single statement, the delimiter {} can be dropped (which is an intuitive convention in my opinion).

    For example, the following two lines are equivalent:

    if (A == 1) { f1(); f2(); }
    if (A == 1) f1(), f2();
    

    Note that , operator makes f1(), f2() as a single statement, so no {} is needed. Just like in the code where the while loop itself is a single statement. The original code could be made more compact as

        bool find132pattern(vector<int>& a) {
            stack<int> st;
            for(int i = a.size()-1, s3 = INT_MIN; i >= 0; st.push(a[i--]))
                if( a[i] < s3 ) return true;
                else while(!st.empty() && a[i] > st.top()) s3 = st.top(), st.pop();
            return false;
        }
    

  • 1
    M

    Brilliant idea! Neat and efficient.

    I think the key points are:

    1. keep the value of s3 as big as possible
    2. use a "sorted" stack to maintain the candidates of s2 and s3.

    The numbers inside the stack are s2 and the number that popped out is the maximum s3. So the last thing to do is to maintain the order of the stack.


  • 1
    C

    I've struggled with this problem for two days...
    Finally, I get this idea. This is so cool solution.
    FYI, S3 here is actually the mid value. S2 is the high value.


  • 1
    F

    I think you need to prove the following thing is correct for this algorithm correctness.
    how to make sure the max value nums[j] always is stored in s3 when you check nums[i], where nums[j] < nums[k], j,k both > i.

    If you always store this max value in s3 when you check every nums[i], you can find out the solution.

    I almost can prove it but can't strictly prove it.

    Anyway, I think this algorithm is hard.

    Appreciate someone can prove this.


  • 0
    B
    This post is deleted!

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.