Home » Data Structure » Hashing Coding Problems

Given an array A[] and number X, check for pair in A[] with sum X | using hashing O(n) time complexity | Set 1

In this article, we are going to check how we can use hashing to solve the two sum problem in O(n) time complexity?
Submitted by Radib Kar, on July 18, 2020

Prerequisite:

• Hashing data structure

Problem statement:

Given an array and a sum X, fins any pair which sums to X. Expected time complexity O(n).

Example:

Input array:
[4, -1, 6, 5, -2, 2]
Sum, X=2

Output:
Pair {4,-2}

Explanation:
4+(-2)=2 and thus the pair is {4,-2}

Solution:

Obviously, in brute force, we can solve it by checking each pair sums to X or not. In the worst case, it will take O(n²) which is too costly for the problem. Still, the algorithm would be like the following:

For i=0:n-1
    For j=i+1: n-1
        If arr[i]+arr[j]==X
            Return pair {arr[i],arr[j]}

To solve this efficiently, we will use hashing. What we need to create is a hash table which will be used as our lookup table. The idea is to lookup whether X-current_element exists in the hash table or not. If we find any element in the hash table, then obviously
{X-current_element, current_element} is our desired pair.

Now, we can create a lookup table by simply inserting each element. Then in another loop, we can start finding whether X-current_element is in the hash table or not. Following is the two-pass algorithm,

Create a hash table using set

unordered_set<int> myset;
//first pass->building the hash table
For i=0 to n-1
	current_element=arr[i]
	Add current_element to look up table, myset if it’s not there 
End for

Find the pair

//second pass-> finding the pair using the hash table built
For i=0 to n-1
	current_element=arr[i]
	if(X-current_element is in myset)
		the desired pair is { current_element , X-current_element } 
        and return 
End for

The time complexity of the algorithm is of course O(n) and space complexity is also O(n) for the hash table.

Now, we can further optimize the above algorithm into a single pass.

Instead of creating the hash table in a separate pass, we can do both searching and creating in one pass. The idea is if X-current_element is in the hash table then we are done, otherwise, add this current_element to the hash table.

So the algorithm would be:

//both searching and looking at a time
For i=0 to n-1
    current_element=arr[i]
    if(X-current_element is in myset)
        the desired pair is { current_element , X-current_element } 
        and return 
    Else
        Add current_element to myset
End for

So, how it guarantees to work?

We can show that by our example. Where input array is [4, -1, 6, 5, -2, 2]
If we have used the two-pass algorithm then, we have got {4,-2} as a pair where 4 would be the current_element and-2 would be the X-current_element.

But if we use the one-pass algorithm we would get the pair as {-2, 4} where -2 would be the current_element and 4 would be X-current_element.

The reason is when we have 4 as our current_element in our one-pass algorithm then the hash table is empty. Thus we simply add 4.

But when we process -2 as our current_element we have X-(-2) to look for which is 2-(-2) and 4 now exists. So the thing is the one pass is guaranteed to work. Only it will return the pair in reverse order.

The time & space complexity of the one-pass algorithm is of course same as the two-pass algorithm since it's big O notation.

C++ implementation:

#include <bits/stdc++.h>
using namespace std;

pair<int, int> find_pair_sum(vector<int> arr, int n, int X)
{
    unordered_set<int> myset;

    for (int i = 0; i < n; i++) {
        //pair exists current_element, X-current_element
        if (myset.find(X - arr[i]) != myset.end()) {
            return make_pair(arr[i], X - arr[i]);
        }
        //if arr[i] already not there
        else if (myset.find(arr[i]) == myset.end()) 
            myset.insert(arr[i]);
    }

    return make_pair(INT_MAX, INT_MAX);
}

int main()
{
    cout << "Enter number of input elements,n\n";
    int n;
    cin >> n;
 
    cout << "Enter the input elements\n";
    vector<int> arr(n);
 
    for (int i = 0; i < n; i++)
        cin >> arr[i];

    cout << "Enter sum, X\n";
    int X;
    cin >> X;

    pair<int, int> p = find_pair_sum(arr, n, X);
    if (p.first == INT_MAX && p.second == INT_MAX)
        cout << "No pairs found\n";
    else
        cout << "The pairs are : " << p.first << ", " << p.second << endl;

    return 0;
}

Output:

Enter number of input elements,n
6
Enter the input elements
4 -1 6 5 2 -2
Enter sum, X
2
The pairs are : -2, 4