C# - hash table to reduce to O(n^2) but why the Tag to use Binary Search?


  • 0

    Here is the common hash table solution which reduces the time/iterations from n^4 to n^2 with trade off of n^2 space usage. But there is a clue/tag on problem which calls for Binary Search. Any idea what that is hinting at?

    Also it says the lengths are all equal but the only thing I can think of as to why they mention that is so we don't have to check which arrays to pair for the looping. You'd want to pair arrays so that the total iterations for each of the steps (product of lengths) is as equal as possible.

        public int FourSumCount(int[] A, int[] B, int[] C, int[] D) 
        {
            Dictionary<int,int> countsCD = new Dictionary<int,int>();
            foreach (int c in C)
            {
                foreach (int d in D)
                {
                    int sum = c + d;
                    countsCD[sum] = 1 + (countsCD.ContainsKey(sum) ? countsCD[sum] : 0);
                }
            }
            
            int count = 0;
            foreach (int a in A)
            {
                foreach (int b in B)
                {
                    int diff = -(a + b);
                    count  += countsCD.ContainsKey(diff) ? countsCD[diff] : 0;
                }
            }
            
            return count;
        }
    

  • 0

    @jdrogin Here is the BinarySearch method you are talking about in C version

    int compare_ints(const void* a, const void* b)
    {
        int arg1 = *(const int*)a;
        int arg2 = *(const int*)b;
        if (arg1 < arg2) return -1;
        if (arg1 > arg2) return 1;
        return 0;
    }
    
    int lowerBound(int*arr, int size, int target){
        int l = 0, r = size-1;
        while(l <= r){
            int m = l+((r-l)>>1);
            if(arr[m] >= target) r = m-1;
            else l = m+1;
        }
        return arr[l]==target? l : -1;
    }
    
    int upperBound(int*arr, int size, int target){
        int l = 0, r = size-1;
        while(l <= r){
            int m = l+((r-l)>>1);
            if(arr[m] <= target) l = m+1;
            else r = m-1;
        }
        return arr[r]==target? r : -1;
    }
    int fourSumCount(int* A, int ASize, int* B, int BSize, int* C, int CSize, int* D, int DSize) {
        int *arr1 = (int*)malloc(sizeof(int)*(ASize*BSize)), *arr2 = (int*)malloc(sizeof(int)*(CSize*DSize));
        int k = 0;
        for(int i = 0; i < ASize; ++i)
            for(int j = 0; j < BSize; ++j)
                arr1[k++] = A[i]+B[j];
        k = 0;
        for(int i = 0; i < CSize; ++i)
            for(int j = 0; j < DSize; ++j)
                arr2[k++] = C[i]+D[j];
        qsort(arr1, ASize*BSize, sizeof(int), compare_ints);
        qsort(arr2, CSize*DSize, sizeof(int), compare_ints);
        int sumCount = 0;
        for(int i = 0; i < ASize*BSize; ++i){
            int l = lowerBound(arr2, CSize*DSize, -arr1[i]);
            if(l != -1){
                int r = upperBound(arr2, CSize*DSize, -arr1[i]);
                sumCount += r-l+1;
            }
        }
        return sumCount;
    }
    

  • 0

    @LHearen I see now. It is either Hash table or Binary Search. I figured somehow they were suggesting to use both. Got it. Thanks!


Log in to reply
 

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