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:**

**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 ^{2})* 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

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.