Find All Pairs with Given Sum
Java coding interview problem for Array Coding: Find All Pairs with Given Sum.
Finding all pairs with a given sum is one of the most popular array interview problems.
This problem is an extension of the famous Two Sum problem.
It helps you understand:
- Array traversal
- Complement searching
- Hashing
- Sorting
- Two Pointer Technique
- Duplicate handling
- Time Complexity optimization
This concept is used as a foundation for many advanced problems:
- Three Sum
- Four Sum
- Pair Difference
- Subarray Sum
- Frequency Problems
What Are Pairs With Given Sum?
Given an array and a target value,
find all pairs of elements whose sum equals the target.
Example
Input:
Array:
[2,7,11,15]
Target:
9
Pairs:
2 + 7 = 9
Output:
[2,7]
Finding All Pairs
Unlike Two Sum, we need to find all possible pairs.
Example:
Input:
Array:
[1,2,3,4,5,6]
Target:
7
Possible pairs:
1 + 6 = 7
2 + 5 = 7
3 + 4 = 7
Output:
[
[1,6],
[2,5],
[3,4]
]
Why is This Question Asked in Interviews?
Interviewers ask this problem because it evaluates:
- Problem-solving ability
- Optimization thinking
- HashMap knowledge
- Sorting techniques
- Duplicate handling
- Trade-off decisions
It is commonly asked by:
- Amazon
- Microsoft
- Oracle
- Meta
Real-World Applications
Financial Systems
Finding transactions that match a specific amount.
Example:
Transactions:
[20,50,80,100]
Target:
120
Pairs:
20 + 100
50 + 70
E-Commerce
Finding product combinations within a budget.
Example:
Products:
[25,40,60,75]
Budget:
100
Possible combinations:
25 + 75
40 + 60
Fraud Detection
Finding suspicious transactions that match known patterns.
Recommendation Systems
Finding two products frequently purchased together.
Problem Statement
Given an integer array and a target sum,
find all unique pairs whose sum equals the target value.
Example 1
Input:
Array:
[1,5,7,-1,5]
Target:
6
Output:
[
[1,5],
[7,-1]
]
Example 2
Input:
Array:
[2,4,3,5,7,8,9]
Target:
7
Output:
[
[2,5],
[3,4]
]
Example 3
Input:
Array:
[1,2,3]
Target:
10
Output:
[]
Understanding Pair Formation
Consider:
Array:
[10,20,30,40,50]
Target:
60
For each element:
Take:
10
Need:
60 - 10 = 50
50 exists.
Pair:
[10,50]
Take:
20
Need:
40
Pair:
[20,40]
Take:
30
Need:
30
Only one occurrence.
Ignore.
Final:
[
[10,50],
[20,40]
]
Mathematical Concept
For every element:
Current Element + Required Element = Target
Therefore:
Required Element = Target - Current Element
Example:
Target:
10
Current:
3
Required:
10 - 3 = 7
Search for:
7
Pair Visualization
Input:
[2,4,5,7,8,9]
Target = 11
Searching:
2 + 9 = 11
4 + 7 = 11
5 + 6 = 11
Result:
[
[2,9],
[4,7]
]
Dry Run
Input:
Array:
[1,3,5,7,9]
Target:
10
Start:
Result = []
Element:
1
Required:
10 - 1 = 9
Found:
[1,9]
Element:
3
Required:
7
Found:
[3,7]
Element:
5
Required:
5
Only one 5.
Ignore.
Final:
[
[1,9],
[3,7]
]
Approach 1 — Brute Force Using Nested Loops
The simplest approach is checking every possible pair.
For every element:
- Compare it with every other element.
- Check whether sum equals target.
Algorithm
- Use first loop for selecting first element.
- Use second loop for selecting second element.
- Check:
numbers[i] + numbers[j] == target
- Store matching pairs.
Java Program
import java.util.*;
public class FindPairsBruteForce {
public static List<List<Integer>> findPairs(
int[] numbers,
int target) {
List<List<Integer>> result =
new ArrayList<>();
for (int i = 0; i < numbers.length; i++) {
for (int j = i + 1;
j < numbers.length;
j++) {
if (numbers[i] + numbers[j]
== target) {
result.add(
Arrays.asList(
numbers[i],
numbers[j]));
}
}
}
return result;
}
public static void main(String[] args) {
int[] numbers =
{1,5,7,-1,5};
int target = 6;
System.out.println(
findPairs(numbers,target));
}
}
Output
[
[1,5],
[7,-1]
]
Step-by-Step Explanation
Input:
[1,5,7,-1,5]
Target:
6
Compare:
1 + 5 = 6
Add:
[1,5]
Compare:
7 + (-1) = 6
Add:
[7,-1]
Remaining pairs:
No match.
Complexity Analysis
For every element,
we check all remaining elements.
Number of comparisons:
n * (n-1) / 2
Time:
O(n²)
Space:
O(k)
Where:
k = number of pairs
Advantages
- Very easy to understand.
- Works for unsorted arrays.
- No extra data structure required.
Drawbacks
- Slow for large arrays.
- Many unnecessary comparisons.
- Not suitable for production scale.
Approach 2 — Using HashSet (Optimal for Unsorted Arrays)
HashSet improves performance by storing previously seen values.
The idea:
For every number:
Calculate:
target - number
Check whether this value already exists.
Example
Array:
[2,7,11,15]
Target:
9
Read:
2
Need:
7
Not found.
Store:
{2}
Read:
7
Need:
2
Found.
Pair:
[2,7]
Algorithm
- Create HashSet.
- Traverse array.
- Calculate complement:
target - current
- If complement exists:
- Add pair.
- Otherwise:
- Store current value.
Java Program
import java.util.*;
public class FindPairsHashSet {
public static List<List<Integer>> findPairs(
int[] numbers,
int target) {
Set<Integer> seen =
new HashSet<>();
Set<String> uniquePairs =
new HashSet<>();
List<List<Integer>> result =
new ArrayList<>();
for (int number : numbers) {
int complement =
target - number;
if (seen.contains(complement)) {
int first =
Math.min(number, complement);
int second =
Math.max(number, complement);
String key =
first + "," + second;
if (uniquePairs.add(key)) {
result.add(
Arrays.asList(
first,
second));
}
}
seen.add(number);
}
return result;
}
}
Complexity Analysis
Time:
O(n)
Space:
O(n)
Advantages
- Much faster than brute force.
- Works with unsorted arrays.
- Easy to implement.
Drawbacks
- Requires extra memory.
- Duplicate handling needs attention.
Approach 3 — Using HashMap Frequency (Handle Duplicate Pairs)
The HashSet approach works well when we need unique pairs.
But many interview problems ask:
Find all pairs including duplicate occurrences.
For this case, we use a HashMap to store frequencies.
Why Use HashMap?
HashMap stores:
Number → Count
Example:
Array:
[2,2,3,4,4,4]
Frequency:
2 → 2
3 → 1
4 → 3
This helps us understand how many times a number can participate in pairs.
Example
Input:
Array:
[1,5,5,7]
Target:
10
Frequency:
1 → 1
5 → 2
7 → 1
Pairs:
5 + 5 = 10
Output:
[5,5]
Algorithm
- Create a frequency map.
- Store count of every element.
- Traverse the array.
- Calculate complement:
target - current
- Check complement frequency.
- Decrease counts after using values.
- Store pairs.
Java Program
import java.util.*;
public class FindPairsHashMap {
public static List<List<Integer>> findPairs(
int[] numbers,
int target) {
Map<Integer, Integer> frequency =
new HashMap<>();
for (int number : numbers) {
frequency.put(
number,
frequency.getOrDefault(
number, 0) + 1);
}
List<List<Integer>> result =
new ArrayList<>();
for (int number : numbers) {
if (frequency.get(number) == 0) {
continue;
}
int complement =
target - number;
if (frequency.getOrDefault(
complement, 0) > 0) {
if (number == complement &&
frequency.get(number) < 2) {
continue;
}
result.add(
Arrays.asList(
number,
complement));
frequency.put(
number,
frequency.get(number) - 1);
frequency.put(
complement,
frequency.get(complement) - 1);
}
}
return result;
}
public static void main(String[] args) {
int[] numbers =
{1,5,5,7};
int target = 10;
System.out.println(
findPairs(numbers,target));
}
}
Output
[
[5,5]
]
Step-by-Step Explanation
Input:
[1,5,5,7]
Target:
10
Frequency Map:
1 → 1
5 → 2
7 → 1
Process:
1
Need:
9
Not found.
Process:
5
Need:
5
Frequency:
5 → 2
Pair:
[5,5]
Decrease count.
Process:
7
Need:
3
Not found.
Result:
[5,5]
Complexity Analysis
Time:
O(n)
Space:
O(n)
Advantages
- Handles duplicate values.
- Single traversal after frequency creation.
- Good for real-world data.
Drawbacks
- More complex than HashSet.
- Requires additional memory.
Approach 4 — Two Pointer Approach (Sorted Array)
If the array is sorted, the Two Pointer approach is the most efficient solution.
It avoids extra memory.
Example
Input:
[1,2,3,4,5,6]
Target:
7
Pointers:
L R
1 2 3 4 5 6
Compare:
1 + 6 = 7
Found:
[1,6]
Move both:
L++
R--
Next:
2 + 5 = 7
Found:
[2,5]
Next:
3 + 4 = 7
Found:
[3,4]
Result:
[
[1,6],
[2,5],
[3,4]
]
Algorithm
- Sort the array.
- Set:
left = 0
right = n - 1
- Compare:
sum = numbers[left] + numbers[right]
-
If sum equals target:
- Store pair.
- Move both pointers.
-
If sum is smaller:
- Increase left.
-
If sum is greater:
- Decrease right.
Java Program
import java.util.*;
public class FindPairsTwoPointer {
public static List<List<Integer>> findPairs(
int[] numbers,
int target) {
Arrays.sort(numbers);
List<List<Integer>> result =
new ArrayList<>();
int left = 0;
int right = numbers.length - 1;
while (left < right) {
int sum =
numbers[left] +
numbers[right];
if (sum == target) {
result.add(
Arrays.asList(
numbers[left],
numbers[right]));
int leftValue =
numbers[left];
int rightValue =
numbers[right];
while (left < right &&
numbers[left] == leftValue) {
left++;
}
while (left < right &&
numbers[right] == rightValue) {
right--;
}
} else if (sum < target) {
left++;
} else {
right--;
}
}
return result;
}
public static void main(String[] args) {
int[] numbers =
{1,2,3,4,5,6};
System.out.println(
findPairs(numbers,7));
}
}
Output
[
[1,6],
[2,5],
[3,4]
]
Complexity Analysis
Sorting:
O(n log n)
Two pointer traversal:
O(n)
Overall:
O(n log n)
Space:
O(1)
excluding result.
Advantages
- Memory efficient.
- Simple after sorting.
- Best for sorted arrays.
- Handles duplicates easily.
Drawbacks
- Requires sorting.
- Sorting changes original array.
Approach 5 — Sorting + Binary Search
Another approach:
- Sort the array.
- For each element:
- Calculate complement.
- Search complement using binary search.
Example
Array:
[1,4,6,8,10]
Target:
14
For:
4
Need:
10
Binary search:
Found
Pair:
[4,10]
Algorithm
- Sort array.
- Loop through elements.
- Calculate:
target - current
- Perform binary search.
- Store pair.
Java Program
import java.util.*;
public class FindPairsBinarySearch {
public static List<List<Integer>> findPairs(
int[] numbers,
int target) {
Arrays.sort(numbers);
List<List<Integer>> result =
new ArrayList<>();
for (int i = 0;
i < numbers.length;
i++) {
int complement =
target - numbers[i];
int index =
Arrays.binarySearch(
numbers,
i + 1,
numbers.length,
complement);
if (index >= 0) {
result.add(
Arrays.asList(
numbers[i],
numbers[index]));
}
}
return result;
}
}
Complexity Analysis
Sorting:
O(n log n)
Binary search:
O(n log n)
Total:
O(n log n)
Space:
O(1)
Unique Pair vs Duplicate Pair
Interviewers often ask this clarification.
Unique Pairs
Example:
Array:
[1,1,2,2,3,3]
Target:
4
Output:
[
[1,3],
[2,2]
]
Duplicate Pairs
Output:
[
[1,3],
[1,3],
[2,2]
]
Depends on requirements.
Pair Ordering
Usually:
[a,b]
is considered same as:
[b,a]
Example:
[2,5]
and
[5,2]
represent the same pair.
Primitive vs Object Arrays
Primitive Array
int[]
Benefits:
- Better performance.
- Less memory.
Object Array
Integer[]
Benefits:
- Works with Collections.
- Supports generics.
Comparison of All Approaches
| Approach | Time | Space | Best Use Case |
|---|---|---|---|
| Brute Force | O(n²) | O(1) | Small arrays |
| HashSet | O(n) | O(n) | Unsorted unique pairs |
| HashMap | O(n) | O(n) | Duplicate pairs |
| Two Pointer | O(n log n) | O(1) | Sorted arrays |
| Binary Search | O(n log n) | O(1) | Search-based approach |
Common Interview Mistakes
Mistake 1
Using nested loops for large arrays.
Problem:
O(n²)
Mistake 2
Ignoring duplicate handling.
Always clarify:
Unique pairs?
or
All occurrences?
Mistake 3
Forgetting same number pairs.
Example:
[5,5]
Target = 10
Valid pair:
[5,5]
Mistake 4
Returning duplicate pairs.
Example:
Wrong:
[1,5]
[5,1]
Mistake 5
Integer overflow.
Avoid:
a + b
for extremely large integers without validation.
Edge Cases
| Input | Output |
|---|---|
[] |
[] |
[5,5], target 10 |
[5,5] |
| No matching pair | [] |
| Negative numbers | Works |
| Duplicate values | Handle carefully |
Interview Follow-up Questions
Q1. Find pair with closest sum.
Q2. Find all triplets with given sum.
Q3. Find four numbers with given sum.
Q4. Count number of pairs.
Q5. Find pairs with difference K.
Q6. Find pairs in sorted array.
Q7. Find maximum number of pairs.
Q8. Handle duplicate pairs.
Related Problems
- Two Sum
- Three Sum
- Four Sum
- Pair Difference
- Subarray Sum
- Two Pointer Problems
- Frequency Counting
Key Takeaways
- Brute force is easiest but slow.
- HashSet provides O(n) solution for unique pairs.
- HashMap handles duplicate occurrences.
- Two Pointer is best for sorted arrays.
- Always clarify duplicate requirements.
Frequently Asked Interview Questions
Q1. What is the optimal solution?
For unsorted arrays:
HashSet
Time:
O(n)
For sorted arrays:
Two Pointer
Time:
O(n)
after sorting.
Q2. How do you avoid duplicate pairs?
Use:
- Set of pairs
- Skip duplicate values
- Sorted array approach
Q3. Why is HashSet faster?
Because lookup is approximately:
O(1)
Q4. When should we use HashMap?
When duplicate counts matter.
Interview Tip
When asked:
"Find all pairs with a given sum."
Clarify:
- Do duplicate pairs count?
- Is the array sorted?
- Can extra memory be used?
Then explain:
- Brute Force
- HashSet
- HashMap
- Two Pointer
- Sorting + Binary Search
Understanding these trade-offs demonstrates strong knowledge of Java Collections, algorithms, and production-level problem solving.