find all pairs on integer array whose sum is equal to given number
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]]
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;}