2 Sum Count pairs with given sum
Given an array arr[] of integers and a target value target, count the number of pairs (i, j) such that arr[i] + arr[j] == target and i != j.
Input: arr[] = [1, 5, 7, -1, 5], target = 6 Output: 3 Explanation: Valid pairs: (1,5), (7,-1), (1,5)
Input: arr[] = [1, 1, 1, 1], target = 2 Output: 6 Explanation: Pairs with sum 2 are (1, 1), (1, 1), (1, 1), (1, 1), (1, 1), (1, 1).
Input: arr[] = [10, 12, 10, 15, -1], target = 125 Output: 0 Explanation: There is no valid pair.
- 1 ≤ arr.size ≤ 10^5
- -10^4 <= arr[i] <= 10^4
- 1 <= target <= 10^4
Approach 1 : Brute Force Approach Using Nested Loop
The most straightforward approach is to generate all possible pairs and check if their sum equals the given target value (arr[i] + arr[j] == target). If it does, increment the count variable.
#include <iostream>
using namespace std;
int countPairs(int arr[], int n, int target) {
int cnt = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (arr[i] + arr[j] == target) {
cnt++;
}
}
}
return cnt;
}
int main() {
int arr[] = {1, 5, 7, -1, 5};
int target = 6;
int n = sizeof(arr) / sizeof(arr[0]);
cout << countPairs(arr, n, target) << endl;
return 0;
}3
Time Complexity : O(N^2)
Space Complexity : O(1)
Approach 2 : 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 arr[left] + arr[right] < target: Move the left pointer to the right to increase the sum.
- If arr[left] + arr[right] > target: Move the right pointer to the left to decrease the sum.
- arr[left] + arr[right] = target: We have found a pair whose sum is equal to target. We can find the product of the count of both the elements and add them to the result.
To know more about the implementation, please refer 2 Sum – Count Pairs with given Sum in Sorted Array
Approach 3 (Optimal Solution): Using Hash Map or Dictionary – 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 Map or Dictionary 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 check if it’s in the map. If it is, increment the count variable by the occurrences of complement in map. This method is much faster and allows us to solve the problem in linear time, or O(n).
#include <iostream>
#include <unordered_map>
using namespace std;
int countPairs(int arr[], int n, int target) {
unordered_map<int, int> freq;
int count = 0;
for (int i = 0; i < n; i++) {
int complement = target - arr[i];
if (freq.find(complement) != freq.end()) {
count += freq[complement];
}
freq[arr[i]]++;
}
return count;
}
int main() {
int arr[] = { -1, 1, 5, 5, 7 };
int target = 6;
int n = sizeof(arr) / sizeof(arr[0]);
cout << countPairs(arr, n, target) << endl;
return 0;
}3
Time Complexity : O(N)
Space Complexity : O(N)