JavaScript Set and Big O Notation

Understanding the time complexity (Big O notation) of Set operations is crucial for building efficient algorithms. In this guide, we’ll cover insertion, deletion, existence checks, and iteration complexities, with practical examples and links to related topics such as JavaScript Map and Big O Notation and Searching & Sorting Algorithms in JavaScript.

Big O Notation of Set Operations

1. Insertion (add): O(1)
   • Adding an element to a Set is generally O(1), as it hashes the element and stores it in the appropriate bucket. For comparisons with other structures, see JavaScript Prototype Chain & performance considerations.
2. Deletion (delete): O(1)
   • Removing an element is O(1) on average, locating the element’s bucket and removing it.
3. Check Existence (has): O(1)
   • Checking membership requires hashing the element and inspecting the bucket.
4. Iteration: O(n)
   • Iterating over all elements is O(n). For patterns of iteration with large data, consider Streams and Lazy Evaluation.

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 handle uniqueness.

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) to iterate and build the Set, then convert back.
• Space Complexity: O(n) for storing unique elements.
• Related: For other duplicate-detection patterns, see Memoization in JavaScript.

Example 2: Checking for Duplicates in an Array

Problem: Check if an array contains any duplicates.

Solution: Track seen elements in a Set.

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) for a single pass.
• Space Complexity: O(n) for the Set.
• Related: Similar patterns apply when grouping or counting with a Map, see JavaScript Map and Big O Notation.

Example 3: Finding Intersection of Two Arrays

Problem: Find common elements between two arrays.

Solution: Use two Set objects and filter.

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) for lengths of both arrays.
• Space Complexity: O(n + m) for the two Set objects.
• Related: For union or difference operations and performance, see Functional Programming in JS.

Example 4: Unique Substring Length (Sliding Window)

Problem: Find the length of the longest substring without repeating characters.

Solution: Sliding window with a Set.

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), each character enters/exits window at most once.
• Space Complexity: O(min(n, m)), with m = charset size.
• Related: For more on event-loop and async patterns in JS, see Promises & Async/Await: microtasks vs. macrotasks.

Performance Considerations

When using Set:

• Browser Support: Modern browsers support Set; polyfill for legacy if needed.
• Memory Overhead: Profile when storing large sets; for streaming large data, see Streams and Lazy Evaluation.
• Combined Patterns: Use Set with debounce/throttle for event-heavy operations—see Debounce & Throttle: Controlling Function Execution.
• Algorithm Choices: Compare with Map for cases needing key-value pairs—see JavaScript Map and Big O Notation.

Summary

• Insertion, Deletion, Existence Check: O(1) average, ideal for membership and uniqueness.
• Iteration: O(n).
• Use Set for duplicate removal, intersection, sliding-window substring problems, and any algorithm requiring fast membership checks.
• For overall performance practices, see Why Website Performance Matters.

Further Reading

• Searching & Sorting Algorithms in JavaScript
• Dynamic Programming: Tabulation vs. Memoization
• Streams and Lazy Evaluation
• Memoization in JavaScript
• JavaScript Map and Big O Notation
• Debounce & Throttle: Controlling Function Execution
• Promises & Async/Await: microtasks vs. macrotasks
• Why Website Performance Matters