How to Find a Pair of Elements Whose Sum Equals a Given Number in Java
Finding two elements whose sum equals a given target is one of the most popular array problems in coding interviews. It is commonly known as the Two Sum problem and is frequently used to test problem-solving skills and knowledge of data structures.
The problem can be solved in multiple ways. While the brute-force approach is simple to understand, the HashSet complement lookup provides an efficient O(n) solution for unsorted arrays. If the array is already sorted, the two-pointer technique offers another optimal approach using constant extra space.
In this tutorial, you'll learn all three methods, understand how they work, and know which one to use in different situations.
Problem Statement
Given the following array:
int[] numbers = {2, 7, 11, 15};Find two elements whose sum equals:
int target = 9;Output
Pair found: 2, 7Method 1: Brute Force (Nested Loops)
The simplest solution is to compare every possible pair of elements.
Example
public class Main {
public static void main(String[] args) {
int[] numbers = {2, 7, 11, 15};
int target = 9;
for (int i = 0; i < numbers.length; i++) {
for (int j = i + 1; j < numbers.length; j++) {
if (numbers[i] + numbers[j] == target) {
System.out.println("Pair found: " +
numbers[i] + ", " + numbers[j]);
}
}
}
}
}Output
Pair found: 2, 7Explanation
The algorithm checks every possible combination of two elements.
If their sum equals the target, the pair is printed.
Time Complexity: O(n²)
Space Complexity: O(1)
Although simple, this approach becomes inefficient for large arrays.
Method 2: HashSet Complement Lookup (Optimal for Unsorted Arrays)
Instead of comparing every pair, calculate the complement required to reach the target.
Example
import java.util.HashSet;
import java.util.Set;
public class Main {
public static void main(String[] args) {
int[] numbers = {2, 7, 11, 15};
int target = 9;
Set<Integer> seen = new HashSet<>();
for (int num : numbers) {
int complement = target - num;
if (seen.contains(complement)) {
System.out.println("Pair found: " +
complement + ", " + num);
break;
}
seen.add(num);
}
}
}Output
Pair found: 2, 7Explanation
For every element:
- Calculate the complement.
complement = target - currentNumber- Check whether the complement already exists in the
HashSet. - If it exists, the pair has been found.
Otherwise, add the current element to the set and continue.
Time Complexity: O(n)
Space Complexity: O(n)
This is the standard interview solution for unsorted arrays.
Method 3: Two-Pointer Technique (Sorted Arrays)
If the array is already sorted (or sorting is allowed), the two-pointer technique provides an efficient solution.
Example
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] numbers = {2, 7, 11, 15};
Arrays.sort(numbers);
int target = 9;
int left = 0;
int right = numbers.length - 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum == target) {
System.out.println("Pair found: " +
numbers[left] + ", " + numbers[right]);
break;
} else if (sum < target) {
left++;
} else {
right--;
}
}
}
}Output
Pair found: 2, 7Explanation
Two pointers begin at opposite ends of the sorted array.
- If the sum is too small, move the left pointer.
- If the sum is too large, move the right pointer.
- Stop when the required pair is found.
Time Complexity: O(n) after sorting
Space Complexity: O(1)
If sorting is required first, the total complexity becomes O(n log n).
Finding All Pairs
Sometimes multiple pairs satisfy the target sum.
Example
import java.util.HashSet;
import java.util.Set;
public class Main {
public static void main(String[] args) {
int[] numbers = {2, 7, 4, 5, 11, -2};
int target = 9;
Set<Integer> seen = new HashSet<>();
Set<String> printedPairs = new HashSet<>();
for (int num : numbers) {
int complement = target - num;
if (seen.contains(complement)) {
int smaller = Math.min(num, complement);
int larger = Math.max(num, complement);
String key = smaller + "," + larger;
if (!printedPairs.contains(key)) {
System.out.println("Pair: " +
smaller + ", " + larger);
printedPairs.add(key);
}
}
seen.add(num);
}
}
}Output
Pair: 2, 7
Pair: 4, 5
Pair: -2, 11The second HashSet prevents duplicate pairs from being printed.
Step-by-Step Explanation
Consider:
Array = [2, 7, 11, 15]
Target = 9Initially:
Seen = {}Step 1
Current number:
2Complement:
7Not found.
Add:
Seen = {2}Step 2
Current number:
7Complement:
2Already exists.
Pair found:
2, 7The algorithm stops immediately.
Internal Working
HashSet contents during execution:
{}
↓
{2}
↓
Pair FoundEach lookup in a HashSet takes approximately O(1) time, making the entire algorithm run in linear time.
Real-Life Analogy
Imagine you're trying to find two people whose combined ages equal 50.
Instead of comparing every possible pair of people, you remember the ages you've already seen.
When you meet someone who is 30, you immediately ask:
"Have I already met someone who is 20?"
This simple lookup is much faster than checking every possible pair.
Best Practices
- Use the HashSet approach for unsorted arrays.
- Use the two-pointer technique when the array is already sorted.
- Clarify whether only one pair or all pairs are required.
- Avoid duplicate outputs when finding all pairs.
- Handle duplicate values carefully.
Common Mistakes
1. Using Brute Force as the Final Solution
Nested loops work but are inefficient compared to the HashSet approach.
2. Printing Duplicate Pairs
When multiple identical values exist, use a secondary set to avoid duplicate output.
3. Adding the Current Number Before Checking
Incorrect:
seen.add(num);
if (seen.contains(complement))Correct:
if (seen.contains(complement)) {
...
}
seen.add(num);This prevents an element from incorrectly pairing with itself.
4. Using the Two-Pointer Technique on an Unsorted Array
The two-pointer method only works correctly on sorted arrays.
Expert Tips
- The complement lookup pattern is one of the most important interview techniques.
- If indexes are required instead of values, use a
HashMap<Integer, Integer>instead of aHashSet. - The Two Sum problem is the foundation for more advanced problems such as Three Sum and Four Sum.
- Always clarify whether duplicate values can form valid pairs.
Comparison Table
| Method | Time Complexity | Space Complexity | Requires Sorted Array? |
|---|---|---|---|
| Brute Force | O(n²) | O(1) | ❌ No |
| HashSet Complement Lookup | O(n) | O(n) | ❌ No |
| Two-Pointer Technique | O(n)* | O(1) | ✅ Yes |
*If sorting is required first, the overall complexity becomes O(n log n).
Frequently Asked Questions
1. What is the common name for this problem?
It is widely known as the Two Sum problem.
2. What is the fastest solution for an unsorted array?
The HashSet complement lookup approach provides O(n) time complexity.
3. How do I return indexes instead of values?
Use a HashMap<Integer, Integer> that stores each value and its index.
4. Can there be multiple valid pairs?
Yes. If all pairs are required, continue traversing the array and avoid duplicates using an additional set.
5. Does the two-pointer technique require sorting?
Yes. The array must be sorted before using the two-pointer approach.
6. What happens if no pair exists?
The loop completes without finding a match, and you can display an appropriate message such as:
No pair found.7. Can this technique be extended to Three Sum?
Yes. After sorting the array, fix one element and use the two-pointer technique on the remaining elements.
8. Does the HashSet approach work with duplicate values?
Yes. However, you should carefully handle cases where duplicate values may form valid pairs, depending on the problem requirements.
