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

  1. Initialize two pointers, left at the start and right at the end of the array.
  2. While left < right:
    • Calculate the sum of the elements at left and right.
    • If the sum equals the target:
      • If the elements at left and right are the same, calculate the number of pairs using the combination formula nC2.
      • Otherwise, count all pairs with the same values as arr[left] and arr[right].
    • 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.
  3. 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.