Reference: LeetCode
Difficulty: Easy

Problem

Design and implement a TwoSum class. It should support the following operations: add and find.

  • add - Add the number to an internal data structure.
  • find - Find if there exists any pair of numbers which sum is equal to the value.

Example: 

1
2
3
4
5
6
7
add(1); add(3); add(5);
find(4) -> true
find(7) -> false

add(3); add(1); add(2);
find(3) -> true
find(6) -> false

Analysis

Two Sets

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Set<Integer> nums = new HashSet<>();
Set<Integer> sums = new HashSet<>();

/** Add the number to an internal data structure.. */
public void add(int number) {
  if (nums.contains(number)) {
    sums.add(number * 2);
  } else {
    for (int val : nums) {
      sums.add(number + val);
    }
    nums.add(number);
  }
}

/** Find if there exists any pair of numbers which sum is equal to the value. */
public boolean find(int value) {
  return sums.contains(value);
}

Time: add would take $O(N)$ time each time.
Space: Since we have sums set, it takes $O(N^2)$ space.

Count Map

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Map<Integer, Integer> map = new HashMap<>();

/** Add the number to an internal data structure.. */
public void add(int number) {
  map.put(number, map.getOrDefault(number, 0) + 1);
}

/** Find if there exists any pair of numbers which sum is equal to the value. */
public boolean find(int value) {
  for (int val1 : map.keySet()) {
    int val2 = value - val1;
    if (map.containsKey(val2)) {
      if (val1 == val2) {
        if (map.get(val1) >= 2) return true;
      } else {
        return true;
      }
    }
  }
  return false;
}

Time: find takes $O(N)$.
Space: $O(N)$