find all pairs on integer array whose sum is equal to given number

Easy

Problem

Given an array of integers and a target sum k, count (or list) all pairs of indices i < j with arr[i] + arr[j] = k. Equal values at different indices form separate pairs.

Example 1

Input:  arr = [1, 5, 7, 1], k = 6
Output: 2

Pairs (1,5) at indices (0,1) and (5,1) at indices (1,3).

Example 2

Input:  arr = [1, 1, 1, 1], k = 2
Output: 6

Also asked as: two sum · pair with given sum

Test cases

Case 1

Input:    [1,5,7,-1,3], 6
Expected (any order): [[1,5],[-1,7]]

Case 2

Input:    [2,4], 10
Expected (any order): []

Case 3

Input:    [0,6,2,4], 6
Expected (any order): [[0,6],[2,4]]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution2 approaches

1. Hash set (unsorted)

Time O(n)Space O(n)

For each x check if (target − x) was already seen.

function pairs(a, target) {
const seen = new Set(), out = [];
for (const x of a) {
if (seen.has(target - x)) out.push([target - x, x]);
seen.add(x);
}
return out;
}

2. Sort + two pointers

Time O(n log n)Space O(1)

Sort, then shrink from both ends. O(1) extra space; also lists pairs in order.

function pairs(a, target) {
a.sort((x, y) => x - y);
let l = 0, r = a.length - 1;
const out = [];
while (l < r) {
const s = a[l] + a[r];
if (s === target) { out.push([a[l], a[r]]); l++; r--; }
else if (s < target) l++;
else r--;
}
return out;
}