Contains Duplicates

Tags:

Introduction

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
Explanation: "1" repeated twice.
Example 2
Input: nums = [1, 2, 3, 4]
Output: true
Explanation: all numbers in array are distinct.

Contents

Solution 1 - Using brute force approach

In this approach, in a nested for loop, we will check that every number at index i in nums, exists anywhere between i+1 to n in nums, if it exists that means we have found a duplicate.

  • We will create a function bruteForceApproach that takes input array nums and returns a boolean value true if a duplicate is found and false otherwise. 

public class ContainsDuplicates {

    /* brute force approach */
    static boolean bruteForceApproach(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;
    }


}
Complexity Analysis:

Time complexity: Above code runs in O(n2) time where n is the length of nums array, this is because we are looping through nums array in a nested for loop.
Space complexity: O(1) since we are only doing a numbers comparision and returning true or false.

Solution 2 - Using sorting approach, sort elements first, then check any two consecutive elements are same

In this approach, we we will sort the input array as first step, then loop through the elements of sorted array, and check if any two consecutive elements are same or not, if any two are same return true, false otherwise. 


import java.util.Arrays;
import java.util.HashSet;

public class ContainsDuplicates {

    /* using sorting approach */
    static boolean usingSortingApproach(int[] nums) {
        Arrays.sort(nums); // O(n log n)
        for(int i=1; i<nums.length; i++) {
            if(nums[i] == nums[i-1]) {
                return true;
            }
        }
        return false;
    }

}
Complexity Analysis:

Time complexity: Above code runs in O(n log (n)) time where n is the length of nums array, this is because we are sorting elements first which takes O(n log (n)), then looping through sorted nums array, which takes O(n).
Space complexity: O(1), assuming that sorting will be using an in-place algorithm like QuickSort.

Solution 3 - using HashSet to keep track of numbers

In this approach, we are going to use a HashSet to keep track of numbers from nums array.

As we loop through nums array, we check whether that number already exists in the set or not, if it exists we will return true otherwise we will add it to set and continue. At the end we will return false, it only comes here if all numbers are distinct. 


import java.util.HashSet;

public class ContainsDuplicates {

    /* Using hashset, store values into set and check if duplicate exists before putting a number into it */
    static boolean usingHashSet(int[] nums) {
        HashSet<Integer> cache = new HashSet<>();
        for(int i=0; i<nums.length; i++) {
            if(cache.contains(nums[i])) {
                return true;
            }
            cache.add(nums[i]);
        }
        return false;
    }

}
Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the length of nums array since we are looping through input array only once.
Space complexity: O(n) since we are caching numbers into HashSet.

Above implementations source code can be found at GitHub link for Java code