Home » Technical Interview Questions » Hashing Interview Questions » Pair of Positive Negative Values in an Array

# Pair of Positive Negative Values in an Array

In pair of positive negative values in an array problem we have given an array A of distinct integers, print all the pairs having positive value and negative value of a number that exists in the array. We need to print pairs in order of their occurrences. A pair whose any element appears first should be printed first.

## Example

Input:

`A[]={2, 3, -1, -2, 9, 1}`

Output:

`Pairs having positive value and negative in the array are: -2 2 -1 1`

## Approach 1: Brute force

For every element A[i] in the input array, check if –A[i] is present in the array with an index greater than I if present then prints this pair.

### Algorithm

1. Run a loop for I in range 0 to n-1
1. Run a loop for j in range i+1 to n-1
1. If A[i] is equal to -A[j], then print this pair.
2. Return.

### C++ program for finding Pair of Positive Negative Values in an Array

```#include <bits/stdc++.h>
using namespace std;
void printPairs(vector<int> &A)
{
int n = A.size();
cout << "Pairs having positive value and negative in the array are: ";
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
if (A[i] == -A[j])
{
if (A[i] <= 0)
{
cout << A[i] << " " << (-A[i]) << " ";
}
else
{
cout << (-A[i]) << " " << A[i] << " ";
}
}
}
}
cout << endl;
return;
}
int main()
{
vector<int> A = {2, 3, -1, -2, 9, 1};
printPairs(A);
return 0;
}
```
`Pairs having positive value and negative in the array are: -2 2 -1 1`

### JAVA program for finding Pair of Positive Negative Values in an Array

```public class Main
{
static void printPairs(int[] A)
{
int n = A.length;
System.out.print("Pairs having positive value and negative in the array are: ");
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
if (A[i] == -A[j])
{
if (A[i] <= 0)
{
A[i]=-A[i];
}
System.out.print(A[i]+" -"+A[i]+" ");
}
}
}
return;
}
public static void main(String[] args) {
int[] A={2, 3, -1, -2, 9, 1};
printPairs(A);
}
}
```
`Pairs having positive value and negative in the array are: 2 -2 1 -1`

### Complexity Analysis

#### Time complexity

We are using two nested loops, both of size n. So the total time complexity is O(N^2)

READ  Find all permuted rows of a given row in a matrix

#### Space complexity

We are not using any extra space so the space complexity is O(1)

## Approach 2: Using hashing

### Main idea

We can store which elements are present in the array in a hash table. Now for each element A[i] in the array, check if –A[i] in the hash table has a value of 1 or not, if it is 1 then print this pair and decrement value of A[i] and –A[i] in the hash table by 1 so that we will not print the same pair twice.

### Algorithm

1. Initialize a hash table.
2. Store the frequency of each element in the hash table.
3. Run a loop for I in range 0 to n-1
1. If –A[i] has a value of 1 in the hash table, then print this pair and decrement the value of A[i] and –A[i] by 1.

### Understand with example

Let’s take input array A[]={2, 3, -1, -2, 9, 1}

So our hash table we look like this: Now we will iterate the array,

The orange color shows the current index,      So the final output is: -2 2 -1 1

### C++ program for finding Pair of Positive Negative Values in an Array

```#include <bits/stdc++.h>
using namespace std;
void printPairs(vector<int> &A)
{
int n = A.size();
unordered_map<int, int> hash_table;
for (int i = 0; i < n; i++)
{
hash_table[A[i]]++;
}
cout << "Pairs having positive value and negative in the array are: ";
for (int i = 0; i < n; i++)
{
if (hash_table[-A[i]] == 1)
{
if (A[i] <= 0)
{
cout << A[i] << " " << (-A[i]) << " ";
}
else
{
cout << (-A[i]) << " " << A[i] << " ";
}
hash_table[A[i]]--;
hash_table[-A[i]]--;
}
}
cout << endl;
return;
}
int main()
{
vector<int> A = {2, 3, -1, -2, 9, 1};
printPairs(A);
return 0;
}
```
`Pairs having positive value and negative in the array are: -2 2 -1 1`

### JAVA program for finding Pair of Positive Negative Values in an Array

```import java.util.*;
public class Main
{
static void printPairs(int[] A)
{
int n = A.length;
HashMap<Integer,Integer> hash_table = new HashMap<Integer,Integer>();
for (int i = 0; i < n; i++)
{
hash_table.put(A[i],1);
}
System.out.print("Pairs having positive value and negative in the array are: ");
for (int i = 0; i < n; i++)
{
if(hash_table.containsKey(-1*A[i]) && hash_table.get(-1*A[i])==1)
{
if (A[i] <= 0)
{
A[i]*=-1;
}
System.out.print(A[i]+" -"+A[i]+" ");
hash_table.put(A[i],0);
hash_table.put(-1*A[i],0);
}
}
return;
}
public static void main(String[] args) {
int[] A={2, 3, -1, -2, 9, 1};
printPairs(A);
}
}
```
`Pairs having positive value and negative in the array are: -2 2 -1 1`

### Complexity Analysis

#### Time complexity

We are iterating the whole array twice, so the time complexity is O(N).

READ  Find sum of non-repeating elements (distinct) elements in an array

#### Space complexity

We are using a hash table, so space complexity is O(N).

References

 Array Interview Questions Graph Interview Questions LinkedList Interview Questions String Interview Questions Tree Interview Questions