# C++, use two arrays

• 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;
}
};
``````

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