Need help with this Array Question

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.

2 Likes

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.

1 Like

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;
}

1 Like

Ya hetp it will.work perfectly…

1 Like

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 ? :stuck_out_tongue_winking_eye:

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

Not sure if thats correct.

2 Likes

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.

1 Like

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. :smiley: