C++ 10 lines O(n) Space and Time, 1 Pass and Done


  • 0
    F

    For a clearer but longer version, see next code;

    ///Ultra concise but NOT recommended;
    struct Solution {
        bool find132pattern(vector<int>& nums) {
            if (nums.size() < 3) return false;
            vector<int> mins(nums.size(), INT_MAX), lps(nums.size(), -1);
            for (int i = 1; i < nums.size(); ++ i)
            {
                for (mins[i] = min(mins[i - 1], nums[i - 1]), lps[i] = i - 1; lps[i] >= 0 && nums[lps[i]] <= nums[i];lps[i] = lps[lps[i]]);
                if (lps[i] != -1 && mins[lps[i]] < nums[i])
                    return true;
            }
            return false;
        }
    };
    
    class Solution {
    public:
        bool find132pattern(vector<int>& nums) {
            if (nums.size() < 3)
                return false;
            vector<int> mins(nums.size(), INT_MAX), last_max_poses(nums.size(), -1);
            for (int i = 1; i < nums.size(); ++ i)
            {
                mins[i] = min(mins[i - 1], nums[i - 1]);
                int j = i - 1;
                while (j >= 0 && nums[j] <= nums[i])
                    j = last_max_poses[j];
                last_max_poses[i] = j;
                if (j != -1 && mins[j] < nums[i])
                    return true;
            }
            return false;
        }
    };
    

Log in to reply
 

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