# Share my AC O(n2) python solution.

• 1: Create the sum for each pair, like this: [sum,list_of_pairs]

2; sort the pairs by key.

3: find the match condition pairs, and filter them out.

def fourSum(self, num, target):
num=sorted(num);
sum2={}
for i in range(len(num)):
for j in range(i+1,len(num)):
sumij=num[i]+num[j];
if(sumij not in sum2):
sum2[sumij]=[];
sum2[sumij].append((i,j));
sum2 = sorted(sum2.items(), key=lambda x:x[0])

res=set();
i,j=0,len(sum2)-1;
while(i<=j):
total=sum2[i][0]+sum2[j][0];
if(total==target):
for k1 in range(len(sum2[i][1])):
for k2 in range(len(sum2[j][1])):
a,b=sum2[i][1][k1];
c,d=sum2[j][1][k2];
items= set([a,b,c,d]);
if(len(items)==4):
newItem=[num[fi] for fi in items];
newItem=tuple(sorted(newItem));
i+=1;
j-=1;
elif(total<target):
i+=1;
else:
j-=1;

resNums= [];
for item in res:
resNums.append([i for i in item]);
return resNums;

• Why do you think the complexity of your solution is O(n2)? I think this line would exceed O(n2) since sums may have O(n2) items in it:
sum2 = sorted(sum2.items(), key=lambda x:x[0])

• Time complexity is a fuzzy concept, no matter 1n2, or 10000n2, they both O(n2).

• I think you misunderstand my meaning, i meant number of sum2 is n^2, so the complexity of sorting an array with n^2 items should be NlogN where N is n^2, so the complexity should be n^2 *logn^2 = 2n^2logn , so the complexity is O(n^2logn), i think

• he actually does not have to sort the list. I used similar strategy, without sorting. See my solution.

• Good job, lovejenny! I used a similar strategy. I did not sort the pairSum dictionary, so it will run in O(n^2). One thing we can improve is to preprocess the list, to eliminate redundant element beyond three repeats (if the target is n, limit elements that is not n/4 to at most 3 repeats). this could improve some worst cases.

Update:
filtering added to remove excessive elements.

class Solution:
# @return a list of lists of length 4, [[val1,val2,val3,val4]]
def fourSum(self, num, target):

newNum=[]
filter=dict()
for i in num:
if i in filter:
if (filter[i]==3 and i*4!=target) or filter[i]==4:
continue
else:
newNum.append(i)
filter[i]+=1
else:
newNum.append(i)
filter[i]=1

num=newNum

pairs=[[x,y] for x in xrange(len(num)) for y in xrange(x+1,len(num))]
results=set()

twoSums=dict()
for pair in pairs:
if num[pair[0]]+num[pair[1]] in twoSums:
twoSums[num[pair[0]]+num[pair[1]]].append(pair)
else:
twoSums[num[pair[0]]+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]]
for comb in combinations:
if len(set(comb))==4:

return [list(sums) for sums in results]

• Your code is not O(n^2).

for pair in pairs: ////here, there are n^2 pairs
if num[pair[0]]+num[pair[1]] in twoSums: // and here, the 'in' operation take log(n^2) time.

So, it should be O(n^2*log(n^2));

• Hashmap should be O(1) in finding keys?

• this only works if u allow reuse of elements: e.g.

[1 2 3 0] target=8

• @Chomolungma great solution :-)

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