# Java O(n logn) solution with Binary Indexed Tree

• Chinese called it "牛刀杀鸡"

1. Build BIT from right to left, for each a_i, find maximum a_j that j > i and a_j < a_i, save it as b_i
2. Iterate from left to right, find a_i that a_i and b_i > current minimum.
``````class Solution {
void update(int[] arr, int k) {
int i = k;
while (i < arr.length && arr[i] < k) {
arr[i] = k;
i += i&-i;
}
}
int read(int[] arr, int k) {
int max =0;
while (k > 0) {
max = Math.max(arr[k], max);
k -= k&-k;
}
return max;
}
public boolean find132pattern(int[] nums) {
Map<Integer, Integer> vToI = new HashMap<>();
int[] sorted = nums.clone();
Arrays.sort(sorted);
for (int i = 0; i < sorted.length; ++i) vToI.put(sorted[i], i+1);
int[] rightLess = new int[nums.length];
int[] bit = new int[nums.length+1];
for (int i = nums.length - 1; i >= 0; --i) {
update(bit, vToI.get(nums[i]));
}
int min = Integer.MAX_VALUE;
for (int i = 0; i < nums.length; ++i) {
min = Math.min(min, nums[i]);
int minI = vToI.get(min);
if (rightLess[i] > minI) return true;

}
return false;
}
}
``````

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