2 Sum – Count Pairs with given Sum in Sorted Array
You are given an integer target and an array arr[]. You have to find number of pairs in arr[] which sums up to target. It is given that the elements of the arr[] are in sorted order.
Note : pairs should have elements of distinct indexes.
Input: arr[] = [-1, 1, 5, 5, 7], target = 6
Output: 3
Explanation: There are 3 pairs which sum up to 6 : {1, 5}, {1, 5} and {-1, 7}.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) and (1, 1).
Input: arr[] = [-1, 10, 10, 12, 15], target = 125 Output: 0 Explanation: There is no such pair which sums up to 125.
- -10^5 <= target <=10^5
- 2 <= arr.size() <= 10^5
- -10^5 <= arr[i] <= 10^5
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 : Two Pointer Approach (O(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.
#include <iostream>
#include <algorithm>
using namespace std;
int countPairs(int arr[], int n, int target) {
int count = 0;
int left = 0, right = n - 1;
while (left < right) {
int sum = arr[left] + arr[right];
if (sum < target) {
left++;
} else if (sum > target) {
right--;
} else {
int leftVal = arr[left], rightVal = arr[right];
int leftCount = 0, rightCount = 0;
while (left <= right && arr[left] == leftVal) {
left++;
leftCount++;
}
while (left <= right && arr[right] == rightVal) {
right--;
rightCount++;
}
if (leftVal == rightVal) {
count += (leftCount * (leftCount - 1)) / 2;
} else {
count += leftCount * rightCount;
}
}
}
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(1)