O(nlgn) solution using sorting and binary search with explanation


  • 1
    S

    The idea is to use a modified version of binary search, our binary search returns the index of the first index of the element or -1 otherwise.

    static int binarySearch(int[]a, int startIndex, int key){
        int low = startIndex;
        int high = a.length-1;
        while (low<=high){
            int mid = (low + high)/2;
            int midValue = a[mid];
            if (midValue >= key){
                high = mid - 1;
            }
            else if(midValue < key){
                low = mid + 1;
            }
        }
        if(low>=startIndex && low<a.length && a[low] == key){
            return low;
        }
        return -1;
    }
    

    We sort both arrays, for each element in the bigger array we binary search the smaller array and as long as the elements exist in both arrays we add them to the result, otherwise we skip the elements from both arrays.

    static int[] intersection(int[] nums1, int[] nums2) {
        List<Integer> resultList = new ArrayList<>();
        int[]bigger,smaller;
    
        Arrays.sort(nums1);
        Arrays.sort(nums2);
    
        if(nums1.length >= nums2.length){
            bigger = nums1;
            smaller = nums2;
        }else{
            bigger = nums2;
            smaller = nums1;
        }
    
        int smallIndex = 0;
        for (int i = 0; i < bigger.length; ) {
            int value = bigger[i];
    
            int resultIndex = binarySearch(smaller,smallIndex,value);
            if(resultIndex>=0){
                smallIndex = resultIndex;
                while (i<bigger.length && smallIndex <smaller.length && bigger[i]==value && smaller[smallIndex]==value) {
                    resultList.add(value);
                    i++;
                    smallIndex++;
                }
                while (i<bigger.length && bigger[i]==value){
                    i++;
                }
                while (smallIndex < smaller.length && smaller[smallIndex]==value){
                    smallIndex++;
                }
    
            }else{
                i++;
            }
        }
        int[] result = new int[resultList.size()];
        int index = 0;
        for (Integer i : resultList) {
            result[index++] = i;
        }
        return result;
    }

  • 0
    H

    Thanks for sharing.
    The third while can be removed, since the first while already taken care of smallIndex increment.


  • 0
    D

    why you take the loop of the bigger array? Denote the size of small array is m, and size of bigger is n. If we binary search in the small array and loop the bigger, the runtime is o(nlog(m)). And the other way is o(mlog(n)). Compare these two, I think we should for loop the small one and binary search the bigger one, right?

    But if you consider the question 3 in the leetcode which means the memory of load is limited,then I think you are totally right


Log in to reply
 

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