Find Pairs in Array with Given Sum in Java
Java Program to Find Pairs in Array with Given Sum
When working with arrays, a common coding interview question is “Find all pairs in an array whose sum equals a given number.”
This problem tests your understanding of loops, arrays, hash based data structures, and time complexity optimization. It also helps strengthen your logical thinking and understanding of efficient data searching techniques.
Find Pairs in Array with given Sum in Java
Problem Statement for Find Pairs in Array with given sum
Given an array of integers and a target sum, your task is to find all unique pairs of elements whose sum equals the given target.
Example:
Input:
arr = [1, 5, 7, -1, 5]
target = 6
Output:
Pairs are: (1, 5), (7, -1)
Explanation:
- 1 + 5 = 6
- 7 + (-1) = 6
Even though 5 appears twice, we count only the unique pair (1, 5).
Methods to Find Pairs in Array with Given Sum in Java
To Find Pairs in Array with Given Sum in Java, we have mentioned 3 different methods, with different approach, time and space complexity:
Learn DSA
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
1. Brute Force Approach to Find Pairs in Array with given Sum
Algorithm:
- Use two nested loops to pick all possible pairs.
- For each pair (arr[i], arr[j]), check if arr[i] + arr[j] == target.
- If true, print or store the pair.
Java Code:
public class FindPairsBruteForce {
public static void main(String[] args) {
int[] arr = {1, 5, 7, -1, 5};
int target = 6;
System.out.println("Pairs with sum " + target + " are:");
for (int i = 0; i < arr.length; i++) {
for (int j = i + 1; j < arr.length; j++) {
if (arr[i] + arr[j] == target) {
System.out.println("(" + arr[i] + ", " + arr[j] + ")");
}
}
}
}
}
Output:
Pairs with sum 6 are: (1, 5) (7, -1) (1, 5)
Space Complexity: O(1)
2. Using Hashset to Find Pairs in Array with given Sum
Algorithm:
We can reduce time complexity using a HashSet:
Initialize an empty HashSet<Integer>.
Iterate through each element num in arr.
- For each num, check if (target – num) exists in the set.
If yes → we found a pair.
If no → add num to the set.
Java Code:
import java.util.HashSet;
public class FindPairsUsingHashSet {
public static void main(String[] args) {
int[] arr = {1, 5, 7, -1, 5};
int target = 6;
findPairs(arr, target);
}
static void findPairs(int[] arr, int target) {
HashSet set = new HashSet<>();
System.out.println("Pairs with sum " + target + " are:");
for (int num : arr) {
int complement = target - num;
if (set.contains(complement)) {
System.out.println("(" + complement + ", " + num + ")");
}
set.add(num);
}
}
}
Output:
Pairs with sum 6 are: (1, 5) (7, -1)
Space Complexity: O(n)
3. Using Hashmap to Find Pairs in Array with given Sum
Algorithm:
If the array contains duplicate numbers, using a HashMap can help count occurrences and manage multiple valid pairs efficiently.
Traverse the array and store the frequency of each element in a HashMap.
For each element x, check if (target – x) exists in the map.
Multiply frequencies to get the total number of valid pairs.
Handle duplicates properly to avoid double counting.
Note: This approach is best when the array contains duplicates and you need pair counts as well.
Java Code:
import java.util.HashMap;
public class FindPairsUsingHashMap {
public static void main(String[] args) {
int[] arr = {1, 5, 7, -1, 5};
int target = 6;
findPairs(arr, target);
}
static void findPairs(int[] arr, int target) {
HashMap map = new HashMap<>();
int count = 0;
for (int num : arr) {
int complement = target - num;
if (map.containsKey(complement)) {
count += map.get(complement);
System.out.println("(" + complement + ", " + num + ")");
}
map.put(num, map.getOrDefault(num, 0) + 1);
}
System.out.println("Total pairs = " + count);
}
}
Output:
(1, 5) (7, -1) (1, 5) Total pairs = 3
Space Complexity: O(n)
Comparison Between the Tables
| Method | Approach | Time Complexity | Space Complexity | Best Use Case |
|---|---|---|---|---|
| Brute Force | Nested Loops | O(n2) | O(1) | Small arrays |
| HashSet | Lookup pairs using complement | O(n) | O(n) | Unique pairs |
| HashMap | Count frequency of elements | O(n) | O(n) | Duplicates or counting pairs |
Find Pairs with Given Sum problem is an essential practice question for array manipulation and hashing concepts.
- Brute Force method is simple but inefficient.
- HashSet and HashMap methods offer O(n) solutions suitable for large arrays.
Always choose the approach depending on whether duplicates exist or whether you need to count all pairs.
FAQ's related to Find pairs in Array with given sum
Answer:
Using a HashSet or HashMap is the most efficient method. Both run in O(n) time, compared to O(n²) for brute force loops.
Answer:
Yes. If the array is sorted, you can use the two pointer approach, which runs in O(n) time and requires O(1) space.
Answer:
Use a HashMap to track element frequencies. This ensures you count pairs correctly without duplication.
Answer:
You can store found pairs in a Set of strings (like “(a,b)”) to ensure uniqueness before printing.
Answer:
- Two Sum Problem
- Triplets with Given Sum
- Subarray with Given Sum
- Pair Difference Problems
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment