Count Pairs With Given Sum — Solution in Python, Java & C++
Count Pairs With Given Sum solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Count Pairs With Given Sum is an easy coding problem on arrays and hash table, asked in Amazon, TCS, Wipro and Zoho interviews.
- Difficulty: Easy
- Topics: Arrays, Hash Table
- Asked at: Amazon, TCS, Wipro, Zoho
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an array arr and an integer target, count the pairs of indices (i, j) with i < j and arr[i] + arr[j] == target.
Pairs are counted by position, so repeated values contribute several pairs.
Example 1
Input: arr = [1,5,7,-1,5], target = 6
Output: 3
Explanation: (1,5), (7,-1) and (1,5) again with the second 5.
Example 2
Input: arr = [1,1,1,1], target = 2
Output: 6
Explanation: Every one of the six index pairs sums to 2.
Example 3
Input: arr = [10,12,10,15,-1], target = 125
Output: 0
Constraints
1 <= arr.length <= 100000-100000 <= arr[i] <= 100000-200000 <= target <= 200000
Hints for Count Pairs With Given Sum
Hint 1
The nested double loop is O(n²). A single pass with a frequency map does better.
Hint 2
When you reach
arr[i], how many earlier elements equaltarget - arr[i]?Hint 3
Count the match before inserting the current element, or an element pairs with itself.
How to solve Count Pairs With Given Sum
For each element, the partner it needs is fixed: target - x. Keeping a running tally of everything seen so far turns the search for partners into a single lookup.
Approach
- Keep a map from value to how many times it has appeared so far.
- For each
x, addseen[target - x](zero if absent) to the answer. - Then increment
seen[x]and continue.
Why it works
Counting before inserting means every pair is attributed exactly once — at its later index — so no pair is double counted and no element pairs with itself. Repeated values are handled naturally because the map stores counts, not just presence.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Inserting
xbefore the lookup makesxits own partner whenever2x == target. - Using a set instead of a count map reports
[1,1,1,1]as one pair rather than six.
Reference solution
Python
from typing import List
def countPairsWithSum(arr: List[int], target: int) -> int:
seen = {}
total = 0
for x in arr:
total += seen.get(target - x, 0)
seen[x] = seen.get(x, 0) + 1
return totalJava
public static int countPairsWithSum(int[] arr, int target) {
Map<Integer, Integer> seen = new HashMap<>();
int total = 0;
for (int x : arr) {
Integer c = seen.get(target - x);
if (c != null) total += c;
seen.put(x, seen.getOrDefault(x, 0) + 1);
}
return total;
}C++
int countPairsWithSum(vector<int>& arr, int target) {
unordered_map<int, int> seen;
int total = 0;
for (int x : arr) {
auto it = seen.find(target - x);
if (it != seen.end()) total += it->second;
seen[x]++;
}
return total;
}JavaScript
var countPairsWithSum = function(arr, target) {
var seen = {}, total = 0;
for (var i = 0; i < arr.length; i++) {
var need = String(target - arr[i]);
if (seen[need] !== undefined) total += seen[need];
var key = String(arr[i]);
seen[key] = (seen[key] === undefined ? 0 : seen[key]) + 1;
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets