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)