This solution is quite intuitive. It is inspired by jade86's solution. Thanks a lot!

Since we want to find the three elements where `ai < ak < aj`

and `i < j < k`

, we can find the valid `ak`

in the array first and then find the valid `ai`

which is smaller than `ak`

. We can search the array from right to left with one pass. I'll explan it with the following example.

**Input:** [1, 2, 3, 4, 1, 2, 4, 1]

**Output:** True

**Explanation:**

We always find `ak`

in part of array which consist of a large enough element followed by ascending order sequence. I use `low`

to record the first element value in the ascending sequence and `left`

as position while use `high`

to record the last element value and `right`

as position in my code.

First time we search the colored part and get `aj = 4, ak = 1`

. `left = 7, right = 7`

.

[1, 2, 3, 4, 1, 2, `4, 1`

]

Second time we search the colored part and get `aj = 4, ak = 2`

. Since this `ak`

is larger than last one, we update `ak`

. We can use binary search to find `ak`

with `O(logn)`

time complexity. `left = 4, right = 6`

.

[1, 2, 3, `4, 1, 2, 4,`

1]

Second time we search the colored part and we can find valid `ai`

where `ai < ak`

.

[`1, 2, 3, 4,`

1, 2, 4, 1]

The overall time complexity is `O(nlogn)`

while the space complexity is `O(1)`

. Without stack this solution is quite fast and beats 98% solutions.

```
public class Solution {
public boolean find132pattern(int[] nums) {
if (nums.length < 3) return false;
int aj = Integer.MIN_VALUE, ak = Integer.MIN_VALUE;
int high = nums[nums.length-1], low = nums[nums.length-1];
int left = nums.length-1, right = nums.length-1;
for (int i=nums.length-2; i>=0; i--) {
if (nums[i] < ak) return true;
else if (nums[i] <= low) {
low = nums[i];
left = i;
} else if (nums[i] > low) {
if (nums[i] <= high) {
while (left<=right) {
int mid = left+(right-left)/2;
if (nums[mid]<nums[i] && nums[mid+1]>=nums[i]) {
if (nums[mid] > ak) {
ak = nums[mid];
aj = nums[i];
}
break;
} else if (nums[mid]<nums[i]) left = mid+1;
else right = mid-1;
}
} else {
if (high > ak) {
aj = nums[i];
ak = high;
}
}
low = high = nums[i];
left = right = i;
}
}
return false;
}
}
```