# Java O(nlogn) time and O(1) space solution(11ms) with detailed explanation

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

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