Leetcode 170. Two Sum III - Data structure design

Problem

In this problem, we have to design a TwoSum class. It should support two operations: add and find.

• The add method takes an integer as an input and adds it to an internal data structure.
• The find method takes an integer as input, and it should return true if there exists any pair of numbers within the internal data structure that sums to the value given to find method else it should return false.

For instance, if add(1), add(3), and add(5) methods are called, the internal data structure contains the numbers [1, 3, 5]. Now, if find(4) method is called, it returns true because there exists a pair (1, 3) in the internal data structure that sums to 4.

Let's walk through this example to understand it better:

Example 1:

1. Call add(1) -> adds 1 to the internal data structure.
2. Call add(3) -> adds 3 to the internal data structure.
3. Call add(5) -> adds 5 to the internal data structure.
4. Call find(4) -> Returns true because there exists a pair (1, 3) in the internal data structure that sums to 4.
5. Call find(7) -> Returns false because there is no pair in the internal data structure that sums to 7.

Approach

The solution to this problem involves using a hash map data structure to keep track of the numbers that have been added using the add operation. For every number added, it increments the count associated with that number in the hash map.

When the find operation is called, it goes through every number in the hash map and calculates the remaining value which is value - number.

• If the number itself equals the remaining value, and there are more than one of that number, that means a pair is found, and it returns true.
• If the number does not equal the remaining value, and the remaining value is in the hash map, that means a pair is found, and it returns true.

Otherwise, a pair is not found and it returns false.

Python solution

1
2python
3class TwoSum:
4    def __init__(self):
5        self.count = {}
6
7    def add(self, number: int) -> None:
8        if number in self.count:
9            self.count[number] += 1
10        else:
11            self.count[number] = 1
12
13    def find(self, value: int) -> bool:
14        for key in self.count:
15            if value-key in self.count and (value-key != key or self.count[key] > 1):
16                return True
17        return False

Java solution

1
2java
3class TwoSum {
4    private HashMap<Integer, Integer> count = new HashMap<>();
5
6    public void add(int number) {
7        count.put(number, count.getOrDefault(number, 0) + 1);
8    }
9
10    public boolean find(int value) {
11        for (Integer key : count.keySet()) {
12            int remainder = value - key;
13            if ((key == remainder && count.get(key) > 1) ||
14                    (key != remainder && count.containsKey(remainder))) {
15                return true;
16            }
17        }
18        return false;
19    }
20}

Javascript solution

1
2javascript
3class TwoSum {
4    constructor() {
5        this.count = new Map();
6    }
7
8    add(number) {
9        this.count.set(number, (this.count.get(number) || 0) + 1);
10    }
11
12    find(value) {
13        for (let [key, freq] of this.count.entries()) {
14            let remainder = value - key;
15            if ((key == remainder && freq > 1) ||
16                    (key != remainder && this.count.has(remainder))) {
17                return true;
18            }
19        }
20        return false;
21    }
22}

C++ solution

1
2cpp
3class TwoSum {
4public:
5    unordered_map<int, int> count;
6
7    void add(int number) {
8        count[number]++;
9    }
10
11    bool find(int value) {
12        for (auto it = count.begin(); it != count.end(); ++it) {
13            int key = it->first;
14            int remainder = value - key;
15            if ((key == remainder && it->second > 1) ||
16                    (key != remainder && count.count(remainder))) {
17                return true;
18            }
19        }
20        return false;
21    }
22};

C# solution

1
2csharp
3public class TwoSum {
4    private Dictionary<int, int> count = new Dictionary<int, int>();
5
6    public void Add(int number) {
7        if (count.ContainsKey(number)) {
8            count[number]++;
9        } else {
10            count.Add(number, 1);
11        }
12    }
13
14    public bool Find(int value) {
15        foreach(var entry in count) {
16            int key = entry.Key;
17            int remainder = value - key;
18            if ((key == remainder && count[key] > 1) ||
19                    (key != remainder && count.ContainsKey(remainder))) {
20                return true;
21            }
22        }
23        return false;
24    }
25}

Rust solution

1
2rust
3use std::collections::HashMap;
4
5struct TwoSum {
6    count: HashMap<i32, i32>,
7}
8
9impl TwoSum {
10    pub fn new() -> Self {
11        Self {
12            count: HashMap::new(),
13        }
14    }
15
16    pub fn add(&mut self, num: i32) {
17        let counter = self.count.entry(num).or_insert(0);
18        *counter += 1;
19    }
20
21    pub fn find(&self, value: i32) -> bool {
22        for (&key, &val) in self.count.iter() {
23            let diff = value - key;
24            if (key == diff && val > 1) || (key != diff && self.count.contains_key(&diff)) {
25                return true;
26            }
27        }
28        false
29    }
30}

In this Rust solution, we utilize the HashMap data structure to count the integer numbers. The add function increases the value of the key (which is the given number), and find function iterates over the HashMap to find if a pair that adds up to the input exists.

Ruby solution

1
2ruby
3class TwoSum
4  attr_reader :count
5
6  def initialize
7    @count = Hash.new(0)
8  end
9
10  def add(number)
11    @count[number] += 1
12  end
13
14  def find(value)
15    @count.each do |key, _|
16      remainder = value - key
17      next if remainder == key && @count[key] < 2
18      return true if @count.key?(remainder)
19    end
20    false
21  end
22end

Here, in the Ruby solution, we also use a Hash to store the count of each number that was added. If the pair for the value is found, we return 'true'. If not, after checking all possible values, we return 'false'.