Duplicate Finder

Problem Statement

Write a Java program that implements a method to check if an array of integers contains any duplicate elements. The method should return true if there are duplicates and false otherwise. Test the method with both sorted and unsorted arrays, including edge cases like empty arrays, single-element arrays, and arrays with multiple duplicates. You can visualize this as checking a list of student IDs to determine if any ID appears more than once, whether the list is sorted or unsorted.

Input: An array of integers (e.g., arr = [1, 2, 3, 1] or arr = [1, 1, 2, 3]). Output: A boolean indicating whether the array contains duplicate elements (e.g., true for [1, 2, 3, 1], false for [1, 2, 3, 4]). Constraints:

• The array length is between 0 and 10^5.
• Elements are integers between -10^9 and 10^9.
• The array may be empty. Example:
• Input: arr = [1, 2, 3, 1]
• Output: true
• Explanation: The element 1 appears twice, so the array contains duplicates.
• Input: arr = [1, 2, 3, 4]
• Output: false
• Explanation: All elements are unique.

Pseudocode

FUNCTION hasDuplicates(arr)
    IF arr is null OR length of arr <= 1 THEN
        RETURN false
    ENDIF
    CREATE empty HashSet seen
    FOR each element in arr
        IF element exists in seen THEN
            RETURN true
        ELSE
            ADD element to seen
        ENDIF
    ENDFOR
    RETURN false
ENDFUNCTION

FUNCTION main()
    SET testArrays to arrays of integers
    FOR each array in testArrays
        CALL hasDuplicates(array)
        PRINT result
    ENDFOR
ENDFUNCTION

Algorithm Steps

1. Check if the input array is null or has 0 or 1 element. If so, return false, as duplicates are not possible.
2. Create an empty HashSet to store seen elements.
3. Iterate through the array: a. For each element, check if it exists in the HashSet. b. If the element is in the HashSet, return true, as a duplicate has been found. c. Otherwise, add the element to the HashSet.
4. If the loop completes without finding duplicates, return false.
5. In the main method, create test arrays (sorted and unsorted) with various cases and call the hasDuplicates method to verify correctness.

Java Implementation

import java.util.HashSet;

public class DuplicateFinder {
    // Checks if array contains duplicate elements
    public boolean hasDuplicates(int[] arr) {
        // Check for null or single-element/empty array
        if (arr == null || arr.length <= 1) {
            return false;
        }
        // Use HashSet to track seen elements
        HashSet<Integer> seen = new HashSet<>();
        // Iterate through array
        for (int num : arr) {
            // If element is already in set, duplicate found
            if (seen.contains(num)) {
                return true;
            }
            // Add element to set
            seen.add(num);
        }
        // No duplicates found
        return false;
    }

    // Main method to test hasDuplicates with various arrays
    public static void main(String[] args) {
        DuplicateFinder finder = new DuplicateFinder();

        // Test case 1: Unsorted array with duplicates
        int[] arr1 = {1, 2, 3, 1};
        System.out.println("Test case 1 (unsorted with duplicates): " + finder.hasDuplicates(arr1));

        // Test case 2: Sorted array with duplicates
        int[] arr2 = {1, 1, 2, 3};
        System.out.println("Test case 2 (sorted with duplicates): " + finder.hasDuplicates(arr2));

        // Test case 3: Unsorted array without duplicates
        int[] arr3 = {1, 2, 3, 4};
        System.out.println("Test case 3 (unsorted without duplicates): " + finder.hasDuplicates(arr3));

        // Test case 4: Empty array
        int[] arr4 = {};
        System.out.println("Test case 4 (empty): " + finder.hasDuplicates(arr4));

        // Test case 5: Single-element array
        int[] arr5 = {5};
        System.out.println("Test case 5 (single element): " + finder.hasDuplicates(arr5));

        // Test case 6: Array with negative numbers and duplicates
        int[] arr6 = {-1, 2, -1, 3};
        System.out.println("Test case 6 (negative numbers with duplicates): " + finder.hasDuplicates(arr6));
    }
}

Output

Running the main method produces:

Test case 1 (unsorted with duplicates): true
Test case 2 (sorted with duplicates): true
Test case 3 (unsorted without duplicates): false
Test case 4 (empty): false
Test case 5 (single element): false
Test case 6 (negative numbers with duplicates): true

Explanation:

• Test case 1: [1, 2, 3, 1] returns true (duplicate 1).
• Test case 2: [1, 1, 2, 3] returns true (duplicate 1).
• Test case 3: [1, 2, 3, 4] returns false (no duplicates).
• Test case 4: [] returns false (empty array).
• Test case 5: [5] returns false (single element).
• Test case 6: [-1, 2, -1, 3] returns true (duplicate -1).

How It Works

• Step 1: The hasDuplicates method checks if the array is null or has 0 or 1 element. For [1, 2, 3, 1], it proceeds.
• Step 2: Initialize an empty HashSet seen.
• Step 3: Iterate through [1, 2, 3, 1]:
  • Element 1: Not in seen, add 1 to seen.
  • Element 2: Not in seen, add 2 to seen.
  • Element 3: Not in seen, add 3 to seen.
  • Element 1: In seen, return true.
• Example Trace: For [1, 2, 3, 1], seen grows: {1} → {1, 2} → {1, 2, 3}, then detects duplicate 1, returning true.
• Main Method: Tests the method with sorted and unsorted arrays, including duplicates, no duplicates, empty, single-element, and negative numbers.
• HashSet Efficiency: The HashSet provides O(1) average-time lookups and insertions, making the algorithm efficient for both sorted and unsorted arrays.

Complexity Analysis Table

Note:

• n is the size of the input array.
• Time complexity: O(n), as the algorithm iterates through the array once, with O(1) average-time HashSet operations.
• Space complexity: O(n), as the HashSet may store up to n elements in the worst case.
• Best, average, and worst cases are O(n) for time; space depends on the number of unique elements.

✅ Tip: Use a HashSet for efficient duplicate detection in both sorted and unsorted arrays. Test with edge cases like empty arrays, single-element arrays, and arrays with negative numbers to ensure robustness.

⚠ Warning: Ensure the input array is not null to avoid NullPointerException. Be mindful of memory usage for very large arrays, as the HashSet requires O(n) space.