Clean c++ O(n) solution


  • 0
    1. traverse from end to front
    2. find and update available s2
    3. once we find an element that is smaller than saved s2, we are done
    bool find132pattern(vector<int>& nums) {
        int size = nums.size(), s2 = INT_MIN;
        stack<int> seconds;
        for (int i = size - 1; i >= 0; i--) {
            if (nums[i] < s2)
                return true;
            while (seconds.size() && nums[i] > seconds.top()) {
                s2 = seconds.top();
                seconds.pop();
            }
            if (nums[i] > s2)
                seconds.push(nums[i]);
        }
        return false;
    }
    

Log in to reply
 

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