Hashing: Given 2 arrays, and a value x, you need to find the pairs sum equal to the given value of x.

Problem Statement:

You are given 2 sorted arrays and a value k.

You need to find all pairs from both the array whose value is equal to x.

Example:

Input:

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

x = 8

Output: 2

The pairs are (4, 4) and (3, 5)

Solution 1: Brute force approach

Take 2 loops and check if the pair sum is equal to the given value.

Time Complexity: O(nm)
Space Complexity: O(1)

Solution 2: Hashing approach

We can solve this by hashing approach.

We use unordered set, store all element of the first element in the set.

Then for the elements of second array, subtract every element from x and check the result in hash table.

If the result is present, then increment count

Time Complexity: O(m+n)
Space Complexity: O(m)

Code Solution

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <unordered_set>
using namespace std;

int solution_1 (vector<int>& a, vector<int>& b, int x) 
{
    int count = 0;
    
    for (int i = 0; i < a.size(); i++) 
    {
        for (int j = 0; j < b.size(); j++) 
        {
            if ((a[i] + b[j]) == x) 
                count++;
        }
    }
    return count;
}


int solution_2 (vector<int>& a, vector<int>& b, int x) 
{
    int count = 0;
    int m = a.size();
    int n = b.size();
    
    unordered_set<int> st;
    
    for (int i = 0; i < a.size(); i++)
        st.insert(a[i]);
    
    for (int j = 0; j < b.size(); j++) 
    {

        if (st.find(x - b[j]) != st.end())
            count++;
    }
     
    return count;
}


int main() 
{
    vector<int> a = {1, 2, 3, 4};
    vector<int> b = {2, 3, 4, 5};
    
    int x = 8;

    cout << solution_1(a, b, x)<<endl;
    cout << solution_2(a, b, x);

    return 0;     
}

Output

2
2