Share my AC O(n2) python solution.


  • 4
    L

    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));
                            res.add((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;

  • 0
    F

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


  • 0
    L

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


  • 0
    F

    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


  • 0
    C

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


  • 4
    C

    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:
                            results.add(tuple(sorted([num[i] for i in comb])))
            
            
            return [list(sums) for sums in results]

  • 0
    X

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


  • 0
    I

    Hashmap should be O(1) in finding keys?


  • 0
    T

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

    [1 2 3 0] target=8


  • 0
    A

    @Chomolungma great solution :-)


Log in to reply
 

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