Java O(n logn) solution with Binary Indexed Tree


  • 0
    F

    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]));
                rightLess[i] = read(bit, vToI.get(nums[i])-1);
            }
            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;
        }
    }
    

Log in to reply
 

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