ArrayProblem 18 of 36
Find all pairs on integer array whose sum is equal to given number
Problem Statement
Given an array of integers and a target sum, find all pairs of elements whose sum equals the target.
Example:
- Input:
arr = [1, 5, 7, -1, 5],target = 6 - Output:
[(1, 5), (1, 5), (7, -1)] - Explanation: 1+5=6, 1+5=6, 7+(-1)=6
Approach 1: Brute Force
Intuition
Check all possible pairs and see if their sum equals the target.
Algorithm
- Use two nested loops to generate all pairs
- For each pair (i, j) where i < j
- If
arr[i] + arr[j] == target, add to result
java
import java.util.*;
public class Solution {
public List<int[]> findPairsBruteForce(int[] arr, int target) {
List<int[]> result = new ArrayList<>();
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (arr[i] + arr[j] == target) {
result.add(new int[]{arr[i], arr[j]});
}
}
}
return result;
}
}Complexity Analysis
- Time Complexity: O(n²) - Checking all pairs
- Space Complexity: O(1) - Excluding output space
Approach 2: Using HashMap (Optimal)
Intuition
For each element, we need to find if target - element exists in the array. A HashMap allows O(1) lookups.
Algorithm
- Use a HashMap to store element frequencies
- For each element
x, check iftarget - xexists in map - Handle duplicates carefully
java
import java.util.*;
public class Solution {
public List<int[]> findPairs(int[] arr, int target) {
List<int[]> result = new ArrayList<>();
Map<Integer, Integer> freq = new HashMap<>();
for (int num : arr) {
int complement = target - num;
// If complement exists, form pairs
if (freq.containsKey(complement)) {
for (int i = 0; i < freq.get(complement); i++) {
result.add(new int[]{complement, num});
}
}
// Add current number to map
freq.put(num, freq.getOrDefault(num, 0) + 1);
}
return result;
}
// Alternative: Find unique pairs only
public List<int[]> findUniquePairs(int[] arr, int target) {
List<int[]> result = new ArrayList<>();
Map<Integer, Integer> freq = new HashMap<>();
// Count frequencies
for (int num : arr) {
freq.put(num, freq.getOrDefault(num, 0) + 1);
}
for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
int num = entry.getKey();
int count = entry.getValue();
int complement = target - num;
if (complement == num) {
// Same number: need at least 2 occurrences
if (count >= 2) {
result.add(new int[]{num, num});
}
} else if (complement > num && freq.containsKey(complement)) {
// Only add once (when num < complement to avoid duplicates)
result.add(new int[]{num, complement});
}
}
return result;
}
}Complexity Analysis
- Time Complexity: O(n) - Single pass with O(1) lookups
- Space Complexity: O(n) - HashMap to store elements
Approach 3: Two Pointers (For Sorted Array)
Intuition
If the array is sorted, we can use two pointers from both ends.
Algorithm
- Sort the array
- Use two pointers:
leftat start,rightat end - If sum < target, move left pointer right
- If sum > target, move right pointer left
- If sum == target, record pair and move both pointers
java
import java.util.*;
public class Solution {
public List<int[]> findPairsTwoPointer(int[] arr, int target) {
List<int[]> result = new ArrayList<>();
int[] sorted = arr.clone();
Arrays.sort(sorted);
int left = 0, right = sorted.length - 1;
while (left < right) {
int sum = sorted[left] + sorted[right];
if (sum == target) {
result.add(new int[]{sorted[left], sorted[right]});
// Handle duplicates
int leftVal = sorted[left];
int rightVal = sorted[right];
while (left < right && sorted[left] == leftVal) left++;
while (left < right && sorted[right] == rightVal) right--;
} else if (sum < target) {
left++;
} else {
right--;
}
}
return result;
}
}Complexity Analysis
- Time Complexity: O(n log n) - Dominated by sorting
- Space Complexity: O(n) - For sorted copy (O(1) if sorting in-place is allowed)
Key Takeaways
- HashMap approach is optimal for unsorted arrays
- Two-pointer approach works well if array is already sorted
- Handle duplicates carefully based on problem requirements
- For finding if a pair exists (vs. all pairs), a HashSet suffices
- This is the classic "Two Sum" problem - foundation for many variants
- Variants: Find triplets, quadruplets, pairs with difference k