HashSet Tricks: Seen It Before?

A set remembers what it has seen

A HashSet stores items with no repeats and answers “have I seen this?” in O(1). add() even tells you: it returns false if the item was already there.

import java.util.HashSet;

public class Main {
    public static void main(String[] args) {
        String[] guests = {"Ana", "Ben", "Cara", "Ben", "Dev", "Ana"};
        HashSet<String> arrived = new HashSet<String>();
        for (String g : guests) {
            if (!arrived.add(g)) {
                System.out.println(g + " is already inside!");
            }
        }
        System.out.println(arrived.size() + " different guests");
    }
}

Output

Ben is already inside!
Ana is already inside!
4 different guests

The pair-sum trick

Is there a pair of numbers that adds up to target? Trying every pair is O(n²). Better: for each number x, ask the set whether its partner target - x has already appeared:

import java.util.HashSet;

public class Main {
    public static void main(String[] args) {
        int[] prices = {40, 15, 70, 25, 60};
        int budget = 85;
        HashSet<Integer> seen = new HashSet<Integer>();
        for (int x : prices) {
            int partner = budget - x;
            if (seen.contains(partner)) {
                System.out.println("Buy " + partner + " and " + x);
                break;
            }
            seen.add(x);
        }
    }
}

Output

Buy 15 and 70

Think of it like this: Looking for a dance partner of the right height: instead of comparing everyone with everyone, each person arriving calls out the height they need, and the host checks the guest list.

Remember: Whenever you think “for each item, search for something”, ask: could a HashSet or HashMap make that search O(1)?