JavaScript Set and Big O Notation

Understanding the time complexity (Big O notation) of Set operations is crucial for building efficient algorithms. Here’s a detailed guide on the Big O notation of Set operations and practical examples of how to use them to build more efficient algorithms.

Big O Notation of Set Operations

1. Insertion (add): O(1)

   • Adding an element to a Set is generally an O(1) operation because it involves hashing the element and storing it in the appropriate bucket.

2. Deletion (delete): O(1)

   • Deleting an element from a Set is also O(1) on average, as it involves locating the element's bucket and removing it.

3. Check Existence (has): O(1)

   • Checking if an element exists in a Set is an O(1) operation since it only requires computing the hash of the element and checking the corresponding bucket.

4. Iteration: O(n)

   • Iterating over all elements in a Set is O(n), where n is the number of elements in the Set.

Practical Examples of Using Set for Efficient Algorithms

Example 1: Removing Duplicates from an Array

Problem: Given an array, remove all duplicate elements.

Solution: Use a Set to efficiently handle duplicates.

function removeDuplicates(arr) {
  return [...new Set(arr)]
}

const numbers = [1, 2, 2, 3, 4, 4, 5]
console.log(removeDuplicates(numbers)) // Output: [1, 2, 3, 4, 5]

Analysis:

• Time Complexity: O(n) because converting the array to a Set and back involves iterating over each element.
• Space Complexity: O(n) for storing the unique elements.

Example 2: Checking for Duplicates in an Array

Problem: Check if an array contains any duplicates.

Solution: Use a Set to keep track of seen elements and detect duplicates efficiently.

function hasDuplicates(arr) {
  const seen = new Set()
  for (let item of arr) {
    if (seen.has(item)) {
      return true
    }
    seen.add(item)
  }
  return false
}

const numbers = [1, 2, 3, 4, 5, 6]
console.log(hasDuplicates(numbers)) // Output: false

const numbersWithDuplicates = [1, 2, 3, 4, 5, 6, 3]
console.log(hasDuplicates(numbersWithDuplicates)) // Output: true

Analysis:

• Time Complexity: O(n) because we iterate over the array once.
• Space Complexity: O(n) for storing elements in the Set.

Example 3: Finding Intersection of Two Arrays

Problem: Find the common elements between two arrays.

Solution: Use two Set objects to store the elements of each array and find the intersection.

function intersection(arr1, arr2) {
  const set1 = new Set(arr1)
  const set2 = new Set(arr2)
  return [...set1].filter((item) => set2.has(item))
}

const array1 = [1, 2, 3, 4]
const array2 = [3, 4, 5, 6]
console.log(intersection(array1, array2)) // Output: [3, 4]

Analysis:

• Time Complexity: O(n + m), where n and m are the lengths of the two arrays.
• Space Complexity: O(n + m) for storing elements in the two Set objects.

Example 4: Unique Substring Length

Problem: Given a string, find the length of the longest substring without repeating characters.

Solution: Use a sliding window technique with a Set to keep track of characters in the current window.

function lengthOfLongestSubstring(s: string): number {
  let charSet: Set<string> = new Set()
  let start: number = 0
  let maxLength: number = 0

  for (let end: number = 0; end < s.length; end++) {
    while (charSet.has(s[end])) {
      charSet.delete(s[start])
      start++
    }
    charSet.add(s[end])
    maxLength = Math.max(maxLength, end - start + 1)
  }

  return maxLength
}

const s1 = 'abcabcbb'
console.log(lengthOfLongestSubstring(s1)) // Output: 3

const s2 = 'bbbbb'
console.log(lengthOfLongestSubstring(s2)) // Output: 1

const s3 = 'pwwkew'
console.log(lengthOfLongestSubstring(s3)) // Output: 3

Analysis:

• Time Complexity: O(n), because each character is processed at most twice.
• Space Complexity: O(min(n, m)), where n is the length of the string and m is the character set size.

Summary

• Insertion, Deletion, and Existence Check: All have O(1) average time complexity, making Set highly efficient for operations that require frequent membership checks or uniqueness.
• Iteration: O(n) time complexity for iterating over all elements.

By leveraging the efficient operations of Set, you can significantly improve the performance of algorithms that require frequent membership checks, uniqueness constraints, or set operations like union, intersection, and difference.