A classic software engineering puzzle (often called **Two Sum**) asks: Given an array of integers and a target sum, check if there are any two numbers that add up to the target. While a nested-loop approach is easy to write, it runs in slow O(N²) time. We can solve this in fast O(N) time using a **complements search**.

In this guide, we will implement the complements lookup algorithm using a HashSet and a Java Stream.

Illustration representing index pairs and target sum complement search
Real-World Analogy: Finding Dance Partners

Imagine people standing in a room, each holding a numbered card. You want to find if any two cards sum up to **9**:

  • A person holding card **7** enters. They calculate: "I need a partner holding card 9 - 7 = 2."
  • They check a chalkboard (HashSet) where previous entries are written. Since 2 is not on the board, they write "7" on the board and sit down.
  • Later, a person holding card **2** enters. They calculate: "I need card 9 - 2 = 7."
  • They check the chalkboard, see **7** is already written there, and yell: "Match Found!"
  • We found our pair in a single pass without making everyone compare cards with everyone else.

1. The Complements HashSet Logic

Instead of matching every number with every other number, we loop through the array once. For each number, we check if its complement (target - number) was already seen. If not, we add the current number to a HashSet:

int[] arr = {10, 15, 3, 7};
int target = 9;

HashSet<Integer> complements = new HashSet<>();
// For 10: complement is 9 - 10 = -1. Not seen. Add 10 to complements.
// For 15: complement is 9 - 15 = -6. Not seen. Add 15 to complements.
// For 3:  complement is 9 - 3 = 6. Not seen. Add 3 to complements.
// For 7:  complement is 9 - 7 = 2. But complements set contains 2? No, wait!

Let's look at the correct matching check:

  • If the current number is num, we look for num in our complements board.
  • If num is found, it means some previous number already calculated it was waiting for num to arrive! We have a match.
  • If not found, we calculate the partner needed (target - num) and store it in our complements board.

Java Implementation

We can write this cleanly using Java 8 Stream's anyMatch() method:

package io.practise.hackerrank;

import java.util.HashSet;
import java.util.stream.IntStream;

public class FindSumPair {
    public static void main(String[] args) {
        int[] arr = {10, 15, 3, 7};
        int target = 9;

        HashSet<Integer> complements = new HashSet<>();

        boolean hasPair = IntStream.of(arr).anyMatch(num -> {
            // If the current number is the complement some previous number was looking for
            if (complements.contains(num)) {
                return true; 
            }
            // Store the complement partner needed for the current number
            complements.add(target - num);
            return false;
        });

        System.out.println("Has pair summing to " + target + "? " + hasPair); // Prints: true (7 + 2)
    }
}

Conclusion

Using a HashSet transforms a slow O(N²) nested loop search into a fast O(N) lookup. HashSet contains check operations run in constant O(1) time, representing the most optimal scaling solution for search pairings.