🏰 Palace Window

Search

SearchSearch

Hash Table

Problems

 

Two Sum

Given an array of integers & a target, compute all possible unique two sums that add to the target without replacement returning them as a list of lists. (variant of simpler unique soln problem)

Explore

 t=4
 1 2 3 4 5 6 0 -1
 3 2 1 0-1-2 4  5
  1. Keep track of the value needed to add to reach target in a dictionary that maps value→index for return purposes.
  2. As a solution is found, add it to the solutions list.

Python Solution

class Solution:
    def m(self, nums, target) -> list:
        soln = set()
        diffs = {}
        for i, n in enumerate(nums):
            t = target - n
            if t in diffs:
                soln.add(tuple(sorted([diffs[t], i])))
            diffs[n] = i
 
        return list(soln)

Complexity

We iterate over the input once doing amortized constant time insertions & lookups in the hashmaps yielding O(n) time & space.

 

3Sum

Given an integer array, return all unique triplets that sum to zero|target without replacement.

Explore

t=0 t=0 -1 0 1 2 -1 4 -1 -1 0 1 2 4 -1 -1 2 -1 0 1 -1 0 1 → x

  1. Sort the array.
  2. Consider each array element as -t in a two sum hash table solution containing only the elements to the right of it.
  3. Use a set to check potential solutions for uniqueness. (sorted tuples are hashable)

Python Solution

class Solution:
    def three_sum(self, nums, target) -> list:
        nums.sort()
 
        soln = []
        unique = set()
        comps = {}
        for i, n in enumerate(nums):
            t = target - n
            for m in nums[i + 1 :]:
                c = t - m
                if c in comps and comps[c] == i:
                    p = [c, m, -t]
                    u = tuple(sorted(p))
                    if u not in unique:
                        unique.add(u)
                        soln.append(p)
 
                comps[m] = i
 
        return soln
 
 
# Optimizations if there are follow up questions.
# if n > target or 0<i<n-1 and nums[i] == nums[i-1]:
#     break
# If we have to offer more, we could do this without sorting
# using three tuples.

Complexity

We sort the input in nlogn time & perform two nested iterations on the input array for an O(n^2) time & O(n) space.

Graph View