// Contains Duplicate - https://leetcode.com/problems/contains-duplicate/

class Solution {
    // Brute force 
    // Time Complexity: O(n^2)
    // Space Complexity: O(1)
    // Below solution leads to time limit exceeded on LeetCode
    // public 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;
    //             }
    //         }
    //     }

    //     return false;
    // }

    // Using HashSet
    // Time Complexity: O(n)
    // Space Complexity: O(n)
    // public boolean containsDuplicate(int[] nums) {
    //     Set set = new HashSet<>();

    //     for(int i = 0; i < nums.length; i++) {
    //         set.add(nums[i]);
    //     }

    //     return set.size() != nums.length;
    // }

    // Using HashSet (Optimized)
    // Time Complexity: O(n)
    // Space Complexity: O(n)
    public boolean containsDuplicate(int[] nums) {
        Set set = new HashSet<>();

        for(int i = 0; i < nums.length; i++) {
            if(set.contains(nums[i])) {
                return true;
            }

            set.add(nums[i]);
        }

        return false;
    }
}