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)$


Comment