HashSet for unique elements in C Sharp (C#) - Time & Space Complexity

Time Complexity: HashSet for unique elements

O(n)

Understanding Time Complexity

We want to understand how fast a HashSet can add and check unique items.

How does the time to add or check items grow as we add more elements?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

HashSet<int> uniqueNumbers = new HashSet<int>();
int[] numbers = {1, 2, 3, 2, 4, 5, 3};

foreach (int num in numbers)
{
    uniqueNumbers.Add(num);
}
    

This code adds numbers to a HashSet to keep only unique values.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Adding each number to the HashSet.
• How many times: Once for each number in the input array.

How Execution Grows With Input

Each new number is checked and added quickly, so the time grows roughly in a straight line with the number of items.

Input Size (n)	Approx. Operations
10	About 10 add/check operations
100	About 100 add/check operations
1000	About 1000 add/check operations

Pattern observation: The work grows evenly as the input grows.

Final Time Complexity

Time Complexity: O(n)

This means the time to add all items grows directly with the number of items.

Common Mistake

[X] Wrong: "Adding to a HashSet takes longer and longer as it gets bigger."

[OK] Correct: HashSet uses a smart way to find spots quickly, so adding stays fast even with many items.

Interview Connect

Knowing how HashSet works helps you explain why it's great for finding unique items quickly in real projects.

Self-Check

"What if we used a List instead of a HashSet to keep unique items? How would the time complexity change?"

Practice

1. What is the main purpose of using a HashSet<T> in C#?

easy

A. To allow duplicate elements for faster access

B. To store elements in sorted order

C. To store unique elements without duplicates

D. To store key-value pairs like a dictionary

Solution

1. Step 1: Understand HashSet behavior

   A HashSet automatically ignores duplicate entries and stores only unique elements.

2. Step 2: Compare with other collections

   Unlike lists or dictionaries, HashSet does not allow duplicates and does not maintain order.

3. Final Answer:

   To store unique elements without duplicates -> Option C

4. Quick Check:

   HashSet = Unique elements [OK]

Hint: HashSet always keeps unique items only [OK]

Common Mistakes:

• Thinking HashSet keeps elements sorted
• Assuming HashSet allows duplicates
• Confusing HashSet with Dictionary

2. Which of the following is the correct way to declare and initialize a HashSet<int> with values 1, 2, and 3?

easy

A. var set = HashSet<int> = {1, 2, 3};

B. var set = new HashSet<int> {1, 2, 3};

C. var set = new HashSet<int>[1, 2, 3];

D. var set = new HashSet<int>(1, 2, 3);

Solution

1. Step 1: Check HashSet initialization syntax

   HashSet can be initialized with collection initializer syntax using curly braces after the constructor.

2. Step 2: Validate each option

   var set = new HashSet<int> {1, 2, 3}; uses correct syntax: new HashSet<int> {1, 2, 3}; Options A, B, and C have invalid syntax.

3. Final Answer:

   var set = new HashSet<int> {1, 2, 3}; -> Option B

4. Quick Check:

   Use curly braces after constructor for initialization [OK]

Hint: Use curly braces after new HashSet for values [OK]

Common Mistakes:

• Using parentheses with multiple values directly
• Trying to declare array instead of HashSet
• Incorrect assignment syntax

3. What will be the output of the following C# code?

var set = new HashSet<string>();
set.Add("apple");
set.Add("banana");
set.Add("apple");
Console.WriteLine(set.Count);

medium

A. 0

B. 3

C. 1

D. 2

Solution

1. Step 1: Add elements to HashSet

   "apple" is added first, then "banana", then "apple" again.

2. Step 2: Understand duplicate handling

   The second "apple" is ignored because HashSet stores unique elements only.

3. Final Answer:

   2 -> Option D

4. Quick Check:

   Duplicates ignored, count = 2 [OK]

Hint: Count equals unique items added, duplicates ignored [OK]

Common Mistakes:

• Counting duplicates as separate elements
• Assuming HashSet allows duplicates
• Confusing Count with number of Add calls

4. Identify the error in this code snippet using HashSet<int>:

HashSet<int> numbers = new HashSet<int>();
numbers.Add(1);
numbers.Add(2);
numbers.Add(1);
Console.WriteLine(numbers[0]);

medium

A. HashSet does not support indexing with []

B. Cannot add duplicate values to HashSet

C. HashSet must be initialized with values

D. Add method returns void, cannot be used like this

Solution

1. Step 1: Review HashSet usage

   HashSet stores unique elements but does not support accessing elements by index.

2. Step 2: Identify invalid operation

   Using numbers[0] causes a compile-time error because HashSet has no indexer.

3. Final Answer:

   HashSet does not support indexing with [] -> Option A

4. Quick Check:

   No index access on HashSet [OK]

Hint: HashSet has no indexer; use foreach or Contains [OK]

Common Mistakes:

• Trying to access elements by index
• Thinking Add returns a value
• Assuming duplicates cause errors

5. You have a list of integers with duplicates: List<int> nums = new List<int> {1, 2, 2, 3, 4, 4, 4, 5};
Which code snippet correctly creates a HashSet<int> containing only the unique elements from nums?

hard

A. var unique = new HashSet<int>(nums);

B. var unique = new HashSet<int>(); unique.Add(nums);

C. var unique = new HashSet<int>(); foreach(var n in nums) unique = n;

D. var unique = new HashSet<int>(); unique.AddRange(nums);

Solution

1. Step 1: Understand HashSet constructor

   HashSet has a constructor that accepts an IEnumerable<T> to initialize with unique elements.

2. Step 2: Analyze each option

   var unique = new HashSet<int>(nums); correctly passes the list to the constructor. var unique = new HashSet<int>(); unique.Add(nums); tries to add the whole list as one item (invalid). var unique = new HashSet<int>(); foreach(var n in nums) unique = n; assigns int to HashSet variable (invalid). var unique = new HashSet<int>(); unique.AddRange(nums); uses AddRange which HashSet does not have.

3. Final Answer:

   var unique = new HashSet<int>(nums); -> Option A

4. Quick Check:

   Use constructor with collection for unique set [OK]

Hint: Pass list to HashSet constructor for unique items [OK]

Common Mistakes:

• Using Add to add whole list at once
• Trying to assign int to HashSet variable
• Using AddRange which HashSet lacks