875914. 2 Sum – Count distinct pairs with given sum
2 Sum – Count distinct pairs with given sum
Slug: 2-sum-count-distinct-pairs-with-given-sum
Difficulty: Easy
Id: 875914
Topic Tags: Arrays, Data Structures, Hash
Company Tags: None
Summary
Given an array of integers and a target sum, count the number of distinct pairs that add up to the given sum. This problem involves arrays and hash data structures, making it a classic example of a hash-based solution.
Detailed Explanation
The approach to this problem is to use a hash map (or dictionary) to store the frequencies of each element in the array. Then, for each element in the array, check if there exists another element that, when added together with the current element, equals the target sum.
Here's a step-by-step breakdown:
- Create an empty hash map.
- Iterate through the array and insert each element into the hash map along with its frequency (i.e., how many times it appears in the array).
- For each element in the array, check if there exists another element that, when added together with the current element, equals the target sum.
- If such a pair is found, increment a counter variable to keep track of the number of distinct pairs that add up to the given sum.
- Return the count as the final result.
Here's an ASCII art diagram illustrating the algorithm:
+---------------+
| Iterate array |
+---------------+
|
v
+---------------+
| Insert into hash |
| map (freq = 1) |
+---------------+
|
v
+---------------+
| Check for pairs |
| that add up to sum|
+---------------+
|
v
+---------------+
| Increment counter |
+---------------+
|
v
+---------------+
| Return count as result |
+---------------+
The time complexity of this algorithm is O(n), where n is the size of the input array. The space complexity is also O(n) due to the hash map.
Optimized Solutions
Java
import java.util.HashMap;
import java.util.Map;
public class Solution {
public int countPairs(int[] arr, int sum) {
Map<Integer, Integer> freqMap = new HashMap<>();
int count = 0;
for (int num : arr) {
if (freqMap.containsKey(sum - num)) {
count++;
}
freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
}
return count;
}
}