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

Pair of Positive Negative Values in an Array


Reading Time - 2 mins

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:

Pair of Positive Negative Values in an Array

Now we will iterate the array,

The orange color shows the current index,

Pair of Positive Negative Values in an Array Pair of Positive Negative Values in an Array

Pair of Positive Negative Values in an Array

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