In this article, we have explained different approaches to solve the Two Sum Problem using techniques like Binary Search, Hash Map and others.

Table of contents:

1. Problem Statement: Two Sum
2. Naive Approach
3. Improved Approach using Binary Search
4. Optimal Approach using Hash Map

To find all pairs, go through this problem.

Modified version of this problem which you should try: Two Sum Problem in BST
A variant of this problem is the Problem 1 on Leetcode (1. Two Sum).

Let us get started with Two Sum Problem.

Problem Statement: Two Sum problem

The problem statement is: We are given a list of N elements and a number M. We have to find or check if two elements in the given list whose sum is M.

List = [a₁, a₂, ... , a_N]

So, if the two elements are a_i and a_j, then:

a_i + a_j = M

Example:

Given numbers = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1]

We have presented two approaches to find the two elements:

• Naive Approach
• Improved Approach using Binary Search
• Optimal Approach using Hash Map

Naive Approach

The idea is to pick any element A from the list and then, traverse the entire list using linear search to an element M-A. We need to do this for all N elements.

The steps are:

• Step 1: Take an element a_i in list
• Step 2: Linear search the list to find the element M-a_i
• Perform the above two steps for all elements in the list

Time Complexity: O(N²)

This is because for each element, we have to traverse the list which takes O(N) time and there are N elements.

Space Complexity: O(1)

Space wise this approach is optimal.

Pseudocode:

int two_sum(int list, int sum)
{
    int length = length_of(list);
    int count = 0;
    
    for(int i = 0; i<length; i++)
        for(int j = i+1; j<length; j++)
            if(list[i] + list[j] == sum)
                print(list[i], list[j]);
}

Implementation:

#include <bits/stdc++.h> 
using namespace std; 
 
void two_sum(int arr[], int n, int sum) 
{ 
    int count = 0; 
    for (int i=0; i<n; i++) 
        for (int j=i+1; j<n; j++) 
            if (arr[i]+arr[j] == sum) 
                cout << arr[i] << " , " << arr[j] << endl; 
} 
int main() 
{   int n;
    int a[100];
    cout<<"enter the size of array"<<endl;
    cin>>n;
    cout<<"enter the array"<<endl;
    for(int i=0;i<n;i++)
    {
    cin>>a[i];
    }
    
    int sum;
    cout<<"enter the sum:"<<endl;
    cin>>sum;
    cout << "The pairs= " 
         << two_sum(a, n, sum); 
    return 0; 
}

Improved Approach using Binary Search

The idea is to improve over the naive approach by sorting the list as a pre-processing step and then, use Binary Search instead of Linear Search.

The steps are:

• Sort the list of N elements
• For a given element a_i, find the element M - a_i in the list using Binary Search
• Do the above step for each element in the list

Time Complexity: O(N logN)

This is because Sorting will take O(N logN) time if you choose an optimal sorting algorithm like Quick Sort. Following this, Binary Search takes O(logN) time and we have to do Binary Search for N elements.

Space Complexity: O(1) if the sorting algorithm has O(1) space complexity.

Pseudocode:

int two_sum(int list, int sum)
{
    int length = length_of(list);
    int count = 0;
    
    Sort(list)
    
    for(int i = 0; i<length; i++)
        if(BinarySearch(list, sum - list[i]) == true)
            print(a[i], sum-a[i])
}

Optimal Approach using Hashmap

The idea is to store all elements in a Hashmap and then, traverse the list one by one. For each element a_i, we will search for the element M - a_i in the Hash Map which takes constant time O(1).

The steps are:

• Store the list of N elements in a hash map
• For a given element a_i, find the element M - a_i in the Hash Map
• Do the above step for each element in the list

Time Complexity: O(N)

Converting the list to a hashmap takes linear time. Search for a given element takes constant time O(1) but we have to do this for all N elements on average.

Space Complexity O(N)

The space requirement of a HashMap is the total number of elements to be inserted.

Pseudocode:

int two_sum(int a[], int sum) 
{ 
    int length = length_of(a);
    hashmap m;
    for (int i=0; i<length; i++) 
        if a[i] is not in m
            add a[i] to m with value 1 (a[i], 1)
        else
            increment value of a[i] (a[i], value++)

	int count = 0; 
	for (int i=0; i<length; i++) 
	{ 
        if(sum - a[i] is in m)
            count = count + value of sum-a[i]
		if (sum-a[i] == a[i]) 
			count--;  // to ignore duplicates
	} 

	return count/2; // as all pair has been counted twice
}

Implementation:

#include <bits/stdc++.h> 
using namespace std; 
int two_sum(int a[], int n, int sum) 
{ 
	unordered_map<int, int> m; 
	for (int i=0; i<n; i++) 
		m[a[i]]++; 

	int count = 0; 
	for (int i=0; i<n; i++) 
	{ 
		count += m[sum-a[i]]; 
		if (sum-a[i] == a[i]) 
			count--; 
	} 

	return count/2; 
} 
int main() 
{ 
	int arr[] = {2,4,5,1,0} ; 
	int n = sizeof(arr)/sizeof(arr[0]); 
	int sum = 6; 
	cout << "the number of pairs are = "
		<< two_sum(arr, n, sum); 
	return 0; 
}

With this article at OpenGenus, you must have the complete idea of solving Two Sum problem.