Set operations (Union, Intersect, Except) in C Sharp (C#) - Time & Space Complexity

Time Complexity: Set operations (Union, Intersect, Except)

O(n + m)

Understanding Time Complexity

When we use set operations like Union, Intersect, and Except, we want to know how long these actions take as the sets get bigger.

We ask: How does the time needed grow when the number of items in the sets grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

var setA = new HashSet<int>() {1, 2, 3, 4, 5};
var setB = new HashSet<int>() {4, 5, 6, 7, 8};

var union = setA.Union(setB).ToHashSet();
var intersect = setA.Intersect(setB).ToHashSet();
var except = setA.Except(setB).ToHashSet();
    

This code creates two sets and finds their union, intersection, and difference.

Identify Repeating Operations

Look at what repeats when doing these set operations.

• Primary operation: Checking each item in one set against the other set.
• How many times: Each item in the first set is checked once, and sometimes items in the second set are also checked.

How Execution Grows With Input

As the sets get bigger, the number of checks grows roughly in a straight line with the total number of items.

Input Size (n)	Approx. Operations
10	About 20 checks
100	About 200 checks
1000	About 2000 checks

Pattern observation: Doubling the size of the sets roughly doubles the work done.

Final Time Complexity

Time Complexity: O(n + m)

This means the time grows linearly with the total number of items in both sets.

Common Mistake

[X] Wrong: "Set operations always take the same time no matter how big the sets are."

[OK] Correct: Actually, the time depends on how many items are in the sets because each item needs to be checked.

Interview Connect

Understanding how set operations scale helps you explain your code clearly and shows you know how to handle data efficiently.

Self-Check

"What if we used lists instead of sets for these operations? How would the time complexity change?"

Practice

1.

Which set operation in C# returns all unique elements from two collections combined?

easy

A. Union

B. Intersect

C. Except

D. Concat

Solution

1. Step 1: Understand the meaning of Union

   Union combines all unique elements from both collections without duplicates.

2. Step 2: Compare with other operations

   Intersect returns only common elements, Except returns elements only in the first collection, and Concat just joins collections without removing duplicates.

3. Final Answer:

   Union -> Option A

4. Quick Check:

   Union = all unique elements combined [OK]

Hint: Union = combine all unique items from both sets [OK]

Common Mistakes:

• Confusing Union with Intersect
• Thinking Concat removes duplicates
• Mixing Except with Union

2.

Which of the following is the correct syntax to get the intersection of two sets setA and setB in C#?

var result = ???;

easy

A. setA.Join(setB)

B. setA.Intersect(setB)

C. setA.Except(setB)

D. setA.Union(setB)

Solution

1. Step 1: Identify method for intersection

   The Intersect method returns elements common to both collections.

2. Step 2: Verify syntax correctness

   setA.Intersect(setB) is the correct syntax; Union and Except do different operations, and Join is unrelated.

3. Final Answer:

   setA.Intersect(setB) -> Option B

4. Quick Check:

   Intersect = common elements [OK]

Hint: Use Intersect() to find common elements between sets [OK]

Common Mistakes:

• Using Union instead of Intersect
• Trying to use Join for sets
• Incorrect method call syntax

3.

What is the output of the following C# code?

var setA = new HashSet<int>() {1, 2, 3, 4};
var setB = new HashSet<int>() {3, 4, 5, 6};
var result = setA.Except(setB);
Console.WriteLine(string.Join(",", result));

medium

A. 1,2,5,6

B. 3,4

C. 5,6

D. 1,2

Solution

1. Step 1: Understand Except operation

   Except returns elements in the first set that are not in the second set.

2. Step 2: Apply Except to given sets

   setA has 1,2,3,4; setB has 3,4,5,6; elements in setA but not in setB are 1 and 2.

3. Final Answer:

   1,2 -> Option D

4. Quick Check:

   Except = elements only in first set [OK]

Hint: Except returns items only in first set, not in second [OK]

Common Mistakes:

• Confusing Except with Intersect
• Including elements from second set
• Expecting all unique elements combined

4.

Find the error in this C# code snippet that tries to get the union of two sets set1 and set2:

var set1 = new HashSet<string>() {"apple", "banana"};
var set2 = new HashSet<string>() {"banana", "cherry"};
var result = set1.Union(set2).ToList();
Console.WriteLine(result);

medium

A. Union method does not exist for HashSet

B. ToList() should be called before Union

C. Console.WriteLine cannot print a List directly

D. HashSet cannot contain strings

Solution

1. Step 1: Check method usage

   Union exists and works on HashSet; ToList() is valid after Union.

2. Step 2: Identify Console.WriteLine issue

   Console.WriteLine cannot print a List directly; it prints the type name instead.

3. Final Answer:

   Console.WriteLine cannot print a List directly -> Option C

4. Quick Check:

   Printing List needs string.Join or loop [OK]

Hint: Use string.Join to print collections, not Console.WriteLine directly [OK]

Common Mistakes:

• Assuming Union is invalid for HashSet
• Calling ToList before Union
• Thinking HashSet can't hold strings

5.

You have two lists of integers representing IDs: list1 = {1, 2, 3, 4, 5} and list2 = {4, 5, 6, 7}. You want to find IDs that are either in list1 or list2 but not in both (exclusive or). Which C# code snippet correctly achieves this using set operations?

hard

A. var result = list1.Except(list2).Union(list2.Except(list1));

B. var result = list1.Intersect(list2).Except(list1.Union(list2));

C. var result = list1.Union(list2).Except(list1.Except(list2));

D. var result = list1.Except(list2).Intersect(list2.Except(list1));

Solution

1. Step 1: Understand exclusive or (XOR) logic

   XOR means elements in one set or the other but not both.

2. Step 2: Analyze each option

   var result = list1.Union(list2).Except(list1.Except(list2)); subtracts elements unique to list1 from the union, leaving common and list2-unique elements - incorrect. var result = list1.Except(list2).Union(list2.Except(list1)); combines elements unique to each list using Except and Union, which directly matches XOR.

3. Final Answer:

   var result = list1.Except(list2).Union(list2.Except(list1)); -> Option A

4. Quick Check:

   XOR = unique elements from each set combined [OK]

Hint: XOR = (A except B) union (B except A) [OK]

Common Mistakes:

• Using Intersect instead of Except for uniqueness
• Confusing union and intersection order
• Trying to intersect except results