Find a Pair with the Given Sum

Title: Find a Pair with the Given Sum

In this guide, you’ll learn how to find two numbers in an array that add up to a target sum. This is one of the most common interview questions and teaches you the power of data structures in solving algorithmic problems efficiently.

Understanding the Problem

Given an array of integers and a target sum, you need to find two distinct elements whose sum equals the target. For example, in the array [1, 5, 7, -1, 5] with target sum 6, you can find the pair (1, 5) or (7, -1).

The key insight is that for each element, you’re asking: “Is the complement (target – element) also in the array?” A HashSet lets you answer this in O(1) time, collapsing an O(n²) brute force into O(n).

Approach / Algorithm Steps

1. Create a HashSet to store numbers we’ve already visited.
2. Iterate through the array one element at a time.
3. For each element, calculate the complement = target - element.
4. Check if the complement exists in the HashSet. If yes, we’ve found the pair.
5. If not found, add the current element to the HashSet and continue.
6. If the loop ends without finding a pair, return a special marker (e.g., null or throw an exception).

Java Program

import java.util.HashSet;
import java.util.Set;

public class FindPairWithSum {
    public static int[] findPair(int[] arr, int target) {
        Set<Integer> seen = new HashSet<>();
        
        for (int num : arr) {
            int complement = target - num;
            if (seen.contains(complement)) {
                return new int[]{complement, num};
            }
            seen.add(num);
        }
        
        return null; // No pair found
    }
    
    public static void main(String[] args) {
        int[] arr1 = {1, 5, 7, -1, 5};
        int target1 = 6;
        int[] result1 = findPair(arr1, target1);
        System.out.println("Array: " + java.util.Arrays.toString(arr1));
        System.out.println("Target: " + target1);
        System.out.println("Pair found: " + java.util.Arrays.toString(result1));
        System.out.println();
        
        int[] arr2 = {2, 4, 9, 11};
        int target2 = 15;
        int[] result2 = findPair(arr2, target2);
        System.out.println("Array: " + java.util.Arrays.toString(arr2));
        System.out.println("Target: " + target2);
        System.out.println("Pair found: " + java.util.Arrays.toString(result2));
    }
}

Explanation of the Program

The method findPair accepts an integer array and a target sum. It maintains a HashSet named seen to track elements we’ve processed so far.

The loop iterates through each element. For every number, we calculate its complement (the value needed to reach the target). We check if this complement is already in the seen set. If it is, we’ve found our pair and return immediately as an array containing both numbers.

If the complement is not in the set, we add the current number to seen and continue. This way, we build up the set of numbers we’ve encountered, ready to match against future complements. If we finish the loop without finding a pair, we return null to signal failure.

Step-by-Step Trace

Let’s trace the algorithm on the array [2, 7, 11, 3] with target sum 9:

At the end of iteration 2, we found that the complement of 7 (which is 2) already exists in our seen set, confirming the pair (2, 7) sums to 9. The algorithm terminates early because we found the solution.

Examples

Example 1: Basic Case

// Input: arr = [1, 5, 7, -1, 5], target = 6
// Output: [1, 5] or [5, 1] or [7, -1]

int[] arr = {1, 5, 7, -1, 5};
int target = 6;
int[] pair = findPair(arr, target);
System.out.println("Pair: " + java.util.Arrays.toString(pair));
// Output: Pair: [1, 5]

Example 2: Negative Numbers

// Input: arr = [-5, -2, 0, 2, 5, 10], target = 0
// Output: [-5, 5] or other combinations

int[] arr = {-5, -2, 0, 2, 5, 10};
int target = 0;
int[] pair = findPair(arr, target);
System.out.println("Pair: " + java.util.Arrays.toString(pair));
// Output: Pair: [-5, 5]

Example 3: No Pair Found

// Input: arr = [1, 2, 3, 4], target = 100
// Output: null (no valid pair exists)

int[] arr = {1, 2, 3, 4};
int target = 100;
int[] pair = findPair(arr, target);
System.out.println("Pair: " + pair);
// Output: Pair: null

Common Mistakes to Avoid

• Checking before adding to the set – The order matters: always check for the complement before adding the current element. If you add first, you risk matching an element with itself on arrays with duplicate targets (e.g., array [5] with target 10 would incorrectly return [5, 5]).
• Forgetting to use a Set for O(1) lookup – Using an ArrayList and contains() results in O(n²) complexity. Always use HashSet for constant-time membership testing.
• Returning the pair in the wrong order – Return the complement first, then the current number: return new int[]{complement, num}. This maintains clarity about which value was found first in the set.
• Not handling the case where no pair exists – Always ensure your method gracefully handles the failure case with a clear return value (null, empty array, or an exception depending on your contract).
• Confusing pairs with indices – This algorithm returns the values that form the pair, not the indices. If you need indices, you’d store Map<Integer, Integer> instead of a Set.

Edge Cases to Test

• Empty array – should return null
• Array with one element – cannot form a pair, return null
• Duplicate elements in the array – [5, 5, 10], target 10 should return [5, 5]
• All negative numbers – [-10, -5, -3], target -15 should return [-10, -5]
• Zero as part of the pair – [0, 5, 10], target 5 should return [0, 5]
• Target is sum of same element twice – [7, 14], target 14 should return [7, 7] only if array contains two 7s
• Large numbers causing integer overflow – though in Java, int overflow wraps; consider using long for safety
• Pair found at the very end – array [1, 2, 3, 4, 5], target 9 should find [4, 5]

Additional Considerations

Time and Space Complexity

Time Complexity: O(n), where n is the length of the array. We iterate through the array exactly once, and each HashSet operation (add, contains) runs in O(1) on average.

Space Complexity: O(n) for the HashSet. In the worst case, we may store all n elements in the set before finding a pair (or determining no pair exists).

Alternative Approaches

If the array were already sorted, you could use a two-pointer approach: start with one pointer at the beginning and one at the end. If their sum is less than the target, move the left pointer right; if greater, move the right pointer left. This also runs in O(n) time but uses O(1) space (ignoring the cost of sorting if needed). However, the HashSet approach is cleaner when the array is unsorted and you want to find the pair quickly in a single pass.

Interview Follow-up Questions

• What if you need to find all pairs? – Instead of returning after the first match, collect all pairs in a List. Be careful about duplicates: consider sorting the result or using a Set of pairs to avoid listing the same pair twice.
• What if the array is very large and sorted? – Use the two-pointer technique: O(n) time and O(1) extra space, which is better than the HashSet when memory is a constraint.
• How would you handle floating-point numbers? – Be aware of precision issues. Instead of using == for comparison, check if the absolute difference is within a small epsilon (e.g., Math.abs(a – b) < 1e-9).
• What if you must find pairs with zero extra space (in-place)? – Sort the array first (O(n log n)), then use two pointers. This destroys the original order but meets the space constraint.
• What if the array is a stream of unknown length? – Use a HashSet to track elements and emit a pair as soon as you find the complement. This works in O(1) space per element processed, but you can only output pairs once.

Conclusion

Finding a pair with a given sum is a foundational problem that teaches you the value of choosing the right data structure. By using a HashSet to trade space for time, you collapse a naive O(n²) search into O(n). This pattern—store-then-match—appears throughout algorithms, from two-sum variants to graph traversal to caching in dynamic programming.

Practice this problem with different constraints: sorted arrays, in-place requirements, streaming input, or the need to find all pairs. Each variation deepens your intuition. You can learn more about array algorithms and interview-style problems on the Arrays category page.