Leetcode 4sum problem using hashmaps

Question

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

Answer 1

• 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} & {p, q}):
                    indices = tuple(sorted(array[x] for x in (i, j, p, q)))
                    result.add(indices)
    return result

Answer 2

Implementation

• why not build result with condition i < j < p < q?

Algorithm

• code builds hash map as combination of all indexes from nums. Combination of all unique values from nums (or index or unique values) is better choice. Case: fourSum([0 for x in range(n)], 0)
• code builds hash map with integers from nums which can't be added to result. Case: fourSum([x for x in range(1, n, 1)], 0)
• code check if for key from hash map also target - key exists in final loop, can earlier. Case: fourSum([x for x in range(0, n*10, 10)], n*5+1)
• You can split hash map for two parts: a,b and c,d pair. Don't change complexity of hash map, but final loop: 1/2 * 1/2 faster

Speedup

• best: algorithm (big O notation), e.g. reduce O(n^2) memory to O(n)
• sometimes good: algorithm constants, e.g. split hash map for first and second pair
• bad: dirty, low-level language speed-up constants, e.g. replace itertools.combinations with directly loops. This is anti-pattern. Reasons: less understandable, maintainable, changeable and paradoxically slower. Slower because bottlenecks are usually caused by cascade several algorithms, e.g. O(n^3) * O(n^3). With clean code easier reduce problem to O(n^5) or less. With dirty code usually at the end we get O(n^6) with small const

Code (the same O(n^2) mem)

from itertools import combinations
from collections import defaultdict, Counter

def fourSum(self, nums, target):
    if len(nums) < 4:
        return []
    half_target = target // 2
    counter = Counter(nums)
    uniques_wide = sorted(counter)
    x_min, x_max = target - 3 * uniques_wide[-1], target - 3 * uniques_wide[0] # bad
    uniques = [ x for x in uniques_wide if x_min <= x <= x_max ]
    duplicates = [x for x in uniques if counter[x] > 1]

    target_minus_xy_sums = set(target - x - y for x, y in combinations(uniques, 2))
    target_minus_xy_sums |= set(target - x - x for x in duplicates)

    ab_sum_pairs, cd_sum_pairs = defaultdict(list), defaultdict(list)
    for (x, y) in combinations(uniques, 2):
        if x + y in target_minus_xy_sums:
            if x + y <= half_target:
                ab_sum_pairs[x + y].append((x, y))
            if x + y >= half_target:
                cd_sum_pairs[x + y].append((x, y))
    for x in duplicates:
        if x + x in target_minus_xy_sums:
            if x + x <= half_target:
                ab_sum_pairs[x + x].append((x, x))
            if x + x >= half_target:
                cd_sum_pairs[x + x].append((x, x))

    return [[a, b, c, d]
            for ab in ab_sum_pairs
            for (a, b) in ab_sum_pairs[ab]
            for (c, d) in cd_sum_pairs[target - ab]
            if b < c or b == c and [a, b, c, d].count(b) <= counter[b]] # if bi < ci