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.

Examples

Example 1:

1
2
3

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

Example 2:

1
2
3

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

Solution

Method 1 - Using Hashmap

Here is the approach:

  1. Initialization: Create a dictionary counts to store the frequency of each added number.
  2. Adding Numbers: When a number is added using the add method, increment its count in the counts dictionary. If the number is not already in the dictionary, initialize its count to 1.
  3. Finding a Pair:
    • The find method checks whether a pair of numbers exists that sums up to the specified value.
    • Iterate through the keys of the counts dictionary.
    • For each key (number), calculate the complement (target) that adds up to the specified value (target = value - num).
    • Check if the complement exists in the counts dictionary.
    • If the complement is the same as the current number, ensure that its count is at least 2 to satisfy the condition (i.e., the pair must have two distinct instances of the same number).
    • Return True if such a pair is found, otherwise continue the search.
    • If no pairs are found after iterating through the dictionary, return False.

Code

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

public class TwoSum {
	private HashMap<Integer, Integer> counts = new HashMap<Integer, Integer> ();

	public void add(int number) {
		counts.put(number, counts.getOrDefault(number, 0) + 1);
	}

	public boolean find(int value) {
		for (int num: elements.keySet()) {
			int target = value - num;
			if (elements.containsKey(target)) {
				if (num == target && counts.get(target)<2) {
					continue;
				}
				return true;
			}
		}
		return false;
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class TwoSum:
    def __init__(self):
        self.counts = {}

    def add(self, number: int) -> None:
        if number in self.counts:
            self.counts[number] += 1
        else:
            self.counts[number] = 1

    def find(self, value: int) -> bool:
        for num in self.counts:
            target = value - num
            if target in self.counts:
                if num == target and self.counts[target] < 2:
                    continue
                return true
        return false

Complexity

  • Time Complexity: O(n) find | O(1) add | Space Complexity: O(n)

Method 2 - Using List and Hashmap

Here is the better approach:

  • Maintain a dictionary to count the frequency of numbers and a list to store distinct numbers.
  • Keep track of the smallest and largest numbers added to quickly discard impossible pair sums.

Code

 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
30
31
32
33
34
35
36
37

class TwoSum {

    private Map<Integer,Boolean> map;
    private List<Integer> list;
    private int low = Integer.MAX_VALUE;
    private int high = Integer.MIN_VALUE;
    /** Initialize your data structure here. */
    public TwoSum() {
        map = new HashMap<>();
        list = new LinkedList<>();
    }

    /** Add the number to an internal data structure.. */
    public void add(int number) {
        if(map.containsKey(number)){
            map.put(number,true);
        }else{
            map.put(number,false);
            list.add(number);
            low = Math.min(low,number);
            high = Math.max(high,number);
        }
    }

    /** Find if there exists any pair of numbers which sum is equal to the value. */
    public boolean find(int value) {
        if(value < 2* low || value > 2*high) return false;
        for(int num : list){
            int target = value - num;
            if(map.containsKey(target)){
                if(num != target) return true;
                else if(map.get(target)) return true;
            }
        }
        return false;
    }
}
 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
30
31

class TwoSum:

    def __init__(self):
        """ Initialize your data structure here. """
        self.map = {}
        self.list = []
        self.low = float('inf')
        self.high = float('-inf')

    def add(self, number: int) -> None:
        """ Add the number to an internal data structure. """
        if number in self.map:
            self.map[number] = True
        else:
            self.map[number] = False
            self.list.append(number)
            self.low = min(self.low, number)
            self.high = max(self.high, number)

    def find(self, value: int) -> bool:
        """ Find if there exists any pair of numbers which sum is equal to the value. """
        if value < 2 * self.low or value > 2 * self.high:
            return False
        for num in self.list:
            target = value - num
            if target in self.map:
                if num != target:
                    return True
                elif self.map[target]:
                    return True
        return False

Complexity

  • ⏰ Time complexity
    • add(): O(1) for adding a number.
    • find(): O(n) for checking if a pair exists, where n is the number of unique elements.
  • 🧺 Space complexity: O(n) for storing the counts and unique numbers.