TLE C solution. Any Help?


  • 0

    What can I do with ASize = BSize = ... = N?

    int fourSumCount(int* A, int ASize, int* B, int BSize, int* C, int CSize, int* D, int DSize) {
        int i, j, k, l, cnt = 0;
        int tar1, tar2, tar3;
        for (i = 0; i < ASize;){
            tar1 = 0 - A[i++];
            for (j = 0; j < BSize;){
                tar2 = tar1 - B[j++];
                for (k = 0; k < CSize;){
                    tar3 = tar2 - C[k++];
                    for (l = 0; l < DSize;)
                        if (D[l++] == tar3)
                            cnt++; 
                }
            }
        }
        return cnt;
    }
    

    TLE when pass 26/48.


  • 2

    yeah, you are using n^4 iterations, you need to look for a solution with better performance. The hint provided is to use a hash table. If you just want to know the answer there are several accepted solutions posted.


  • 1

    @leakey Actually once the scope/scale of the problem is up to 100 million then your solution will tumble into TLE, while your solution here will reach 250000*250000 in its worst case.
    This is a kind of guideline for your algorithm selection in the future. Just as @jdrogin mentioned, you could utilise map to do pruning and accelerating.


  • 1

    @leakey I just finished the following solution in C. Sorry about mentioning Hash or Map in my last reply, which is really a hurt in C. So here is a solution in C using Binary Search to reduce the time complexity.

    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;
    }
    

  • 1

    @leakey said in TLE C solution. Any Help?:

    What can I do with ASize = BSize = ... = N?

    For 4 lists with same sizes, it is a hint to simply balance partial sum matching of zero using hashmap into two groups of lists with each group containing two lists (i.e., O(N2)).

    However, for generic list sizes, it is a little tricky about how to wisely pick which list(s) to build the hasmap. I have posted a time analysis for generic list sizes.


Log in to reply
 

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