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

  • 5

    The general k-sum problem is discussed here 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):
            for x in num:
                if x not in filter:
                elif filter[x]<4:
            pairs=[[x,y] for x in xrange(len(new_num)) for y in xrange(x+1,len(new_num))]        
            for pair in pairs:
                if new_num[pair[0]]+new_num[pair[1]] in twoSums:
            for num1 in twoSums:
                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

    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)

  • 0

    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

    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

    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

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

  • 0

    the code is updated : )

  • 0

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

  • 0

    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.