Is there really a O(n^2) solution?


  • 5
    P

    The general k-sum problem is discussed here http://cs.stackexchange.com/questions/2973/generalised-3sum-k-sum-problem. The optimal solution is said to be O(N^(K/2) logN) in general for even K.

    I understand for some special cases there are faster solutions but I have seen not a single solution in the discuss which is O(N^2) (even some are claimed to be O(N^2)).

    Please answer this question after you checked the following case:
    Num has 2N elements of N -1s and N 1s. Target is 0.

    I modified @Chomolungma code which I think is O(N^2). After removing the number of repeating elements to at most 4, the size of duplicates can be bounded by a constant which leads to O(N^2).

    class Solution:
        # @return a list of lists of length 4, [[val1,val2,val3,val4]]
        def fourSum(self, num, target):
            results=set()
            num.sort()
            new_num=[]
            filter=dict()
            for x in num:
                if x not in filter:
                    filter[x]=1
                    new_num.append(x)
                elif filter[x]<4:
                    filter[x]+=1;
                    new_num.append(x)
            pairs=[[x,y] for x in xrange(len(new_num)) for y in xrange(x+1,len(new_num))]        
            twoSums=dict()
            for pair in pairs:
                if new_num[pair[0]]+new_num[pair[1]] in twoSums:
                    twoSums[new_num[pair[0]]+new_num[pair[1]]].append(pair)
                else:
                    twoSums[new_num[pair[0]]+new_num[pair[1]]]=[pair]
    
            for num1 in twoSums:
                num2=target-num1
                if num2 >= num1 and num2 in twoSums:
                    combinations=[pair1+pair2 for pair1 in twoSums[num1] for pair2 in twoSums[num2] if pair1[1]<pair2[0]]
                    for comb in combinations:
                        results.add(tuple([new_num[i] for i in comb]))
            return [list(sums) for sums in results]

  • 1
    C

    Yes there is.

    The general optimum for k-sum is O(n^(k/2)lg(k)). But there are special cases for some even k's to run faster.

    Refer to this question:

    Roll down to my answer. the OP's algorithm is very smart, but as it need to sort, it was actually O(n^2lg(n)). Mine does not sort, it should be O(n^2)

    https://oj.leetcode.com/discuss/18953/share-my-ac-o-n2-python-solution


  • 0
    P

    I agree with you "there are special cases for some even k's to run faster". That is the reason I post the question here. However, you need to show it is O(n^2). The gap is that it is hard to analyze how many elements in the hashtable (key: list of pairs) and how many elements in the list of pairs given a key value. As a consequence, in your code the size of combinations is not clear (combinations=[pair1+pair2 for pair1 in twoSums[num1] for pair2 in twoSums[num2]]). Actually I think in the worst case, your code is O(N^4). Let's say that num has 2N elements of N -1s and N 1s, target is 0.
    Then we have 3 keys, -2,0, and 2. Just take key 2 and -2 for example. There are O(N^2) pair1s and O(N^2) pair2s which lead to O(N^4) pair1+pair2. Correct me if I am wrong.


  • 0
    C

    I was well aware of the problem you raised. And that's why I said we could refine the algorithm by first filtering off excessive repeating elements. We don't need those repeat to be more than 4 times. I just did not take the time to do the refinement in my own code, but I did mention it.


  • 0
    C

    remove the duplicate elements from the input list, not from the pairs. You don't need the same element appearing more than 4 times in the input list. That is O(N)


  • 0
    P

    I think you are right after filtering the repeating elements down to 4. Would you update your answer?


  • 0
    C

    the code is updated : )


  • 0
    L

    What about num = [-n, -n+1, ...,-1, 1,..., n]. Is it still n^2 pair for 0, making comb n^4?


  • 0
    W

    in this case, the size of answer list is about (n^3)/48,so in the worst case, the time complexity is at least O(n^3).


Log in to reply
 

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