Leetcode 4sum problem using hashmaps 4sum problem


  Given an array S of n integers, are there elements a, b, c, and d in S
  such that a + b + c + d = target? Find all unique quadruplets in the
  array which gives the sum of target.
  
  Note: The solution set must not contain duplicate quadruplets.


Idea is to put all the pair sums a in hashmap along with corresponding indexes and once done check if -a is also present in the hashmap. If both a and -a is present and since the question is looking for unique quadruplets then we can just filter out with indexes.

class Solution(object):
    def fourSum(self, arr, target):
        seen = {}
        for i in range(len(arr)-1):
            for j in range(i+1, len(arr)):
                if arr[i]+arr[j] in seen: 
                    seen[arr[i]+arr[j]].add((i,j))
                else: 
                    seen[arr[i]+arr[j]] = {(i,j)}
        result = []
        for key in seen:
            if -key + target in seen:
                for (i,j) in seen[key]:
                    for (p,q) in seen[-key + target]:
                        sorted_index = sorted([arr[i], arr[j], arr[p], arr[q]])
                        if i not in (p, q) and j not in (p, q) and sorted_index not in result:
                            result.append(sorted_index)
        return result
Use enumerate rather than range(len(...)) + __getitem__. It is both faster and more readable.
To limit items of the second iteration to be "after the current item" you can use itertools.combinations.
To avoid the need to check for the special case of "is the item already in the dictionary?", use a collections.defaultdict.
You could use a set rather than a list to store the final results and remove yourself the need to check for duplicates
-key + target is better written as target - key




import itertools
from collections import defaultdict


def four_sum(array, target):
    seen = defaultdict(set)
    for (i, first), (j, second) in itertools.combinations(enumerate(array), 2):
        seen[first + second].add((i, j))

    result = set()
    for key, first_indices in seen.items():
        second_indices = seen.get(target - key, set())
        for p, q in second_indices:
            for i, j in first_indices:
                # Not reusing the same number twice
                if not ({i, j} &amp; {p, q}):
                    indices = tuple(sorted(array[x] for x in (i, j, p, q)))
                    result.add(indices)
    return result