Find All Pairs with the Given Sum

Title: Find All Pairs with the Given Sum

In this guide, you’ll learn how to find all pairs in an array of integers whose sum equals a given target value. This is one of the most frequently asked array problems in coding interviews, and it is a great way to practice hash-based lookups instead of reaching for a brute-force nested loop.

We will walk through a single-pass solution using a HashSet, trace it step by step on a fresh example, and then cover the edge cases and follow-up questions an interviewer is likely to ask once you solve the base problem.

Understanding the Problem

Given an array of integers numbers and a target value targetSum, we need to find every pair of elements whose sum equals targetSum. Each pair should be reported only once, even if the array contains duplicate values or the same two values could be read in either order.

For example, given numbers = {8, 7, 2, 5, 3, 1} and targetSum = 10, the valid pairs are (2, 8) and (3, 7). Even though 8 appears before 2 in the array, the pair is still reported only once with a consistent ordering.

Approach

1. Create an empty HashSet<Integer> called seen to remember every number processed so far.
2. Create an empty HashSet<String> called addedPairs to remember which value pairs have already been reported.
3. Iterate over the array once. For the current number num, compute complement = targetSum - num.
4. If complement is already in seen, a valid pair exists. Normalize it as (Math.min(num, complement), Math.max(num, complement)) so the same two values always produce the same key.
5. Check the normalized key against addedPairs. If it has not been added yet, add the pair to the result list and record the key.
6. Add num to seen only after the check, so a number is never paired with itself unless it genuinely occurs twice in the array.
7. Return the collected list of pairs once the loop finishes.

Java Program

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class FindAllPairsWithGivenSum {

    public static List<int[]> findPairsWithSum(int[] numbers, int targetSum) {
        List<int[]> pairs = new ArrayList<>();
        Set<Integer> seen = new HashSet<>();
        Set<String> addedPairs = new HashSet<>();

        for (int num : numbers) {
            int complement = targetSum - num;
            if (seen.contains(complement)) {
                int smaller = Math.min(num, complement);
                int larger = Math.max(num, complement);
                String key = smaller + "," + larger;
                if (!addedPairs.contains(key)) {
                    pairs.add(new int[]{smaller, larger});
                    addedPairs.add(key);
                }
            }
            seen.add(num);
        }
        return pairs;
    }

    public static void main(String[] args) {
        int[] numbers = {8, 7, 2, 5, 3, 1};
        int targetSum = 10;

        List<int[]> pairs = findPairsWithSum(numbers, targetSum);

        System.out.println("Pairs with sum " + targetSum + ":");
        for (int[] pair : pairs) {
            System.out.println(pair[0] + " + " + pair[1] + " = " + targetSum);
        }
    }
}

Explanation of the Program

The method findPairsWithSum makes a single pass over numbers. For each element, it asks a simple question: have I already seen the number that completes this pair?

• seen acts as a lookup table of every number visited before the current index, giving an average O(1) membership check.
• complement is the value that, added to the current number, produces targetSum.
• Normalizing with Math.min and Math.max guarantees that (2, 8) and (8, 2) are always treated as the same pair.
• addedPairs stops the same value pair from being reported twice when the array contains repeated numbers.
• seen.add(num) runs after the lookup, so a number can only pair with itself if it genuinely appears at least twice in the array.

Step-by-Step Trace

Consider numbers = {4, 1, 5, 3, 6, 2} with targetSum = 7. The table below shows how seen grows and when a pair gets added on each iteration.

At the end of each iteration, seen holds every number processed so far, so the complement check on any later element correctly detects an earlier partner regardless of the order the two numbers appear in.

Examples

Example 1: Basic Pair Sum

A plain array with no duplicate values. Each pair is found exactly once.

int[] numbers = {8, 7, 2, 5, 3, 1};
int targetSum = 10;
List<int[]> pairs = findPairsWithSum(numbers, targetSum);
// Output:
// 2 + 8 = 10
// 3 + 7 = 10

Example 2: Duplicate and Negative Values

The value 5 appears twice, but the pair (1, 5) is still reported only once. Negative numbers are handled the same way as positive ones.

int[] numbers = {1, 5, 7, -1, 5};
int targetSum = 6;
List<int[]> pairs = findPairsWithSum(numbers, targetSum);
// Output:
// 1 + 5 = 6
// -1 + 7 = 6

Common Mistakes to Avoid

These are the mistakes that most often slip into a first attempt at this problem.

• Adding the number to seen before checking it – causes a single occurrence of a value to incorrectly pair with itself when targetSum is exactly double that value, for example a lone 4 wrongly matching itself when targetSum is 8. Always check seen for the complement first, then add the current number afterward.
• Reporting pairs without normalizing order – printing (2, 8) and later (8, 2) as if they were different results. Always store the pair as (Math.min(a, b), Math.max(a, b)) so both orderings produce the same key.
• Skipping the addedPairs tracking set – an array with repeated values like {1, 5, 5, 1} and targetSum = 6 reports the pair (1, 5) twice even though it is the same value pair. Track already-emitted pairs with a Set<String> keyed on the normalized values.
• Using a nested loop instead of a hash lookup – works correctly but degrades to O(n squared) time, which times out on large inputs. Replace the inner loop with a single HashSet membership check.
• Confusing value pairs with index pairs – treating numbers[2] and numbers[4] as a different pair from numbers[0] and numbers[4] even when both pairs hold the same two values. Decide up front whether the problem wants distinct value pairs or distinct index pairs, since duplicate values change the answer.

Edge Cases to Test

Walk through these input shapes before calling the solution finished.

• Empty array
• Single-element array
• No pair sums to the target
• Target sum reachable only by pairing a value with itself (even target, value appears once)
• Duplicate values that could form the same pair more than once
• Negative numbers mixed with positive numbers
• All elements identical
• Integer overflow when two large values are added

Additional Considerations

The hash-based approach runs in O(n) time, since each element triggers one constant-time lookup and insert into seen plus a constant-time lookup and insert into addedPairs.

Space complexity is O(n) in the worst case, because seen may end up holding every element of the array and addedPairs may hold up to n divided by 2 keys.

If the array is already sorted, a two-pointer approach achieves the same O(n) time with O(1) extra space, trading the flexibility of unsorted input for a lower memory footprint. Choose the hash-based version when the input order must be preserved or sorting is not an option, and the two-pointer version when the array is sorted or can be sorted cheaply.

Interview Follow-up Questions

Once the base solution is working, expect an interviewer to push on these variations.

• What if the array is already sorted? – use a two-pointer scan from both ends instead of a hash set, which keeps O(n) time but drops extra space to O(1) beyond the output.
• What if you need to count every pair with multiplicity instead of deduplicating? – build a frequency map of values, then for each value compute how many pairs it forms with its complement using the stored counts.
• What if the array arrives as a stream of unknown length? – keep the same seen and addedPairs sets, update them per incoming element, and emit a pair as soon as it is found instead of waiting for the full array.
• What if the array has billions of elements that do not fit in memory? – partition the data by value range, build the seen set per partition, and only look for complements that fall within the same or an adjacent partition.
• What if you need the pair whose sum is closest to the target instead of an exact match? – sort the array and use a two-pointer sweep that tracks the smallest absolute difference seen so far, moving the pointer on the side that overshoots or undershoots.

Conclusion

Finding all pairs with a given sum is a compact problem that rewards recognizing the hash-lookup pattern instead of reaching for nested loops. The same seen-then-check structure shows up across many array problems, from two-sum variants to subarray sum problems.

Try adapting the program to return index pairs instead of value pairs, or to extend it to three numbers that sum to a target instead of two. You can learn more about array-based interview problems in the Arrays category on dailyjavaconcept.com.