Two Number Sum

This is a simple function that takes in an array of integers and another single integer. The idea is to look through the array and find the first set of numbers that add up to the target sum. The problem assumes the array is always full of numbers and that there is no more than one set of numbers that add up to the target sum.

"""
Searches list for two numbers that add up to a targeted sum and
returns a sorted list of the two numbers.
"""


class TwoNumberSum:
    """
    Class will take a non empty array of integers and an integer representing
    a target.  If any two numbers within the array add up to the target number,
    the two numbers are returned sorted.
    For this, it is assumed that there is no more than one set of numbers that
    will add up to the target sum.
    If no numbers total the target sum, an empty list is returned.
    """

    def __init__(self, array: list, target_sum: int) -> list:
        """

        :param array:
        :param target_sum:
        """
        self.arr = array
        self.target = target_sum

        self.rv = []

    def __clear_rv(self):
        self.rv = None if self.rv is not None else self.rv

    def brute_force(self):
        """
        O(n^2) time, O(1) space
        :return: sorted list
        """
        self.__clear_rv()
        for a in self.arr:
            for b in [b for b in self.arr if a != b]:
                if a + b == self.target:
                    self.rv = [a, b]
                    break
        return sorted(self.rv)

    def dictionary_populate(self):
        """
        O(n) time
        O(n) space
        :return: sorted list
        """
        self.__clear_rv()
        seen_values = {}
        for num in self.arr:
            match = self.target - num
            if match in seen_values:
                self.rv = [match, num]
                break
            else:
                seen_values[num] = True
        return sorted(self.rv)

    def collapsing_pointers(self):
        """
        O(nLog(n)) time, O(1) space
        :return: sorted list
        """
        sa = sorted(self.arr)
        left, right = 0, len(sa) - 1
        while left < right:
            _ = sa[left] + sa[right]
            if _ == self.target:
                self.rv = [sa[left], sa[right]]
            elif _ < self.target:
                left += 1
            elif _ > self.target:
                right -= 1
        return sorted(self.rv)
comments powered by Disqus