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)

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).

Space complexity

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

References