Two Sum - Pair with given Sum
Given an array arr[] of n integers and a target value, the task is to find whether there is a pair of elements in the array whose sum is equal to target. This problem is a variation of 2Sum problem.
Input: arr[] = [0, -1, 2, -3, 1], target = -2 Output: true Explanation: There is a pair (1, -3) with the sum equal to given target, 1 + (-3) = -2.
Input: arr[] = [1, -2, 1, 0, 5], target = 0 Output: false Explanation: There is no pair with sum equals to given target.
- 1 ≤ arr.size ≤ 10^5
- 1 ≤ arr[i] ≤ 10^5
- 1 ≤ target ≤ 2*10^5
Approach 1 : Brute Force Approach Using Nested Loop
Brute Force approach involves using nested loops. The outer loop selects the starting element, while the inner loop calculates the sum with starting element. Check every possible pair of elements and see if their sum equals the target.
#include <iostream>
#include <vector>
using namespace std;
bool HasPairWithSum(vector<int> &arr, int target) {
int n = arr.size();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (arr[i] + arr[j] == target) {
return true;
}
}
}
return false;
}
int main() {
vector<int> arr = {0, -1, 2, -3, 1};
int target = -2;
if(HasPairWithSum(arr, target))
cout << "true";
else
cout << "false";
return 0;
}true
Time Complexity : O(N^2)
Space Complexity : O(1)
Approach 2 : Sorting and Binary Search – O(n*log(n)) time and O(1) space
We can also solve this problem using binary search. Since binary search works efficiently on sorted arrays, with a time complexity of O(log n), the first step is to sort the array. Then, for each element arr[i], we calculate its complement by subtracting it from the target value (i.e., target - arr[i]). After that, we use binary search to check if this complement exists in the subarray starting from the next index (i + 1). If we find the complement, we return true. If we go through all the elements without finding a valid pair, we return false.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool binarySearch(vector<int> &arr, int left, int right, int target){
while (left <= right){
int mid = left + (right - left) / 2;
if (arr[mid] == target)
return true;
if (arr[mid] < target)
left = mid + 1;
else
right = mid - 1;
}
return false;
}
bool HasPairWithSum(vector<int> &arr, int target){
sort(arr.begin(), arr.end());
for (int i = 0; i < arr.size(); i++){
int complement = target - arr[i];
if (binarySearch(arr, i + 1, arr.size() - 1, complement))
return true;
}
return false;
}
int main(){
vector<int> arr = {0, -1, 2, -3, 1};
int target = -2;
if (HasPairWithSum(arr, target))
cout << "true";
else
cout << "false";
return 0;
}true
Time Complexity : O(NlogN)
Space Complexity : O(1)
Approach 3 : Sorting + Two Pointer Approach (O(n log n) Time, O(1) Space)
This approach uses the two-pointer technique, which works efficiently when the array is sorted. So, the first step is to sort the array. Once sorted, we place one pointer at the start (left) and the other at the end (right) of the array. We then check the sum of the elements at these two pointers.
- If the sum matches the target value, we’ve found the pair we're looking for.
- If the sum is less than the target, we move the left pointer one step to the right to try a larger value.
- If the sum is greater than the target, we move the right pointer one step to the left to try a smaller value.
- This continues until we either find a matching pair or the pointers cross each other
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool HasPairWithSum(vector<int> &arr, int target){
sort(arr.begin(), arr.end());
int left = 0, right = arr.size() - 1;
while (left < right){
int sum = arr[left] + arr[right];
if (sum == target)
return true;
else if (sum < target)
left++;
else
right--;
}
return false;
}
int main(){
vector<int> arr = {0, -1, 2, -3, 1};
int target = -2;
if (HasPairWithSum(arr, target))
cout << "true";
else
cout << "false";
return 0;
}true
Time Complexity : O(N log N)
Space Complexity : O(1)
Approach 4 (Optimal Solution): Using Hash Set – O(n) time and O(n) space
Using hashing is a highly efficient way to solve the 2Sum problem. Instead of checking every possible pair, we can use a Hash Set to keep track of the numbers we’ve seen so far as we loop through the array. For each element, we compute its complement by subtracting it from the target (i.e., target - current number) and then check if that complement is already in the set. If it is, we’ve found a pair that adds up to the target. This method is much faster and allows us to solve the problem in linear time, or O(n).
Step-by-step breakdown- Initialize an empty Hash Set
- Loop through each element in the array
- Calculate the complement (target - current number).
- Check if this complement exists in the set
- If it exist, we have found the required pair.
- If it not exist, add the current number to the set.
- If no such pair is found by the end of the loop, return a message indicating that no pair exists.
#include <iostream>
#include <unordered_set>
using namespace std;
bool HasPairWithSum(int arr[], int size, int target) {
unordered_set<int> seen;
for (int i = 0; i < size; i++) {
int complement = target - arr[i];
if (seen.count(complement))
return true;
seen.insert(arr[i]);
}
return false;
}
int main() {
int arr1[] = {0, -1, 2, -3, 1};
int target1 = -2;
int arr2[] = {1, -2, 1, 0, 5};
int target2 = 0;
cout << "Example 1: " << (HasPairWithSum(arr1, 5, target1) ? "true" : "false") << endl;
cout << "Example 2: " << (HasPairWithSum(arr2, 5, target2) ? "true" : "false") << endl;
return 0;
}Example 1: true Example 2: false
Time Complexity : O(N)
Space Complexity : O(N)