# Trade off in this problem should be considered

• The big data test only have the condition that lots of add and few find. In fact, there has to be one operation's time complexity is O(n) and the other is O(1), no matter add or find. So clearly there's trade off when solve this problem, prefer quick find or quick add.

If consider more find and less add or we only care time complexity in finding.For example, add operation can be pre-done.

``````public class TwoSum {
Set<Integer> sum;
Set<Integer> num;

TwoSum(){
sum = new HashSet<Integer>();
num = new HashSet<Integer>();
}
// Add the number to an internal data structure.
if(num.contains(number)){
}else{
Iterator<Integer> iter = num.iterator();
while(iter.hasNext()){
}
}
}

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

On the other side

``````public class TwoSum {
Map<Integer,Integer> hm;

TwoSum(){
hm = new HashMap<Integer,Integer>();
}
// Add the number to an internal data structure.
if(hm.containsKey(number)){
hm.put(number,2);
}else{
hm.put(number,1);
}
}

// Find if there exists any pair of numbers which sum is equal to the value.
public boolean find(int value) {
Iterator<Integer> iter = hm.keySet().iterator();
while(iter.hasNext()){
int num1 = iter.next();
int num2 = value - num1;
if(hm.containsKey(num2)){
if(num1 != num2 || hm.get(num2) == 2){
return true;
}
}
}
return false;
}
}``````

• I basicly use the second method except for manual iteration instead of using an iterator, but TLE here.

Storing all possible sum may lead to O(n2) space.

• Both solution is now TLE.

• Change the type of HashMap to LinkedHashMap can boost the traversal. Hence, TLE can be avoided.

• I think this part is not necessary:

``````if(num.contains(number)){
...
``````

is that right?

• why you are so sure one operation should be O(n)?

• @chidong it is a clever optimization if you think of it. The problem is a 2-sum so the only possible new sum that could be added is number*2. You don't have to iterate again through the entire set and add all the sums.

• @syftalent In the first algorithm

The find method is using contains method. Doesn't that mean it takes linear time to search through the list?

• ``````public class TwoSum {
ArrayList<Integer> list = new ArrayList<>();
// Add the number to an internal data structure.
}

// Find if there exists any pair of numbers which sum is equal to the value.
public boolean find(int value) {
HashSet<Integer> set = new HashSet<>();
for(Integer num : list){
if(set.contains(value - num)){
return true;
}
}
return false;
}
}
``````

As @wei88 pointed storing sum will have O(n^2) complexity. I used the second approach but every find is taking O(n) space which might be not good. Any improvements ?

A couple points to consider:

• you can simplify your map and just map to Boolean because you are using an integer but only caring about 2 states, occurring once or more than once.
• this seems like a bit of cheap trick but when I did this I shaved off 30% of my OJ time. For basically no cost you can keep track of min/max to rule out queries for numbers outside the bounds.
``````public class TwoSum
{
Dictionary<int,bool> map = new Dictionary<int,bool>();
int max = int.MinValue;
int min = int.MaxValue;

public TwoSum() { }

{
map[number] = map.ContainsKey(number);
max = Math.Max(max, number);
min = Math.Min(min, number);
}

public bool Find(int value)
{
if (value < min + min || value > max + max) return false;
foreach (int x in map.Keys)
{
int y = value - x;
if (map.ContainsKey(y) && (x != y || map[y] == true)) return true;
}
return false;
}
}
``````

• @syftalent I use the first solution but it shows time limit exceed. Then I copy your first solution it is also shown time limit exceed. Did you pass the first one?

• The add time for 1st solution is O(n^2)

• For using ordered data structure, only need to search (value-s)<s elements.

class TwoSum {
private:
map<int,int> s;
public:
/** Initialize your data structure here. */
TwoSum() {

``````}

/** Add the number to an internal data structure.. */
s[number]++;
}

/** Find if there exists any pair of numbers which sum is equal to the value. */
bool find(int value) {
for(const auto& v : s){
int diff=value-v.first;
if(diff<v.first)
{
return false;
}
else if(diff==v.first && v.second>1){
return true;
}
else if(diff!=v.first && s.find(diff)!=s.end())
{
return true;
}
}
return false;
}
``````

};

• ``````# O(1) add time, O(n) find time, O(n) space
def __init__(self):
"""
"""
self.__num_dict = {}

"""
Add the number to an internal data structure..
:type number: int
:rtype: void
"""
if number in self.__num_dict:
self.__num_dict[number] += 1
else:
self.__num_dict[number] = 1

def find(self, value):
"""
Find if there exists any pair of numbers which sum is equal to the value.
:type value: int
:rtype: bool
"""
for num in self.__num_dict.keys():
complement = value - num
if complement in self.__num_dict:
# No duplicate element
if complement != num:
return True
# Check if there are two dupliate element can add together to target
elif self.__num_dict[num] > 1:
return True

return False
``````

• `Time Limit Exceeded`, looks like the big data is more add heavy than find. We should optimize find if in that case.

``````  # O(n)add time, O(1) find time, O(n^2) space
def __init__(self):
"""
"""
self.__nums = set()
self.__sums = set()

"""
Add the number to an internal data structure..
:type number: int
:rtype: void
"""
for num in self.__nums:
s = num + number
if s not in self.__sums:

if number not in self.__nums: