5ms O(MlogN) Binary Search Solution


  • 0

    Just a little tweaks on the BS solution from Intersection of Two Arrays I.

    In this problem, elements in the intersection does not have to be unique, so we have to make sure that when we apply binary search on B, it does not return the same value it has found previously.

    For example, for A = [1,2,2], B = [2,2], when we search for the second 2, binary search has to return the second 2 on B. If we still use the same algo in the previous problem, the algorithm will return the wrong result for A = [1,2,2], B = [1,2] => intersect = [2,2]. Because both 2s in A can be found in B.

    To tackle this, I maintain a lower bound on B, and every time we found a target value on B, we increase the lower bound so that for the next duplicate value, it does not search for that same element again.

    public int[] intersect(int[] A, int[] B) {
        if (A.length == 0 || B.length == 0) return new int[0];
        if (A.length > B.length) return intersect(B, A);  // apply bs on bigger array
        List<Integer> list = new ArrayList<>();
        Arrays.sort(A);
        Arrays.sort(B);
        
        int lowerBound = 0;  // lower bound for binary search
        for (int i = 0; i < A.length; i++) {
            int index = binarySearch(B, lowerBound, A[i]);
            if (index < B.length && B[index] == A[i]) {  // found on B
                list.add(A[i]);
                lowerBound = index + 1;
            }
        }
    
        // adding result from list to final int[]
        int[] res = new int[list.size()];
        int i = 0;
        for (int n : list)  res[i++] = n;
        return res;
    }
    
    private int binarySearch(int[] A, int lo, int target) {
        int L = lo, R = A.length-1;
        while (L < R) {
            int M = L + (R - L) / 2;
            if (A[M] < target)  L = M + 1;
            else                R = M;
        }
        return L;
    }

Log in to reply
 

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