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

• 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)).

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:
return [list(sums) for sums in results]``````

• 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

• 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.

• 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.

• 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)

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

• the code is updated : )

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

• 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).

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