Leetcode 217) Contains Duplicate

10 Nov 2021 in Algorithms

My Solution

• Time Complexity : O(n) => Set has constant search and insert time
• Space Complexity : O(n) => Creating new data structure from given array.

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

Other Solution

• Time Complexity : O(n lon n) => Arrays.sort algo takes O(n log n)
• Space Complexity : O(1)

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Arrays.sort(nums);
        for(int i=0;i<nums.length-1;i++)
        {
            if(nums[i]==nums[i+1])
                return true;
        }
        return false;
    }
}