Find Duplicate Elements in an Array Using HashSet

• HashSet – a collection backed by a HashMap that stores only unique elements with average O(1) add, contains, and remove.
• add() return value – returns true if the element was new and false if it already existed, which is the core duplicate-detection trick.
• Linear scan – one pass over the array with a HashSet gives O(n) time and O(n) extra space.
• Duplicate collection – storing found duplicates in a second Set prevents reporting the same value more than once if it appears three or more times.
• Alternative – sorting the array first lets you compare neighbours with no extra set, at the cost of O(n log n) time and loss of original order.

What is the problem?

Given an array of elements, find all elements that appear more than once. The simplest and most efficient general approach uses a HashSet to detect duplicates in a single linear pass.

At the National Bank of India, Rajesh receives a nightly batch of processed transaction IDs from a payment partner. Because of retries, the same ID sometimes appears twice. Posting a duplicate would double-charge a customer like Priya, so before posting Rajesh scans the batch for duplicates.

Why use a HashSet?

A HashSet stores only unique elements and offers average O(1) time for add, contains, and remove. The key insight is the return value of add(): it returns true when the element is new and false when it already exists. That single boolean is the elegant core of duplicate detection.

• No need to call contains separately before adding.
• One method call both checks and inserts.
• Average constant time per element, so the full scan is O(n).

package com.bank.service;

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

public class DuplicateDetector {
    public static Set<String> findDuplicates(String[] transactionIds) {
        Set<String> seen = new HashSet<>();
        Set<String> duplicates = new HashSet<>();
        for (String id : transactionIds) {
            if (!seen.add(id)) {
                duplicates.add(id);
            }
        }
        return duplicates;
    }
}

How does the algorithm work step by step?

The algorithm walks through the array once. For each element, it calls seen.add(element). If the return value is false, the element was already in the set, so it is a duplicate and gets added to the duplicates set.

package com.bank.service;

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

public class DuplicateDemoStepByStep {
    public static void main(String[] args) {
        String[] ids = {"TXN-101", "TXN-102", "TXN-101", "TXN-103", "TXN-102", "TXN-101"};
        Set<String> seen = new HashSet<>();
        Set<String> duplicates = new HashSet<>();

        for (String id : ids) {
            boolean isNew = seen.add(id);
            System.out.println("Processing " + id + " -> add returned " + isNew);
            if (!isNew) {
                duplicates.add(id);
            }
        }
        System.out.println("Duplicates: " + duplicates);
    }
}

Processing TXN-101 -> add returned true
Processing TXN-102 -> add returned true
Processing TXN-101 -> add returned false
Processing TXN-103 -> add returned true
Processing TXN-102 -> add returned false
Processing TXN-101 -> add returned false
Duplicates: [TXN-101, TXN-102]

Why collect duplicates into a Set rather than a List?

If an element appears three or more times, a List would record it as a duplicate on every repeat. A Set ensures each duplicate value is reported exactly once.

// Wrong: List records TXN-101 twice as a duplicate
List<String> dupList = new ArrayList<>();
// ids = {"TXN-101", "TXN-101", "TXN-101"}
// dupList becomes [TXN-101, TXN-101]

// Correct: Set records TXN-101 once
Set<String> dupSet = new HashSet<>();
// dupSet becomes [TXN-101]

How to count the frequency of each duplicate?

When you need how many times each value appears, switch from a HashSet to a HashMap frequency counter.

package com.bank.service;

import java.util.HashMap;
import java.util.Map;

public class FrequencyCounter {
    public static Map<String, Integer> countFrequencies(String[] transactionIds) {
        Map<String, Integer> freq = new HashMap<>();
        for (String id : transactionIds) {
            freq.merge(id, 1, Integer::sum);
        }
        return freq;
    }

    public static void main(String[] args) {
        String[] ids = {"TXN-101", "TXN-102", "TXN-101", "TXN-103", "TXN-102", "TXN-101"};
        Map<String, Integer> freq = countFrequencies(ids);
        freq.forEach((id, count) -> {
            if (count > 1) {
                System.out.println(id + " appeared " + count + " times");
            }
        });
    }
}

TXN-101 appeared 3 times
TXN-102 appeared 2 times

What is the time and space complexity?

| Approach | Time | Space | Preserves Order? |
|---|---|---|---|
| HashSet scan | O(n) | O(n) | Yes |
| Sorting + neighbour compare | O(n log n) | O(1) | No |
| Brute-force nested loops | O(n^2) | O(1) | Yes |
| HashMap frequency count | O(n) | O(n) | Yes |

The HashSet approach is the standard choice: linear time, linear space, and it preserves the original array order.

What are common mistakes?

A common mistake is using contains followed by add as two separate calls, which works but is redundant.

// Redundant: two hash lookups per element
if (seen.contains(id)) {
    duplicates.add(id);
} else {
    seen.add(id);
}

// Clean: one hash lookup per element
if (!seen.add(id)) {
    duplicates.add(id);
}

Another mistake when dealing with BigDecimal amounts in banking is relying on equals instead of compareTo. Two BigDecimal values like 100 and 100.00 are not equal by equals but are equal by compareTo.

import java.math.BigDecimal;

BigDecimal a = new BigDecimal("100");
BigDecimal b = new BigDecimal("100.00");
System.out.println(a.equals(b));      // false (different scale)
System.out.println(a.compareTo(b));   // 0 (same value)

What are the edge cases?

• Empty array: return an empty set immediately.
• All elements identical: every element after the first is a duplicate.
• No duplicates: the seen set grows to the array size and the duplicates set stays empty.
• Null elements: HashSet allows one null, so a second null is correctly detected as a duplicate.

String[] edge1 = {};                          // result: []
String[] edge2 = {"TXN-101", "TXN-101"};      // result: [TXN-101]
String[] edge3 = {"TXN-101", "TXN-102"};      // result: []
String[] edge4 = {null, "TXN-101", null};     // result: [null]

What about the sorting alternative?

If extra space is not available and modifying the input is acceptable, sort the array first and then compare each element with its neighbour.

package com.bank.service;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class SortBasedDuplicateFinder {
    public static List<String> findDuplicates(String[] ids) {
        Arrays.sort(ids);
        List<String> duplicates = new ArrayList<>();
        for (int i = 1; i < ids.length; i++) {
            if (ids[i].equals(ids[i - 1])) {
                if (duplicates.isEmpty() || !duplicates.get(duplicates.size() - 1).equals(ids[i])) {
                    duplicates.add(ids[i]);
                }
            }
        }
        return duplicates;
    }
}

This uses O(1) extra space (ignoring the sort's internal stack) but costs O(n log n) time and destroys the original order.

What should a senior engineer know?

A senior engineer considers the space-time tradeoff and the data characteristics.

• HashSet is the standard answer: simple, fast, preserves order, but uses O(n) extra memory.
• Sorting trades time and order for zero extra space.
• Bloom filter is an approximate structure that trades a tiny false-positive rate for drastically less memory, useful for very large or streaming datasets.
• Bit vector can replace the HashSet when elements are non-negative integers in a known range, using one bit per possible value.
• In concurrent systems, use ConcurrentHashMap.newKeySet() or Collections.synchronizedSet() to make the set thread-safe.

What are common interview follow-up questions?

• How would you find the first duplicate in the order of the array? (Return immediately on the first add returning false.)
• How would you find all elements that appear exactly twice? (Use a frequency map and filter for count equals two.)
• Can you solve it in O(1) space without sorting? (Only if elements are in range 0 to n-1, using the index-marking trick.)
• How would you handle this for a stream of data? (Use the HashSet approach since it processes elements one at a time.)