Java: Contains Duplicate

Thought Process

To determine if an array contains duplicate elements, we can use a 'set' data structure. A set automatically eliminates duplicate values, so by inserting all elements of the array into the set, we can compare the size of the set with the size of the original array. If the sizes differ, it means there were duplicates in the array. 

class Solution {
    public boolean containsDuplicate(int[] nums) {
              
        Set<Integer> st = new HashSet<>();
              
        for(int i=0;i<nums.length;i++){
            if(st.contains(nums[i]))
                return true;
            else
                st.add(nums[i]);
        }
        return false;
    }
}

Code Complexity

Time Complexity: O(n)

The algorithm inserts all elements of the array into a set, which takes O(n) time, where 'n' is the number of elements in the array. Checking the size of the set is a constant-time operation.

Space Complexity: O(n)

The set stores at most 'n' elements, where 'n' is the size of the input array. In the worst case, if all elements are unique, the set will store all 'n' elements.

Code copied!