Given two unsorted arrays, find pairs whose sum is x in C++

We are given a problem statement that goes as: Given two unsorted arrays, find all pairs whose sum is x in C++. Basically, we are given a number X and we have to find pairs in the given two arrays, with one element from each array whose sum is equal to x. There can be multiple approaches to solve this problem. Let us look at some.

Let us say we have two unsorted arrays given as:

arr1=[5,3,8,6]
arr2=[4,3,2,1]

target=8
expected output : 5 3
                  6 2

Given two unsorted arrays, find all pairs whose sum is x in C++ solution

A simple approach can be to iterate over two loops and check the sum of all the possible pairs. If we find any such pair whose sum is equal to the given value, we print the pair, else, we continue.

BRUTE FORCE

Approach:

  1. Traverse one of the arrays and for each element of the array traverse the second array to find its corresponding element such that their sum is equal to the given value.
  2. If such an element exists, increase the counter by 1.
  3. Else, return 0.

Code:

#include <iostream>
using namespace std;


int main() {
    int arr1[]={5,3,8,6};
    int arr2[]={4,1,3,2};
    int target=8;
    
    for(int i=0;i<4;i++){
        for(int j=0;j<4;j++){
            if(arr1[i]+arr2[j]==target){
                cout<<arr1[i]<<" "<<arr2[j]<<endl;
            }
        }
    }
  return 0;
}

TIME COMPLEXITY: O(n*m)
SPACE COMPLEXITY: O(1)

 

EFFICIENT APPROACH USING HASHING

We use an unordered map for this purpose because the access time of the unordered map is 0(1). Note that we cannot use an unordered set because its access time is O(logN) and that will increase the overall time complexity to O(NlogN) from O(n).

Approach:

  1. We trade the time complexity with the space complexity. We use an unordered map to store the numbers of the first list.
    for(int i=0;i<4;i++){ 
        val[arr1[i]]++; 
    }
  2. Then we iterate over the next list and check if the corresponding value exists in the hashmap or not.
    for(int i=0;i<4;i++){ 
        int left=target-arr2[i]; 
        if(val.find(left)!=val.end()){ 
            cout<<left<<" "<<arr2[i]<<endl; 
        } 
    }
  3. We increment the counter if the pair exists.

Code:

#include <iostream>
#include<unordered_map>
using namespace std;


int main() {
    int arr1[]={5,3,8,6};
    int arr2[]={4,1,3,2};
    int target=8;
    unordered_map<int,int> val;

//insert all the elements of the first array
    for(int i=0;i<4;i++){
        val[arr1[i]]++;
    }

//find if the piar exists
    for(int i=0;i<4;i++){
        int left=target-arr2[i];
        if(val.find(left)!=val.end()){
            cout<<left<<" "<<arr2[i]<<endl;
        }
    }
    
  return 0;
}

TIME COMPLEXITY: O(n1+n2)  n1=size of arr1, n2=size of arr2.
SPACE COMPLEXITY: O(n1) where n1 is the size of the first array.

Note that both these approaches work for arrays with distinct sizes as well. Also, using the unordered map we can print repeated pairs as well.

READ MORE:

Find a number not present in second array from given two arrays in C++
Find the closest pair from two sorted arrays in Python

Leave a Reply

Your email address will not be published. Required fields are marked *