suppose there is an Array (**NOT SORTED**) of integers(+ve & -ve) and you have to find out if there are 2 element whose sum is 0 (zero).

for example:

given Array = {-1, 0, 1}

find if 2 elements inside the Arrays adds up to zero… in this case -1 and 1 will add up to zero and we return true. Else false.

**The size of the Array will be 10^9, we cant use STL and we have to do it in O(n) time complexity**

Problem source ? …

I don’t think Size of the array can be 1e9.

Anyways use 2 pointer approach.

The Question is from some Coding interview and he told me to solve the problem with Array size 10^9.

I guess he might have told you that the elements in the array are till the size 10^9. There is a misunderstanding.

That would require sorting the array since it is unsorted. So, cannot be done in O(N).

ohk… Use unordered maps then.

something like this:

```
unordered_map<int,int> mp;
for(int i:array){
if(mp[-i]+i==0)match found.
mp[i]=i;
}
```

Ya hetp it will.work perfectly…

He specifically told me that the Array will contain 10^9 elements.

I used the same solution but he told me that you can’t use STL ,means no containers.

I dont see any other way…

Make your own unordered map ?

Or use an array as map after shifting all the elements to make them +ve.

Not sure if thats correct.

Yes, not to nitpick, but AFAIK, unordered_maps are Amortized Constant for searching. Hence, making the overall complexity Amortized Linear. So, it will be still isn’t exactly Linear.

I told him that we can use 2 hash set one for +ve elements and one for -ve elements but he said no the array contains 10^9 elements.