Pair with given sum in a 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. 

Examples :

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: There are 6 pairs which sum up to 2 : {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 4.

Constraints:
-10⁵ <= target <=10⁵
 2 <= arr.size() <= 10⁵
-10⁵ <= arr[i] <= 10⁵

Approach 01:

#include <vector>
#include <unordered_map>
using namespace std;

class Solution {
public:
    int countPairs(vector<int>& numbers, int targetSum) {
        unordered_map<int, int> frequencyMap;  // Tracks the frequency of each number encountered
        int pairCount = 0;  // Stores the count of valid pairs

        for (int number : numbers) {
            int complement = targetSum - number;  // Determine the complement for the current number
            if (frequencyMap.find(complement) != frequencyMap.end()) {
                pairCount += frequencyMap[complement];  // Increment pair count by frequency of the complement
            }
            frequencyMap[number]++;  // Update the frequency map for the current number
        }

        return pairCount;
    }
};

class Solution:
    def countPairs(self, numbers, targetSum):
        frequencyMap = {}  # Tracks the frequency of each number encountered
        pairCount = 0  # Stores the count of valid pairs

        for number in numbers:
            complement = targetSum - number  # Determine the complement for the current number
            if complement in frequencyMap:  # Check if the complement exists
                pairCount += frequencyMap[complement]  # Increment pair count by frequency of the complement
            if number in frequencyMap:  # Update the frequency map for the current number
                frequencyMap[number] += 1
            else:
                frequencyMap[number] = 1

        return pairCount

Time Complexity:

• Single Iteration Over the Array:

  The algorithm iterates over the numbers array once, contributing \( O(n) \), where \( n \) is the size of the array.

• Hash Map Operations:

  Each lookup and insertion in the hash map has an average time complexity of \( O(1) \). These operations occur \( n \) times during the iteration.

• Overall Time Complexity:

  \( O(n) \), as the single iteration and hash map operations dominate.

Space Complexity:

• Hash Map Storage:

  The hash map can store up to \( n \) unique keys, requiring \( O(n) \) space in the worst case.

• Auxiliary Variables:

  Constant space is used for variables like pairCount and complement.

• Overall Space Complexity:

  \( O(n) \), dominated by the space used by the hash map.