Count Pairs With Given Sum — Easy Problem & Solution

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

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

1. Keep a map from value to how many times it has appeared so far.
2. For each x, add seen[target - x] (zero if absent) to the answer.
3. 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 x before the lookup makes x its own partner whenever 2x == 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 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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Special Array I Easy
• Type of Triangle Easy
• Find the Losers of the Circular Game Easy
• Form Smallest Number From Two Digit Arrays Easy
• Delete Greatest Value in Each Row Easy
• The Employee That Worked on the Longest Task Easy