Java 3ms beats 96.70% using Binary Search (UPDATED)


  • 0
    W

    ...

    public int[] intersection(int[] nums1, int[] nums2) {
        List<Integer> intersection = new LinkedList<Integer>();
        
        // make nums1 the longer array, nums2 the shorter array
        if(nums2.length > nums1.length){
            int[] tmp = nums1;
            nums1 = nums2;
            nums2 = tmp;
        }
        
        //sort nums1 and nums2
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        
        int startIndex = 0;
        for(int i=0; i<nums2.length; i++){
            // skip duplicated numbers
            if(i>0 && nums2[i-1]==nums2[i]){
                continue;
            }
            int bsIndex = Arrays.binarySearch(nums1, startIndex, nums1.length, nums2[i]);
            if(bsIndex >= 0){
                // Since nums2 is sorted, we only need to search from 1+(the index of the last element we searched in nums1)
                startIndex = bsIndex + 1;
                intersection.add(nums2[i]);
            }
        }
        
        int[] res = new int[intersection.size()];
        int i=0;
        for(int num : intersection){
            res[i++] = num;
        }
        return res;
    }
    

    ....

    The above solution is 5ms.

    To achieve Runtime 3ms, we can store the intersection in nums2 rather than creating a new list.
    ...

    public int[] intersection(int[] nums1, int[] nums2) {
        
        if(nums2.length > nums1.length){
            int[] tmp = nums1;
            nums1 = nums2;
            nums2 = tmp;
        }
        
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        
        int intersectionIndex = -1;
        int startIndex = 0;
        for(int i=0; i<nums2.length; i++){
            if(i>0 && nums2[i-1]==nums2[i]){
                continue;
            }
            int bsIndex = Arrays.binarySearch(nums1, startIndex, nums1.length, nums2[i]);
            if(bsIndex >= 0){
                startIndex = bsIndex + 1;
                nums2[++intersectionIndex] = nums2[i];
            }
        }
        
        return Arrays.copyOf(nums2, intersectionIndex+1);
    }
    

    ....


  • 0
    W

    Your runtime is at best O(nlogn) with n being the number of elements in the longer array. Using hashsets you can get down to O(n)


Log in to reply
 

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