Set Operations (Union, Intersection, Difference)

Beyond simply storing and checking for unique elements, Sets truly shine when performing mathematical set operations. These operations combine or compare two or more sets to produce a new set based on specific rules. Understanding these is crucial for many data manipulation and algorithmic tasks.

For these examples, let Set A and Set B be two distinct Set objects.

1. Union: `A ∪ B` (A "or" B)

The union of two sets A and B is a new set containing all unique elements that are in A, or in B, or in both. Duplicates are automatically handled by the nature of Sets.

Concept:
1. Create a new empty result Set.
2. Add all elements from Set A to the result Set.
3. Add all elements from Set B to the result Set. Since Sets only store unique values, any elements already added from Set A that also exist in Set B will not be re-added.
Time Complexity: O(N + M) where N is the size of Set A and M is the size of Set B. This is because we essentially iterate through both sets once.
Space Complexity: O(N + M) in the worst case (if A and B have no common elements and all elements are unique).

JavaScript Example:

const setA = new Set([1, 2, 3, 4]);
const setB = new Set([3, 4, 5, 6]);

// Method 1: Using forEach (explicit iteration)
function unionSetsForEach(set1, set2) {
  const unionResult = new Set();
  set1.forEach(item => unionResult.add(item));
  set2.forEach(item => unionResult.add(item));
  return unionResult;
}
console.log("Union (forEach):", unionSetsForEach(setA, setB)); // Set(6) { 1, 2, 3, 4, 5, 6 }

// Method 2: Using spread operator (concise and common)
function unionSetsSpread(set1, set2) {
  return new Set([...set1, ...set2]);
}
console.log("Union (spread):", unionSetsSpread(setA, setB));   // Set(6) { 1, 2, 3, 4, 5, 6 }

// Example with objects (uses reference equality)
const obj1 = { id: 1 };
const obj2 = { id: 2 };
const obj3 = { id: 3 };
const setC = new Set([obj1, obj2]);
const setD = new Set([obj2, obj3]); // obj2 is the same reference
console.log("Union (objects):", unionSetsSpread(setC, setD)); // Set(3) { { id: 1 }, { id: 2 }, { id: 3 } }

2. Intersection: `A ∩ B` (A "and" B)

The intersection of two sets A and B is a new set containing only the elements that are common to both A and B.

Concept:
1. Create a new empty result Set.
2. Iterate through the elements of one set (e.g., Set A).
3. For each element, check if it also exists in the other set (Set B) using the .has() method.
4. If it exists in both, add it to the result Set.
Time Complexity: O(min(N, M)) on average. We iterate through the smaller set and perform has() checks on the larger set. Since has() is O(1) on average, the complexity is dominated by the size of the smaller set.
Space Complexity: O(K) where K is the number of common elements (at most min(N, M)).

JavaScript Example:

const setA = new Set([1, 2, 3, 4]);
const setB = new Set([3, 4, 5, 6]);

function intersectionSets(set1, set2) {
  const intersectionResult = new Set();
  // It's more efficient to iterate over the smaller set
  const [smallerSet, largerSet] = set1.size < set2.size ? [set1, set2] : [set2, set1];

  smallerSet.forEach(item => {
    if (largerSet.has(item)) {
      intersectionResult.add(item);
    }
  });
  return intersectionResult;
}
console.log("Intersection:", intersectionSets(setA, setB)); // Set(2) { 3, 4 }

// Example with no common elements
const setX = new Set([10, 20]);
const setY = new Set([30, 40]);
console.log("Intersection (no common):", intersectionSets(setX, setY)); // Set(0) {}

3. Difference: `A \ B` or `A - B` (A "minus" B)

The difference of two sets A and B (read as "A minus B") is a new set containing all elements that are in A but NOT in B.

Concept:
1. Create a new empty result Set.
2. Iterate through the elements of Set A.
3. For each element, check if it does not exist in Set B using the .has() method.
4. If it's only in A (and not in B), add it to the result Set.
Time Complexity: O(N) on average, where N is the size of Set A. We iterate through Set A and perform has() checks on Set B.
Space Complexity: O(K) where K is the number of elements unique to Set A (at most N).

JavaScript Example:

const setA = new Set([1, 2, 3, 4]);
const setB = new Set([3, 4, 5, 6]);

function differenceSets(set1, set2) {
  const differenceResult = new Set();
  set1.forEach(item => {
    if (!set2.has(item)) {
      differenceResult.add(item);
    }
  });
  return differenceResult;
}

console.log("Difference (A - B):", differenceSets(setA, setB)); // Set(2) { 1, 2 }
console.log("Difference (B - A):", differenceSets(setB, setA)); // Set(2) { 5, 6 }

Tip: These set operations are fundamental building blocks for many algorithms, particularly those involving unique collections, filtering data, or analyzing relationships between groups of items. The efficiency of JavaScript's built-in Set makes these operations perform very well for most practical scenarios.