Skip to content

Latest commit

 

History

History
145 lines (95 loc) · 3.57 KB

07(Jan) Pair with given sum in a sorted array.md

File metadata and controls

145 lines (95 loc) · 3.57 KB

07. Pair with Given Sum in a Sorted Array

The problem can be found at the following link: Problem Link

Problem Description

You are given a sorted array arr[] of size n and an integer target. Your task is to find the number of pairs (i, j) such that arr[i] + arr[j] = target, where i and j are distinct indices (i ≠ j).

Examples:

Input:
arr[] = [-1, 1, 5, 5, 7], target = 6
Output:
3
Explanation:
The pairs (1, 5), (1, 5), and (-1, 7) sum up to 6.

Input:
arr[] = [1, 1, 1, 1], target = 2
Output:
6
Explanation:
There are 6 pairs: (1, 1), (1, 1), (1, 1), (1, 1), (1, 1), (1, 1).

Input:
arr[] = [-1, 10, 10, 12, 15], target = 125
Output:
0
Explanation:
No such pairs exist.

Constraints:

  • $2 <= arr.size() <= 10^5$
  • $-10^5 <= arr[i] <= 10^5$
  • $-10^5 <= target <= 10^5$

My Approach

  1. Efficient Pair Counting Using a Hash Map:

    • This approach leverages a hash map to store the frequency of elements as we traverse the array.
    • For each element x in the array, the complement required to form a pair is target - x.
    • We check if the complement exists in the hash map. If yes, the frequency of the complement contributes to the count of valid pairs.
    • Update the frequency of x in the hash map.

  2. Steps:

    • Initialize an empty hash map freq to store the frequency of elements.
    • Traverse the array and for each element:
      • Check if the complement (target - x) exists in the hash map.
      • Add the frequency of the complement to the result.
      • Update the frequency of the current element in the hash map.
    • Return the total count of pairs.

Time and Auxiliary Space Complexity

  • Expected Time Complexity: O(n), where n is the size of the array. Each element is processed once, and hash map operations (insertions and lookups) take O(1) on average.
  • Expected Auxiliary Space Complexity: O(n), as we store the frequency of up to n elements in the hash map.

Code (C++)

class Solution {
public:
    int countPairs(vector<int>& arr, int target) {
        unordered_map<int, int> freq;
        int res = 0;

        for (int num : arr) {
            int complement = target - num;
            if (freq.count(complement)) 
                res += freq[complement];
            
            freq[num]++;
        }

        return res;
    }
};

Code (Java)

class Solution {
    int countPairs(int[] arr, int target) {
        HashMap<Integer, Integer> freq = new HashMap<>();
        int res = 0;

        for (int num : arr) {
            res += freq.getOrDefault(target - num, 0);
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }

        return res;
    }
}

Code (Python)

class Solution:
    def countPairs(self, arr, target):
        freq = {}
        res = 0

        for num in arr:
            res += freq.get(target - num, 0)
            freq[num] = freq.get(num, 0) + 1

        return res

Contribution and Support

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: Any Questions. Let’s make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

📍Visitor Count