Evolve from brute force to optimal


  • 0
    1. O(n^3), try all triplets
        bool find132pattern(vector<int>& nums) {
            int n = nums.size();
            for(int i=0;i<n-2;i++)
                for(int j=i+1;j<n-1;j++) {
                    if(nums[j]-nums[i]<=1) continue;
                    for(int k=j+1;k<n;k++) 
                        if(nums[i]<nums[k] && nums[k]<nums[j]) return 1;
                }
            return 0;
        }
    
    1. O(n^2), 3 and 2 can be tried in one pass. For each 1, we cache the current max as 3.
        bool find132pattern(vector<int>& nums) {
            int n = nums.size();
            for(int i=0;i<n-2;i++) {
                int three = nums[i];
                for(int j=i+1;j<n;j++)
                    if(nums[j] > three) three = nums[j];
                    else if(nums[j] < three && nums[i]<nums[j]) return 1;
            }
            return 0;
        }
    
    1. O(nlongn), instead of trying in the order of i, j, k as above, we can try each j and see if we have a valid i on the left and a valid k on the right. When checking for a valid k, we only need to check the next number of aj in descending order. And bst fits here.
        bool find132pattern(vector<int>& nums) {
            int n = nums.size();
            if(n<3) return 0;
            int mi = nums[0];
            vector<int> left(n);
            for(int i=1;i<n-1;i++) {
                left[i] = mi;
                mi = min(nums[i],mi);
            }
            set<int,greater<int>> bst{nums.back()};
            for(int i=n-1;i>0;i--) {
                if(nums[i] > left[i] + 1) {
                    auto right = bst.upper_bound(nums[i]);
                    if (right != bst.end() && *right > left[i]) return 1;
                }
                bst.insert(nums[i]);
            }
            return 0;
        }
    
    1. O(n), similar to #3, we can use a stack to cache all the numbers on the right of j and checking can be done in constant time.
      When visiting nums from end to beginning, left[j] increases, so it is sufficient to check if a number is a valid k the first time we see a j larger than it. The numbers in the stack is always ascending from top to bottom.
        bool find132pattern(vector<int>& nums) {
            int n = nums.size();
            if(n<3) return 0;
            int mi = nums[0];
            vector<int> left(n);
            for(int i=1;i<n-1;i++) {
                left[i] = mi;
                mi = min(nums[i],mi);
            }
            stack<int> stk({nums.back()});
            for(int i=n-1;i>0;i--) {
                if(nums[i] > left[i] + 1)
                    while(!stk.empty() && nums[i]>stk.top()) {
                        if (stk.top() > left[i]) return 1;
                        stk.pop();
                    }
                stk.push(nums[i]);
            }
            return 0;
        }
    

Log in to reply
 

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