Skip to content

170. Two Sum III - Data structure design πŸ”’

DifficultyEasy

Description

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.

 

Example 1:

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

 

Constraints:

  • -105 <= number <= 105
  • -231 <= value <= 231 - 1
  • At most 104 calls will be made to add and find.

Solutions

Solution 1: Hash Table

Thinking

Support adding numbers and querying whether two of them sum to a value. At most \(10^4\) calls. Sorting on every \(\textit{find}\) is undone by later adds. A frequency map makes \(\textit{add}\) \(O(1)\); \(\textit{find}\) tries each \(x\) and looks up \(\textit{value}-x\), requiring count at least \(2\) when \(x\) equals \(\textit{value}-x\).

We use a hash table cnt to store the count of each number.

When the \(\textit{add}\) method is called, we increment the count of the number number.

When the \(\textit{find}\) method is called, we iterate over the hash table cnt. For each key x, we check if value - x is also a key in the hash table cnt. If it is, we check if x is equal to value - x. If they are not equal, it means we have found a pair of numbers whose sum is \(\textit{value}\), and we return true. If they are equal, we check if the count of x is greater than 1. If it is, it means we have found a pair of numbers whose sum is \(\textit{value}\), and we return true. If it is less than or equal to 1, it means we have not found a pair of numbers whose sum is \(\textit{value}\), and we continue to iterate over the hash table cnt. If we have not found a pair after the iteration, we return false.

Time complexity:

  • The time complexity of the \(\textit{add}\) method is \(O(1)\).
  • The time complexity of the \(\textit{find}\) method is \(O(n)\).

The space complexity is \(O(n)\), where \(n\) is the size of the hash table \(\textit{cnt}\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class TwoSum:

    def __init__(self):
        self.cnt = defaultdict(int)

    def add(self, number: int) -> None:
        self.cnt[number] += 1

    def find(self, value: int) -> bool:
        for x, v in self.cnt.items():
            y = value - x
            if y in self.cnt and (x != y or v > 1):
                return True
        return False


# Your TwoSum object will be instantiated and called as such:
# obj = TwoSum()
# obj.add(number)
# param_2 = obj.find(value)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class TwoSum {
    private Map<Integer, Integer> cnt = new HashMap<>();

    public TwoSum() {
    }

    public void add(int number) {
        cnt.merge(number, 1, Integer::sum);
    }

    public boolean find(int value) {
        for (var e : cnt.entrySet()) {
            int x = e.getKey(), v = e.getValue();
            int y = value - x;
            if (cnt.containsKey(y) && (x != y || v > 1)) {
                return true;
            }
        }
        return false;
    }
}

/**
 * Your TwoSum object will be instantiated and called as such:
 * TwoSum obj = new TwoSum();
 * obj.add(number);
 * boolean param_2 = obj.find(value);
 */
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class TwoSum {
public:
    TwoSum() {
    }

    void add(int number) {
        ++cnt[number];
    }

    bool find(int value) {
        for (auto& [x, v] : cnt) {
            long y = (long) value - x;
            if (cnt.contains(y) && (x != y || v > 1)) {
                return true;
            }
        }
        return false;
    }

private:
    unordered_map<int, int> cnt;
};

/**
 * Your TwoSum object will be instantiated and called as such:
 * TwoSum* obj = new TwoSum();
 * obj->add(number);
 * bool param_2 = obj->find(value);
 */
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
type TwoSum struct {
    cnt map[int]int
}

func Constructor() TwoSum {
    return TwoSum{map[int]int{}}
}

func (this *TwoSum) Add(number int) {
    this.cnt[number] += 1
}

func (this *TwoSum) Find(value int) bool {
    for x, v := range this.cnt {
        y := value - x
        if _, ok := this.cnt[y]; ok && (x != y || v > 1) {
            return true
        }
    }
    return false
}

/**
 * Your TwoSum object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Add(number);
 * param_2 := obj.Find(value);
 */
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class TwoSum {
    private cnt: Map<number, number> = new Map();
    constructor() {}

    add(number: number): void {
        this.cnt.set(number, (this.cnt.get(number) || 0) + 1);
    }

    find(value: number): boolean {
        for (const [x, v] of this.cnt) {
            const y = value - x;
            if (this.cnt.has(y) && (x !== y || v > 1)) {
                return true;
            }
        }
        return false;
    }
}

/**
 * Your TwoSum object will be instantiated and called as such:
 * var obj = new TwoSum()
 * obj.add(number)
 * var param_2 = obj.find(value)
 */

Comments