1. Contains Duplicate

Here’s a detailed list of all approaches to checking for duplicates in an array, implemented in Java, from brute force to optimal methods, with their time and space complexities:

1. Brute Force Approach – O(n²)

Logic: Compare every element with every other element

Use two nested loops to compare each element with every other element.

Time Complexity: O(n²)
Space Complexity: O(1)

Java Code:

public class ContainsDuplicateBruteForce {
    public static boolean containsDuplicate(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] == nums[j]) {
                    return true;  // Duplicate found
                }
            }
        }
        return false;  // No duplicates
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5, 2};
        System.out.println(containsDuplicate(nums));  // Output: true
    }
}

2. Sorting-Based Approach – O(n log n)

Logic: Sort the array and check for adjacent duplicates

Sort the array in O(n log n) and then check if any two consecutive elements are the same.

Time Complexity: O(n log n)
Space Complexity: O(1) (if sorting is in-place)

Java Code:

import java.util.Arrays;

public class ContainsDuplicateSorting {
    public static boolean containsDuplicate(int[] nums) {
        Arrays.sort(nums);  // Sort the array
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] == nums[i + 1]) {
                return true;  // Duplicate found
            }
        }
        return false;  // No duplicates
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5, 2};
        System.out.println(containsDuplicate(nums));  // Output: true
    }
}

3. HashSet Approach (Optimal) – O(n)

Logic: Use a `HashSet` to store unique elements

Traverse the array and store each element in a HashSet. If an element already exists in the set, return true.

Time Complexity: O(n)
Space Complexity: O(n)

Java Code:

import java.util.HashSet;

public class ContainsDuplicateHashSet {
    public static boolean containsDuplicate(int[] nums) {
        HashSet<Integer> seen = new HashSet<>();
        for (int num : nums) {
            if (seen.contains(num)) {
                return true;  // Duplicate found
            }
            seen.add(num);
        }
        return false;  // No duplicates
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5, 2};
        System.out.println(containsDuplicate(nums));  // Output: true
    }
}

4. HashMap (Frequency Count) – O(n)

Logic: Store frequencies of elements in a `HashMap`

Traverse the array and store the frequency of each element in a HashMap. If any element has a count greater than 1, return true.

Time Complexity: O(n)
Space Complexity: O(n)

Java Code:

import java.util.HashMap;

public class ContainsDuplicateHashMap {
    public static boolean containsDuplicate(int[] nums) {
        HashMap<Integer, Integer> frequencyMap = new HashMap<>();
        for (int num : nums) {
            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
            if (frequencyMap.get(num) > 1) {
                return true;  // Duplicate found
            }
        }
        return false;  // No duplicates
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5, 2};
        System.out.println(containsDuplicate(nums));  // Output: true
    }
}

5. Using Java Streams and Sets (Java 8+)

Logic: Compare the size of the original array with the size of a `Set` (which removes duplicates)

If the set size is smaller than the array size, duplicates are present.

Time Complexity: O(n)
Space Complexity: O(n)

Java Code (Using Streams in Java 8+):

import java.util.Arrays;
import java.util.Set;
import java.util.stream.Collectors;

public class ContainsDuplicateUsingStreams {
    public static boolean containsDuplicate(int[] nums) {
        Set<Integer> uniqueSet = Arrays.stream(nums).boxed().collect(Collectors.toSet());
        return uniqueSet.size() != nums.length;  // Compare set size with array size
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5, 2};
        System.out.println(containsDuplicate(nums));  // Output: true
    }
}

Summary of Approaches and Complexities:

Approach	Time Complexity	Space Complexity	Description
Brute Force	`O(n²)`	`O(1)`	Compare each element with every other
Sorting-Based	`O(n log n)`	`O(1)` (in-place)	Sort array and check adjacent elements
HashSet (Optimal)	`O(n)`	`O(n)`	Store unique elements in a `HashSet`
HashMap (Frequency Count)	`O(n)`	`O(n)`	Store element counts in a `HashMap`
Using Streams and Set	`O(n)`	`O(n)`	Compare array size with `Set` size

Best Approach Recommendation:

The HashSet Approach is usually the best solution due to its simplicity, efficiency, and linear time complexity O(n).
For modern Java, the Streams approach is concise and elegant if you prefer functional programming.