C++, use two arrays


  • 0
    T
    • idx_i[i] : the index of the minimum in subarray nums[0,...,i]
    • idx_j[i] : the index of the first element(from right to left) in subarray nums[0...i - 1] that is larger than nums[i]
    • if there is nums[i] that satisfy nums[i] > nums[idx_i[idx_j[i]]], return true;

    I am not sure about the time complexity. Any thoughts on this?

    class Solution {
    public:
        bool find132pattern(vector<int>& nums) {
            int n = nums.size();
            if (n < 3) return false;
            vector<int> idx_i(n , -1), idx_j(n, -1);
            for (int i = 1, j, k = 0; i < n; ++i) {
                idx_i[i] = k;
                if (nums[i] < nums[k])
                    k = i; //update the minimum
    
                if (nums[i] < nums[i - 1])
                    idx_j[i] = i - 1;
                else {
                    j = i - 1;
                    while (j >= 0 && idx_j[j] >= 0 && nums[idx_j[j]] <= nums[i]) j = idx_j[j];
                    idx_j[i] = j >= 0 ? idx_j[j] : j;
                }
                if (idx_j[i] >= 0 && idx_i[idx_j[i]] >= 0 && nums[idx_i[idx_j[i]]] < 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.