# 0170. Two Sum III - Data structure design

{% tabs %}
{% tab title="❓ Problem Statement" %}

> Source: [LeetCode - Two Sum III - Data structure design](https://leetcode.com/problems/two-sum-iii-data-structure-design/)\
> GitHub: [Solution / Performance](https://github.com/yylou/leetcode/tree/main/0170-two-sum-iii-data-structure-design)

**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`.
  {% endtab %}

{% tab title="✍🏻 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
```

{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="💡 Ideas" %}

{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="🤖 Python3" %}

```python
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
```

{% endtab %}
{% endtabs %}