217. Contains Duplicate

https://leetcode.com/problems/contains-duplicate/

Approach

1. Brute force

   take the first element and compare it to every other element that would be n operations to check whether the first number is duplicate or not. We have to do it for every number present in the array. Since we comparing all the elements in the array, the overall complexity would be O(n²). But we don't need any auxiliary space.

   

   Time - O(n²)
   Space - O(1)

    const containsDuplicate = (nums: number[]) => {
      const length = nums.length;
      for (let element = 0; element < length; element++) {
        //O(n)
        for (let i = element + 1; i < length; i++) {
          //  Time O(n)
          const isDuplicate = nums[element] === nums[i];
          if (isDuplicate) return true;
        }
      }
      return false;
    };
   

2. Sort the array and compare elements to its neighbor

   If we sort the array, it will look different. Now if any duplicates exist in the array, they will be adjacent.

   

   Time - O(N * logN) for sorting the array and O(N) for comparing the adjacent

   Total - O(N * logN)

Space - O(1 || log(N) || N) Depends which sorting algorithms we are using
HeapSort Space O(1) , QuickSort Space O(log(N)) , MergeSort Space O(N)

    const containsDuplicate2 = (nums: number[]) => {

      nums.sort((a, b) => a - b);
      const length = nums.length;
      for (let element = 0; element < length; element++) {
        const neighbor = element + 1;
        const isDuplicate = nums[element] === nums[neighbor];
        if (isDuplicate) return true;
      }
    };

3. Using HashSet data structure
   HashSet stores a collection of unique elements. It is typically used when we need to quickly check whether a specific element is present in the set or not. HashSet allows to insert element on O(1) complexity. we are going to insert the elements one by one into the HashSet and check if an element is already present in the HashSet so there is a duplicate element in the array

   

   Time - O(n) to insert all the elements into HashSet
   Space - O(n)

    const containsDuplicate3 = (nums: number[]) => {
      const numsSet = new Set()
   
      for(const element of nums){
        if(numsSet.has(element)){
          return true
        }
        numsSet.add(element)
      }
      return false
    };