0170. Two Sum III - Data structure design

Easy | Binary Search | 80 ms (100.00%), 20.2 MB (85.90%)

❓ Problem Statement

Source: LeetCode - Two Sum III - Data structure design GitHub: Solution / Performance

Design a data structure that accepts a stream of integers and checks if it has a pair of integers that sum up to a particular value.

Implement the TwoSum class:

• TwoSum() Initializes the TwoSum object, with an empty array initially.

• void add(int number) Adds number to the data structure.

• boolean find(int value) Returns true if there exists any pair of numbers whose sum is equal to value, otherwise, it returns false.

✍🏻 Constraints & Example

💡 Ideas

🤖 Python3

class TwoSum:

    def __init__(self):
        self.data = []
        self.sorted = False

    def add(self, number: int) -> None:
        self.data.append(number)
        self.sorted = False

    def find(self, value: int) -> bool:
        if not self.sorted:
            self.data.sort()
            self.sorted = True
            
        start, end = 0, len(self.data) - 1
            
        while start < end:
            if self.data[start] + self.data[end] == value:
                return True
            elif self.data[start] + self.data[end] > value:
                # result may be on left side
                end = bisect_right(self.data, value - self.data[start], start+1, end) - 1
            else:
                # result may be on right side
                start = bisect_left(self.data, value - self.data[end], start+1, end - 1)
            
        return False

    def bisect_right(target: int, start: int, end: int) -> int:
        while start < end:
            mid = (start + end) // 2
            if self.data[mid] <= target: start = mid+1
            else: end = mid
        return start

    def bisect_left(target: int, start: int, end: int) -> int:
        while start < end:
            mid = (start + end) // 2
            if self.data[mid] < target: start = mid+1
            else: end = mid
        return start