LeetCode Blind75 #2 - Contains Duplicate (Easy)

Problem Statement

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

Test Cases

TC 1
Input: nums = [1,2,3,1]
Output: true
Explanation: occurrence of 1 is twice in the array.

TC 2
Input: nums = [1,2,3,4]
Output: false

TC 3
Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true

Constraints

1 <= nums.length <= 105
-109 <= nums[i] <= 109

Solutions

#S1 - Naïve Approach

Here, we iterate over each element and try to find its occurrences.

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;
  }

// Time Complexity : O(n^2)
// Space Complexity : O(1)

#S2 - Sort and Search

Here, we sort the array and then check for the consecutive duplicates.

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

// Time Complexity : O(n*logn)
// Space Complexity : O(1)

#S3 - Using HashSet (Collection Framework)

Here, we use HashSet to reduce time complexity from polynomial to linear (Time Space tradeoff ).

public  boolean containsDuplicate(int[] nums) {
         HashSet<Integer> set = new HashSet<Integer>();
         for(int i : nums)
             if(!set.add(i))
                 return true; 
         return false;
}

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

#S4 - Using Stream API (Java 8)

Here, we try to take distinct element form the array and compare the size to the original one.

• Stream API : Used to process collection of objects
• The distict() method is one such stateful intermediate operation that uses the state from previously seen elements from the Stream while processing the new items.
• The count() returns a long value indicating the number of items in the stream.

    public boolean containsDuplicate(int[] nums) {
        return Arrays.stream(nums).distinct().count() < nums.length;
    }

// Time Complexity : O(n), slower than Set
// Space Complexity : O(1)