Pairs with Positive Negative values | GeeksforGeeks | Hashing data structure | Leetcode DSA series

This is the video under the series of DATA STRUCTURE & ALGORITHM in a HASHING Playlist. We are going to solve the problem "Pairs with Positive Negative values" from geeks for geeks which are solved by using unordered_map, vector, map in c++.

Given an array of distinct integers, print all the pairs having positive value and negative value of a number that exists in the array.
NOTE: If there is no such pair in the array, return empty array.

Input:
n = 6
a[] = {1, -3, 2, 3, 6, -1}
Output:
-1 1 -3 3

We also Provide courses on Competitive Programming and Data structure and Algorithms. Please see our Full Playlist on our Channel.
----------------------------------------------------------------------------------------

----------------------------------------------------------------------------------------
*Follow me *
----------------------------------------------------------------------------------------

►Our Playlists on:-

------------------------------------------------------------------------

🌟 Please leave a LIKE ❤️ and SUBSCRIBE for more AMAZING content! 🌟

✨ Tags ✨
how to find Pairs with Positive Negative values
question asked in Goldman Sachs interview
how to crack Goldman Sachs online test
how to crack Google Interview
off-campus placement
how to learn to code for beginners
Practice Hashing data structure
hashing in data structure
Best Telegram channel for Off-campus Placement drive
hashing in a data structure in Hindi
unordered_map
vector in cpp

#hashing #geeksforgeeks #programming

[Man_of_Culture.]

Solved it without extra space .Use sorting and two pointer algo

sort(a, a+n);
int i=0, j=n-1;
vector<int>res;
while(i<j)
{
if(a[i]+a[j]==0)
{
res.insert(res.begin(), a[j]);
res.insert(res.begin(), a[i]);
i++;
j--;
}
else if(abs(a[i])>abs(a[j]))
i++;
else
j--;
}
return res;

[oqant]

was solving this....1hr passed ...1.5hr passed still not got successful after trying for 1hr +40
I made a successful submission without looking at a single hint

🙂feeling very confident
A big thanks to u bhaiya❤

class Solution{
public:
vector<int> PosNegPair(int a[], int n) {
vector<int>ans;
unordered_map<int, int>mp;
sort(a, a+n);
for(int i=0;i<n;i++){
if(mp[-a[i]]>=1){
int key=abs(a[i]);
ans.push_back(-key);
ans.push_back(key);
int oppo=-a[i];
mp[oppo]--;
}
else{
mp[a[i]]++;
}
}
return ans;
}
};

[mayankkumar]

KHUD SOLVE KARLIYA BHAI CONFIDENCE INFINITTY PAR HAI LOVE FROM UTTARAKHAND

[amanmotghare]

Sir ji I have tried any my 80% of approach is similar to your approach
the thing is I am not very pro in implementation but I have tried

[sambhavsharma]

2nd Approach Solution :-

class Solution{
public:
vector<int> PosNegPair(int arr[], int n) {
unordered_map<int, int> pos;
unordered_map<int, int> neg;
vector<int> ans;
for(int i=0; i<n; i++){
if(arr[i]>0){
pos[arr[i]]++;
}else neg[arr[i]]++;
}
for(auto it=pos.begin(); it!=pos.end(); it++){
int key = it->first;
int value = it->second;

auto negItr = neg.find(-key);
int negValue = negItr->second;
int data = min(value, negValue);
for(int i=0; i<(data*2); i++){
ans.push_back(key);
}
}
}
sort(ans.begin(), ans.end());
for(int i=0; i<ans.size();i++){
if(i%2==0) ans[i] *= -1;
}
return ans;
}
};

[aritrakumarbara]

public List<Long> PosNegPair(long a[], long n)
{
Map<Long, Integer> freq = new HashMap<>();
for (long i : a) {
freq.put(i, freq.getOrDefault(i, 0) + 1);
}
List<Long> pair = new ArrayList<>();

for (long i : a) {
int cnt = 2 * Math.min(freq.get(i), freq.getOrDefault(-i, 0));
freq.put(-i, 0);
while (cnt-- > 0) {
if (i < 0)
i = -i;
pair.add(i);
}
}
pair.sort(null);
for (int i = 0; i < pair.size(); i += 2) {
pair.set(i, pair.get(i) * -1);
}
return pair;
} // Sir we can do it with a single map also

[harshexploring]

Thanks AA lot bhaiya
This playlist is very helpful
Love from iitkgp

[_mohammadahadkhan]

public:
vector<int> PosNegPair(int a[], int n) {
unordered_map<int, int > umap;
for(int i=0;i<n;i++){
umap[a[i]]++;
}
vector<int> ans;
sort(a, a+n);
for(int i=0; i<n;i++){
if(a[i]>0){
if(umap[a[i]] && umap[a[i]*(-1)]){

ans.push_back(abs(a[i]));
umap[a[i]]--;
umap[a[i]*(-1)]--;
}
}
}
return ans;
}
};

Here is use only one unordered map, as searching, insertion takes o(1) on average this solution is better than using map. This is Correct solution Right.

[AnjaliSingh-ykyc]

vector<int> PosNegPair(int a[], int n) {
unordered_map<int, int> mp;
set<int> s;
vector<int> v;
for(int i=0; i<n; i++){
mp[a[i]]++;
if(a[i]>0)
s.insert(a[i]);
}
int m;
for(auto a : s){
int x= -(a);
if(mp[a]<=mp[x])
m=mp[a];
else
m=mp[x];
for(int i=1;i<=m;i++)
{
v.push_back(x);
v.push_back(a);
}

}
return (v);
}

[Ramneet]

vector<int> PosNegPair(int a[], int n) {
unordered_map<int, int>m;
sort(a, a+n);
for(int i=0;i<n;i++){
if(a[i]>0){
m[a[i]]++;
}
}
vector<int>ans;
for(int i=n-1;i>=0;i--){
if(a[i]<0){
if(m[abs(a[i])]){
m[abs(a[i])]--;
ans.push_back(a[i]);
ans.push_back(abs(a[i]));
}
}
}
return ans;
}
I did this solution 100 accurate!!

[manojgollapelli]

I think for 3rd solution, there is no specific use of ordered map which can also be replaced with unordered map...

any way nice logic brother.. I m feeling more confident, Thank you brother

[prabhatmishra]

Bhayia why can't we use unordered map? Your algorithm is taking more time than mine.
since we already sorted negative values so what is the need of ordered map, since searching time is more in ordered map? attaching code in reply

[dudlavarumakanth]

prince sir, aap internship ke bar me bath karo
what will be the process of internships
what are skills one need to be gained to crack internships

What we need to learn.
and many
please prince bhai make a video on this

[shashankkumar]

its already written in the question that it has distinct elemets then why to count frquency

[pragatikumari]

m[data ] represent here ....in last few vedio u used either find method or count method

[rockzz]

in 27th line of code, while loop should be used ....Here there are distinct elements that's why frequency of all elements is 1 and its working

[yash]

The approach i tried was making a map and storing values then i searched if (-key) is present or not and if present, print out -key and key.

[uditsethi]

hey brother when u explained the sol using unordered set it will work fine as per solution as in question it is given to us the array contains all distinct integers means no repetitive element is present in array.

[keshavagarwal]

can anyone give the solution of method 2??I am trying but i am not able to solve completely.

[amitraj-vuoe]

your video and explanation is great !!! but u deserve more views nd subscriber.... thank u for this video