King Of Interviews

Contains Duplicate: 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.

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9

Try this Problem on your own or check similar problems:

Solution:

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

Time/Space Complexity:

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

Explanation:

Your first hint should be the term duplicate and it should trigger you to think about the data structure that has a natural property of deduplication (removal of duplicated elements). So Set is a good option for this problem. We loop over all number in the input and check if the set already contains the value, if it does we simply return true from our function, otherwise we add the current element to the set. If the loop has finished without the function terminating earlier it means there are no duplicate numbers in our input array and we can return false. The time complexity is O(n) where n is the length of input array since we (at most) loop once over the input. Since we have an auxiliary (helper) data structure in this case the space complexity will be O(n).

Bonus:

For Java streams lovers we can tranform the top solution to a one-liner:

public boolean containsDuplicate(int[] nums) {
  return !Arrays.stream(nums).allMatch(new HashSet()::add);
}

Here we use the property of HashSet()::add which returns false if the element is already present in the set (otherwise true), and we check that predicate on all numbers in input array which is converted to a stream. If all numbers are added successfully the negation ! will return false, otherwise true if there are any duplicates.

Note: You can solve this problem with two loops, basically running comparison for each element against all the next elements in array turning the time complexity to O(n^2). Another way would be to sort array (time complexity O(nlogn)) and then compare each element with it’s previous neighbour (duplicate elements will appear next to each other in sorted array).

Contains Duplicate