Contains Duplicate: Check Using a HashSet in O(n)

• Contains Duplicate – a problem that asks whether any value appears more than once in a collection.
• HashSet approach – scan the collection once, calling add() for each element; add() returns false when the element already exists, signalling a duplicate.
• Time complexity – average O(n) because each add() is O(1) average, one per element.
• Space complexity – O(n) for the set, the classic time-for-space trade-off.
• Alternative – sort first, then scan adjacent elements for O(n log n) time with O(1) extra space if mutation is allowed.

What is the Contains Duplicate problem?

The problem asks whether any value appears more than once in a given collection. It is the simplest duplicate-detection problem and appears as the gateway to harder variants like Contains Duplicate II (within k distance) and Contains Duplicate III (within k distance and t difference). The answer is a simple boolean: true if any duplicate exists, false otherwise.

package com.bank.service;

public class DuplicateChecker {
    // Returns true if any transaction ID appears more than once
    public boolean containsDuplicate(String[] txnIds) {
        // implementation below
        return false;
    }
}

How does the HashSet approach work?

A HashSet stores unique elements and offers average O(1) add and contains. The key trick is that add() returns a boolean: true if the element was newly added, false if it was already present. So you loop over the collection, call add() on each element, and if add() ever returns false, you immediately return true for contains-duplicate. If every add() returns true, there are no duplicates.

package com.bank.service;

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

public class TransactionDuplicateChecker {
    public static boolean hasDuplicate(String[] txnIds) {
        Set<String> seen = new HashSet<>(txnIds.length * 2);
        for (String id : txnIds) {
            if (!seen.add(id)) {
                return true; // duplicate found
            }
        }
        return false; // all unique
    }

    public static void main(String[] args) {
        String[] ids = {"TXN-001", "TXN-002", "TXN-003", "TXN-001"};
        System.out.println("Has duplicate: " + hasDuplicate(ids));
    }
}

Has duplicate: true

Why is this O(n) time and O(n) space?

Each call to add() is O(1) average time because the HashSet hashes the element to a bucket and checks for equality. You make one call per element, so the total is O(n). The space is O(n) because in the worst case every element is unique and the set holds all of them. This is the classic time-for-space exchange: you spend memory to avoid the O(n squared) cost of comparing every pair or the O(n log n) cost of sorting.

// Brute force: O(n^2) time, O(1) space
for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        if (ids[i].equals(ids[j])) return true;
    }
}

// HashSet: O(n) time, O(n) space
Set<String> seen = new HashSet<>();
for (String id : ids) {
    if (!seen.add(id)) return true;
}

How is this different from the sorting approach?

Sorting the array first places duplicates next to each other, so a single scan of adjacent elements detects them. This is O(n log n) time with O(1) extra space if you sort in place, but it mutates the input. The HashSet approach is faster (O(n)) but uses more memory (O(n)). Choose sorting when memory is tight and mutation is acceptable; choose HashSet when speed matters most.

| Approach | Time | Space | Mutates Input |
|---|---|---|---|
| HashSet | O(n) avg | O(n) | No |
| Sort + scan | O(n log n) | O(1) | Yes |
| Brute force | O(n squared) | O(1) | No |

package com.bank.service;

import java.util.Arrays;

public class SortApproach {
    public static boolean hasDuplicate(String[] ids) {
        Arrays.sort(ids);
        for (int i = 1; i < ids.length; i++) {
            if (ids[i].equals(ids[i - 1])) return true;
        }
        return false;
    }
}

What about BigDecimal and the equals/hashCode trap?

When checking for duplicate monetary amounts, BigDecimal's equals() considers scale. So new BigDecimal("100") and new BigDecimal("100.00") are not equal and hash differently. A HashSet would not detect them as duplicates even though they represent the same amount. To fix this, normalise with stripTrailingZeros() before adding.

package com.bank.service;

import java.math.BigDecimal;
import java.util.HashSet;
import java.util.Set;

public class AmountDuplicateChecker {
    public static boolean hasDuplicateAmount(BigDecimal[] amounts) {
        Set<BigDecimal> seen = new HashSet<>();
        for (BigDecimal amount : amounts) {
            BigDecimal normalised = amount.stripTrailingZeros();
            if (!seen.add(normalised)) {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        BigDecimal[] amounts = {
            new BigDecimal("100.00"),
            new BigDecimal("200.50"),
            new BigDecimal("100") // same as 100.00 after normalisation
        };
        System.out.println("Duplicate amount: " + hasDuplicateAmount(amounts));
    }
}

Duplicate amount: true

What are edge cases?

The main edge cases are an empty array (no duplicates, return false), a single-element array (no duplicates), and an array where every element is the same (duplicate found at index 1). The early exit optimisation means that when a duplicate appears near the start, the method returns almost instantly without scanning the rest.

package com.bank.service;

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

public class EdgeCases {
    public static boolean hasDuplicate(int[] nums) {
        if (nums == null || nums.length < 2) return false;
        Set<Integer> seen = new HashSet<>(nums.length * 2);
        for (int num : nums) {
            if (!seen.add(num)) return true;
        }
        return false;
    }

    public static void main(String[] args) {
        System.out.println(hasDuplicate(new int[]{}));       // false
        System.out.println(hasDuplicate(new int[]{42}));     // false
        System.out.println(hasDuplicate(new int[]{5, 5}));   // true
    }
}

false
false
true

What are common mistakes?

The most common mistake is forgetting to pre-size the HashSet. Without a capacity hint, the set starts small and resizes several times as it grows, which wastes time on large batches. Another mistake is using contains() followed by add() as two separate calls instead of using the single add() return value, which doubles the hash lookups.

// Wrong: two hash lookups per element
if (seen.contains(id)) return true;
seen.add(id);

// Correct: one hash lookup per element
if (!seen.add(id)) return true;

What should a senior engineer know?

A senior engineer pre-sizes the set to avoid rehashing, uses the add() return value for a single lookup, handles the BigDecimal scale trap for monetary data, and chooses between the HashSet and sorting approaches based on the memory and mutation constraints. They also know that HashSet is backed by a HashMap internally, so all the same rules about equals/hashCode and thread safety apply.