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

Constraints:

• -10^5 <= number <= 10^5

• -2^31 <= value <= 2^31 - 1

• At most 5 * 10^4 calls will be made to add and find.

Input
["TwoSum", "add", "add", "add", "find", "find"]
[[], [1], [3], [5], [4], [7]]
Output
[null, null, null, null, true, false]

Explanation
TwoSum twoSum = new TwoSum();
twoSum.add(1);   // [] --> [1]
twoSum.add(3);   // [1] --> [1,3]
twoSum.add(5);   // [1,3] --> [1,3,5]
twoSum.find(4);  // 1 + 3 = 4, return true
twoSum.find(7);  // No two integers sum up to 7, return false

💡 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