Java solution using TreeSet. Easy to understand.


  • 0
    K

    Traverse from 1 to n-2 to build dp[], which dp[i] store the min value before nums[i].
    Then traverse from n-2 to 1 and build a TreeSet to check if there exists one or more values between dp[i] and nums[i]. Time complexity is O(nlogn).

    public boolean find132pattern(int[] nums) {
            if(nums.length<3) return false;
            int len=nums.length;
            int[] dp=new int[len];
            dp[1]=nums[0];
            for(int i=2;i<len-1;i++){
                dp[i]=Math.min(dp[i-1],nums[i-1]);
            }
            TreeSet<Integer> set=new TreeSet<Integer>();
            set.add(nums[len-1]);
            for(int i=len-2;i>=1;i--){
                set.add(nums[i]);
                if(dp[i]>=nums[i]) continue;
                else{
                    if(set.higher(dp[i])==nums[i]) continue;
                    else return true;
                }
            }
            return false;
    }
    

Log in to reply
 

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