Last Updated: August 01, 2023
·
917
· lukasz-madon

Given a list of n integers, write a function to determine if any two sum to k

Three possible solutions:

  1. Naive. Compering all pairs of number. Perf O(n^2) Mem O(1)

    def find_pair_sum(lst, k):
        if lst is None:
            return
        for i in xrange(0, len(lst)):
            for j in xrange(0, len(lst)):
                if lst[i] + lst[j] == k:
                    yield lst[i], lst[j]
    
    for p in find_pair_sum([1,2,3,4,9,5], 6):
        print p
  2. Sorting and finding element with Binary Search. Perf O(nlgn) Mem O(1)

    def _binary_search_rec(lst, start, end, elem):   
        if start <= end:
            mid = (end - start) / 2 + start
            if lst[mid] == elem: 
                return True
            elif lst[mid] < elem:
                return _binary_search_rec(lst, mid + 1, end, elem)
            else:
                return _binary_search_rec(lst, start, mid - 1, elem)
    
    def binary_search(lst, elem):
        if lst is None:
            return False
        return _binary_search_rec(lst, 0, len(lst) - 1, elem)
    
    def find_pair_sum(lst, k):
        if lst is None:
            return 
        lst.sort()
        for elem in lst:
            if binary_search(lst, k - elem):
                yield elem, k - elem
    
    for p in find_pair_sum([1,2,3,4,9,5], 6):
        print p
  3. Using Hash set. Perf O(n) Mem O(n)

    def find_pair_sum(lst, k):
        if lst is None:
            return 
        s = set(lst)
        for elem in s:
            if k - elem in s:
                yield elem, k - elem
    
    for p in find_pair_sum([1,2,3,4,9,5], 6):
        print p

2 Responses
Add your response

I don't understand how III can be Pref O(n).
I think it would be O(n^2) or maybe O(nlgn). The second loop is hidden in the search for the (k-elem) element in the S set. This second loop would take O(n) or at best O(lgn) time depending on how the code was written by the system programmers (straight for loop or binary hash).

What am I missing?

over 1 year ago ·

@jratcliff python set is implemented as a hashset finding element takes O(1)

over 1 year ago ·