Count pairs with given sum

JavaView on GFG

Time: O(n)

Space: O(n)

Problem Overview

Count pairs in array with given sum.

See our study guide for structured GFG and LeetCode practice.

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?