C ++ solution ,in O(n)


  • 2
    A

    For each index i , we will find out the closest index j to the left , such that the number in the index is greater than it , and see if there exists an index k for which the number at index k is less that the number at index i,
    we maintain an array dp , that stores the closes index to the left such that it is greater that the number at any index , building this dp array is O(n).

    class Solution {
    public:
        bool find132pattern(vector<int>& nums) {
            int i,j,k,n;
            n = nums.size();
            if(n<3)
                return false;
            vector<int> mn(nums.begin(),nums.end());
            for(i=1;i<n;i++)
                mn[i] = min(mn[i],mn[i-1]);
            int dp[n]{-1};
            for(i=0;i<n;i++)
                {
                    j = i-1;
                    while(j!= -1 && nums[j]<=nums[i])
                        j = dp[j];
                    dp[i] = j;
                }
            for(i=2;i<n;i++)
                {
                    j = dp[i];
                    if(j>0 && mn[j-1]<nums[i])
                        return true;
                }
            return false;
        }
    };
    

  • 0

    how can you guarantee the while loop runs in O(1)?


  • 0
    A

    @aedi , it does run on an average O(1) , it stops when you find a number to the left that is greater than it , some people used to do using a stack , i use array thats all ,for each element you are having a pointer to the element greater than it towards the left , we are using that fact ,instead of iterating the entire array backwards from that index.


  • 0

    running time is about the worse case right?


  • 1

    @arun42 Very nice solution. It seems to me that building DP array is indeed not O(n^2), probably O(n). At least I couldn't come up with an example when it would be quadratic. Do you have a proof that it is O(n)?


  • 0
    A

    @Uduse worst case is still linear only , try coming with examples , best thing is try lots of cases and you will know ir.


  • 0
    K

    @arun42 What's the run time for your submission? In milliseconds?


  • 0
    A

    @kdtree : 33 milliseconds

    0_1479378174141_upload-2a2693c6-d699-4e0f-a384-0ac1533a6c96


  • 1
    K

    @arun42 I have done it using TreeSet O(n*logn) Comes to 34 ms.


  • 0
    Z
    This post is deleted!

  • 1
    E

    I think the inner while loop is the same as KMP's failure function's inner loop, so the time complexity is O(n).


Log in to reply
 

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