Easy to understand & accepted O(N^2) solution

  • 0
    class Solution {
        bool find132pattern(vector<int>& nums) {
            if(nums.size()<3) return false;
            int i=0;
            while(i<nums.size()) {
                // first result element is local minimum
                while((i+1)<nums.size() && nums[i]>=nums[i+1]) i++;
                if((i+3)>nums.size()) return false;
                int i1 = i;
                // second result element is local maximum
                while((i+1)<nums.size() && nums[i]<=nums[i+1]) i++;
                if((i+2)>nums.size()) return false;
                int i2 = i;
                // loop to find final result element
                for(int j=i+1;j<nums.size();j++) {
                    if(nums[j] < nums[i2] && nums[j] > nums[i1]) return true;
            return false;

Log in to reply

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