Pair with given sum in a sorted array
Problem Description
Given a sorted array of integers, find the number of pairs of distinct indices whose elements sum up to a given target. The array is sorted in non-decreasing order.
Example:
- Input:
arr[] = [-1, 1, 5, 5, 7]
,target = 6
- Output:
3
- Explanation: The pairs that sum to
6
are{1, 5}
,{1, 5}
, and{-1, 7}
.
Solution Code
class Solution {
int countPairs(int arr[], int target) {
int left = 0; // Pointer to the start of the array
int right = arr.length - 1; // Pointer to the end of the array
int count = 0; // To store the count of valid pairs
while (left < right) {
int sum = arr[left] + arr[right];
if (sum == target) {
// If the sum equals the target, count all valid pairs
if (arr[left] == arr[right]) {
// If all elements between left and right are the same, calculate the number of pairs
int n = right - left + 1;
count += n * (n - 1) / 2; // Combination formula for nC2
break;
} else {
// Count all pairs with the same value as arr[left] and arr[right]
int leftVal = arr[left];
int rightVal = arr[right];
int leftCount = 0, rightCount = 0;
while (left < arr.length && arr[left] == leftVal) {
left++;
leftCount++;
}
while (right >= 0 && arr[right] == rightVal) {
right--;
rightCount++;
}
count += leftCount * rightCount;
}
} else if (sum < target) {
left++; // Move left pointer to increase the sum
} else {
right--; // Move right pointer to decrease the sum
}
}
return count;
}
}
Hint
- Use a two-pointer approach to efficiently find pairs that sum to the target. Handle duplicate elements carefully to count all valid pairs.
Approach Name
Two-Pointer Technique with Handling Duplicates
Intuition
Since the array is sorted, we can use two pointers, one at the beginning (left
) and one at the end (right
). By adjusting the pointers based on whether the sum of the elements at the pointers is less than, equal to, or greater than the target, we can efficiently find all valid pairs. Special care is taken to handle duplicate elements to ensure all valid pairs are counted.
Algorithm
- Initialize two pointers,
left
at the start andright
at the end of the array. - While
left < right
:- Calculate the sum of the elements at
left
andright
. - If the sum equals the target:
- If the elements at
left
andright
are the same, calculate the number of pairs using the combination formulanC2
. - Otherwise, count all pairs with the same values as
arr[left]
andarr[right]
.
- If the elements at
- If the sum is less than the target, move the
left
pointer to the right. - If the sum is greater than the target, move the
right
pointer to the left.
- Calculate the sum of the elements at
- Return the total count of valid pairs.
Test Input
-1 1 5 5 7, 6
Complexity Analysis
- Time Complexity: O(n), where
n
is the number of elements in the array. Each element is processed at most once. - Space Complexity: O(1), as we are using a constant amount of extra space.
This solution efficiently counts the number of valid pairs using a two-pointer approach, ensuring optimal performance for the given constraints.