HashMap and HashSet Problems in Java: Two Sum, Frequency Counting, and Deduplication Patterns

The moment a problem asks "Have I seen this value before?" or "How many times does it appear?", a hash structure should come to mind. HashMap and HashSet trade extra memory for average constant-time lookup. That trade often turns a nested O(n^2) scan into a single O(n) pass.

Two Sum makes the idea concrete, but the same pattern drives frequency counting, first-unique searches, and duplicate detection.

When to reach for hashing

Without an index, answering "Have I seen x?" may require scanning everything seen so far. Repeating that scan for every element produces quadratic work. A hash table builds the index as the input arrives.

The usual clues are:

• membership, such as whether a value has appeared

• counts, such as the frequency of each word

• complements, such as the earlier value needed to reach a target sum

• uniqueness, such as the first non-repeating character

• deduplication, such as retaining one copy of each value

get, put, containsKey, and contains take O(1) time on average. Hash collisions can make individual operations slower, so the guarantee is average rather than unconditional worst case. Across a well-distributed input, one operation per element gives an O(n) algorithm.

HashMap versus HashSet in Java

HashMap<K, V> associates a key with a value. The value might be a count, an index, or some accumulated result. HashSet<E> stores only membership. Internally, Java's HashSet is backed by a HashMap, but its public question is simpler: is this element present?

Choose a set when presence is enough. Choose a map when each key needs attached information.

Neither HashMap nor HashSet promises iteration order. Use LinkedHashMap or LinkedHashSet when insertion order matters. Use TreeMap or TreeSet when sorted order is part of the requirement.

Fully worked Two Sum with a HashMap

Given nums = [2, 7, 11, 15] and target = 9, return the indices of two numbers whose sum is 9. The answer is [0, 1] because nums[0] + nums[1] = 2 + 7 = 9.

A brute-force solution checks every pair. For each i, it scans later positions j, giving O(n^2) time. The one-pass solution stores each value already visited together with its index:

static int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> seen = new HashMap<>();

    for (int i = 0; i < nums.length; i++) {
        int need = target - nums[i];
        if (seen.containsKey(need)) {
            return new int[] {seen.get(need), i};
        }
        seen.put(nums[i], i);
    }

    return new int[0];
}

Trace the exact input:

At i = 0, the needed complement is 9 - 2 = 7. It has not appeared, so store 2 -> 0. At i = 1, the needed complement is 9 - 7 = 2. The map says 2 appeared at index 0, so return [0, 1]. A final check gives nums[0] + nums[1] = 2 + 7 = 9.

The loop visits each element once, so time is O(n). In the no-answer case the map can hold all n elements, so extra space is O(n). Checking before storing also prevents the current element from pairing with itself.

Frequency counting patterns

A frequency map attaches a count to each value. Java's merge method expresses the update directly:

Map<Integer, Integer> frequency = new HashMap<>();
for (int x : nums) {
    frequency.merge(x, 1, Integer::sum);
}

For [1, 2, 2, 3, 3, 3], process one element at a time. The count of 1 becomes 1. The two visits to 2 produce 1, then 2. The three visits to 3 produce 1, 2, then 3. The final map is {1: 1, 2: 2, 3: 3}, so the value appearing exactly three times is 3.

The equivalent explicit update is map.put(x, map.getOrDefault(x, 0) + 1). Use whichever version your team reads more easily.

For the first non-repeating character in "aabbc", order matters. Count with a LinkedHashMap<Character, Integer> so keys retain first-seen order. The counts are a -> 2, b -> 2, and c -> 1. Scanning those entries finds c as the first key with count 1.

Deduplication and membership with HashSet

Adding [4, 1, 2, 1, 4, 3] to a HashSet leaves the four distinct values 1, 2, 3, and 4. Do not claim a particular printed order, because HashSet does not guarantee one.

Duplicate detection can happen during the same pass:

static boolean containsDuplicate(int[] nums) {
    Set<Integer> seen = new HashSet<>();
    for (int x : nums) {
        if (!seen.add(x)) return true;
    }
    return false;
}

add returns false when an equal element is already present. That single return value combines a membership test with insertion.

Java hashing traps that break correct-looking code

A custom key must obey the equals() and hashCode() contract. Equal objects must have equal hash codes. Override one without the other and a lookup can search the wrong bucket or fail to recognise an equivalent key. HashMap Internal Working in Java: Hashing, Buckets, Treeification and the Interview Answer explains why buckets, equality, and collision handling all matter, while Hashing and Collision Resolution: Hash Functions, Chaining and Open Addressing gives the data-structure view.

Other frequent traps are:

• Comparing boxed Integer objects with ==. That compares references, and cache behaviour can make small values appear to work. Use .equals() for values.

• Assuming iteration follows insertion order. Choose a linked variant when order matters.

• Mutating a key field that participates in equals() or hashCode() after insertion. The object may now hash to a different bucket and become effectively lost inside the map.

• Forgetting that average O(1) is not sorted access. Hashing is the wrong structure when the task needs ordered traversal or range queries.

How coding rounds test these patterns

Two Sum is the entry point. Variants ask for a pair count, a target difference, or indices under duplicate values. The same hash toolkit extends to grouping anagrams, first unique characters, subarray sum equal to k, and duplicate removal.

The key interview step is explaining what the map stores. "I use a HashMap" is incomplete. Say whether the mapping is value to index, value to count, prefix sum to frequency, or signature to group. That invariant is the actual solution.

Hashing patterns to remember

Use a HashSet for presence and a HashMap when a key needs a count, index, or other value. Two Sum stores value to index and finds [0, 1] in one pass. Frequency problems update counts with merge or getOrDefault, and duplicate checks can use the return value of set.add.

KnowledgeGate's Data Structure practice bank offers about 1,500 questions, including about 140 on hashing. Practise the patterns in DSA using Java, build a wider interview plan with Mera Placement Hoga, or choose another sequence from Coding & Skills.