Count pairs with given sum

JavaView on GFG

Time: O(n)

Space: O(n)

Intuition

Count pairs in array with given sum. HashMap frequency count.

Algorithm

1For each element x: count += freq[target-x]. Then freq[x]++.

Common Pitfalls

•Same as LC 1. Count pairs not elements. Process in one pass: check first, then add to map to avoid counting element with itself.

Count pairs with given sum.java

Java

// Approach: HashMap counting. For each element, check how many previous elements equal (target - current).
// Time: O(n) Space: O(n)
class Solution {
    
    int countPairs(int arr[], int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int count = 0;
        for (int i : arr) {
            int rem = target - i;
            if (map.containsKey(rem))
                count += map.get(rem);
            map.put(i, map.getOrDefault(i, 0) + 1);
        }
        return count;
    }
}

Was this solution helpful?