.png)
Find All Pairs with Given Sum
Problem Statement
You are given an array of integers and a target sum X.
Your task is to find all unique pairs in the array whose sum is equal to X.
A pair (a, b) is valid if a + b = X
Each pair should be considered once.
Example 1
Input
arr = [1, 5, 7, -1, 5]
X = 6
Output
(1, 5)
(1, 5)
(7, -1)
Example 2
Input
arr = [2, 4, 3, 5, 7, 8, 9]
X = 7
Output
(2, 5)
(3, 4)
Why This Problem Is Important
- Very frequently asked interview problem
- Tests array traversal
- Tests pair logic and indexing
- Foundation for Two Sum, Hashing & Two Pointer techniques
- Important for optimization thinking
Approaches Overview
| Approach | Technique | Time | Space |
|---|---|---|---|
| Approach 1 | Brute Force | O(n²) | O(1) |
| Approach 2 | Hash Map | O(n) | O(n) |
| Approach 3 | Two Pointer (Sorted Array) | O(n log n) | O(1) |
Approach 1: Brute Force
Idea
Check every possible pair in the array and print the pair if their sum equals X.
Algorithm
- Traverse array using two loops
- Fix first element at index i
- Check all elements after i
- If arr[i] + arr[j] == X, print the pair
Time & Space Complexity
- Time: O(n²)
- Space: O(1)
Implementations
C
#include
int main() {
int arr[] = {1, 5, 7, -1, 5};
int n = 5, X = 6;
for(int i = 0; i < n; i++) {
for(int j = i + 1; j < n; j++) {
if(arr[i] + arr[j] == X)
printf("(%d, %d)\n", arr[i], arr[j]);
}
}
return 0;
}
C++
#include
using namespace std;
int main() {
int arr[] = {1,5,7,-1,5};
int n = 5, X = 6;
for(int i = 0; i < n; i++) {
for(int j = i + 1; j < n; j++) {
if(arr[i] + arr[j] == X)
cout << "(" << arr[i] << ", " << arr[j] << ")\n";
}
}
return 0;
}
Java
public class PairSum {
public static void main(String[] args) {
int[] arr = {1,5,7,-1,5};
int X = 6;
for(int i = 0; i < arr.length; i++) {
for(int j = i + 1; j < arr.length; j++) {
if(arr[i] + arr[j] == X)
System.out.println("(" + arr[i] + ", " + arr[j] + ")");
}
}
}
}
Python
arr = [1,5,7,-1,5]
X = 6
for i in range(len(arr)):
for j in range(i+1, len(arr)):
if arr[i] + arr[j] == X:
print((arr[i], arr[j]))
JavaScript
let arr = [1,5,7,-1,5];
let X = 6;
for (let i = 0; i < arr.length; i++) {
for (let j = i + 1; j < arr.length; j++) {
if (arr[i] + arr[j] === X)
console.log(`(${arr[i]}, ${arr[j]})`);
}
}
Approach 2: Hash Map (Optimal for Unsorted Array)
Idea
For each element, check if (X - current element) exists in the map.
If yes, a valid pair is found.
Algorithm
- Create an empty hash map
- Traverse array
- For each element num
- Check if X - num exists in map
- If yes, print the pair
- Insert current element into map
Time & Space Complexity
- Time: O(n)
- Space: O(n)
Implementations
C++
#include
#include
using namespace std;
int main() {
int arr[] = {1,5,7,-1,5};
int n = 5, X = 6;
unordered_map mp;
for(int i = 0; i < n; i++) {
int complement = X - arr[i];
if(mp[complement] > 0)
cout << "(" << complement << ", " << arr[i] << ")\n";
mp[arr[i]]++;
}
return 0;
}
Java
import java.util.HashMap;
public class PairSum {
public static void main(String[] args) {
int[] arr = {1,5,7,-1,5};
int X = 6;
HashMap map = new HashMap<>();
for(int num : arr) {
int complement = X - num;
if(map.containsKey(complement))
System.out.println("(" + complement + ", " + num + ")");
map.put(num, map.getOrDefault(num, 0) + 1);
}
}
}
Python
arr = [1,5,7,-1,5]
X = 6
seen = {}
for num in arr:
comp = X - num
if comp in seen:
print((comp, num))
seen[num] = seen.get(num, 0) + 1
JavaScript
let arr = [1,5,7,-1,5];
let X = 6;
let map = {};
for (let num of arr) {
let comp = X - num;
if (map[comp])
console.log(`(${comp}, ${num})`);
map[num] = (map[num] || 0) + 1;
}
Approach 3: Two Pointer Technique (Sorted Array)
Idea
Sort the array and use two pointers from both ends to find pairs.
Algorithm
- Sort the array
- Initialize left = 0, right = n - 1
- While left < right
- If sum == X → print pair, move both
- If sum < X → move left
- If sum > X → move right
Time & Space Complexity
- Time: O(n log n)
- Space: O(1)
Implementations
C++
#include
#include
using namespace std;
int main() {
int arr[] = {1,5,7,-1,5};
int n = 5, X = 6;
sort(arr, arr + n);
int left = 0, right = n - 1;
while(left < right) {
int sum = arr[left] + arr[right];
if(sum == X) {
cout << "(" << arr[left] << ", " << arr[right] << ")\n";
left++; right--;
}
else if(sum < X)
left++;
else
right--;
}
return 0;
}
Python
arr = [1,5,7,-1,5]
X = 6
arr.sort()
left, right = 0, len(arr) - 1
while left < right:
s = arr[left] + arr[right]
if s == X:
print((arr[left], arr[right]))
left += 1
right -= 1
elif s < X:
left += 1
else:
right -= 1
JavaScript
let arr = [1,5,7,-1,5];
let X = 6;
arr.sort((a,b) => a - b);
let left = 0, right = arr.length - 1;
while (left < right) {
let sum = arr[left] + arr[right];
if (sum === X) {
console.log(`(${arr[left]}, ${arr[right]})`);
left++; right--;
} else if (sum < X) {
left++;
} else {
right--;
}
}
Dry Run (Hash Map Approach)
Input
arr = [1, 5, 7, -1, 5], X = 6
| Current | Complement | Map | Output |
|---|---|---|---|
| 1 | 5 | {} | — |
| 5 | 1 | {1} | (1,5) |
| 7 | -1 | {1,5} | — |
| -1 | 7 | {1,5,7} | (7,-1) |
| 5 | 1 | {1,5,7,-1} | (1,5) |
Summary
- Brute force is simple but slow
- Hash map gives best performance for unsorted arrays
- Two pointer works best when array is sorted
- Problem builds strong base for Two Sum variants
Next Problem in the Series
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
