How would you check for duplicates in an array of one million numbers?

To check for duplicates in an array of one million numbers, several approaches can be used:

1. Using HashSet:
   • Iterate through the array, adding each element to a HashSet.
   • If the element already exists in the HashSet, a duplicate is found.

import java.util.HashSet;

public boolean hasDuplicates(int[] arr) {
    HashSet<Integer> set = new HashSet<>();
    for (int num : arr) {
        if (!set.add(num)) {
            return true; // duplicate found
        }
    }
    return false; // no duplicates
}

2. Sorting the array:
   • Sort the array.
   • Iterate through it and check neighboring elements for equality.

This method requires O(n log n) time for sorting, while HashSet typically operates in O(n) time.

For an array of a million elements, HashSet is the optimal choice in terms of time, assuming sufficient memory.