Count Pairs With Given Sum

Easy
627.

Count Pairs With Given Sum

Count Pairs With Given Sum is an easy coding problem on arrays and hash table, asked in Amazon, TCS, Wipro and Zoho interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @param {number} target
 * @return {number}
 */
var countPairsWithSum = function(arr, target) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

  1. Hint 1

    The nested double loop is O(n²). A single pass with a frequency map does better.

  2. Hint 2

    When you reach arr[i], how many earlier elements equal target - arr[i]?

  3. 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

  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

Java

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