Set creation (setOf, mutableSetOf) in Kotlin - Time & Space Complexity

Time Complexity: Set creation (setOf, mutableSetOf)

O(n)

Understanding Time Complexity

When we create sets in Kotlin, it's important to know how the time to build them grows as we add more items.

We want to understand how the work changes when the number of elements increases.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

val numbers = listOf(1, 2, 3, 4, 5)
val set1 = setOf(1, 2, 3, 4, 5)
val mutableSet = mutableSetOf()
for (num in numbers) {
    mutableSet.add(num)
}
    

This code creates a read-only set directly and a mutable set by adding elements one by one.

Identify Repeating Operations

• Primary operation: Adding each element to the mutable set inside the loop.
• How many times: Once for each element in the input list.

How Execution Grows With Input

As the number of elements increases, the number of add operations grows directly with it.

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

Pattern observation: The work grows in a straight line with the number of elements.

Final Time Complexity

Time Complexity: O(n)

This means the time to create the set grows directly in proportion to the number of items you add.

Common Mistake

[X] Wrong: "Adding elements to a set takes the same time no matter how many items there are."

[OK] Correct: Each element must be processed once, so more items mean more work, even if each add is fast.

Interview Connect

Understanding how set creation scales helps you explain efficiency when working with collections in real projects.

Self-Check

"What if we used a nested loop to add elements from two lists into a set? How would the time complexity change?"

Practice

1. What does the Kotlin function setOf(1, 2, 2, 3) return?

easy

A. A list containing elements: 1, 2, 2, 3

B. A set containing duplicates: 1, 2, 2, 3

C. A set containing unique elements: 1, 2, 3

D. An error because of duplicate elements

Solution

1. Step 1: Understand setOf behavior

   setOf creates a set that holds only unique elements, automatically removing duplicates.

2. Step 2: Analyze the input elements

   The input has elements 1, 2, 2, 3. The duplicate 2 is ignored in the set.

3. Final Answer:

   A set containing unique elements: 1, 2, 3 -> Option C

4. Quick Check:

   setOf removes duplicates = unique elements [OK]

Hint: Remember: sets keep only unique items [OK]

Common Mistakes:

• Thinking sets keep duplicates like lists
• Confusing setOf with listOf
• Expecting an error for duplicates

2. Which of the following is the correct way to create a mutable set of strings in Kotlin?

easy

A. val mySet = mutableSetOf<String>("apple", "banana")

B. val mySet = setOf<String>("apple", "banana")

C. val mySet = mutableSet("apple", "banana")

D. val mySet = mutableSetOf("apple", "banana")

Solution

1. Step 1: Identify correct syntax for mutableSetOf

   The correct function is mutableSetOf with type parameter and parentheses.

2. Step 2: Check each option

   val mySet = mutableSetOf<String>("apple", "banana") uses mutableSetOf<String>("apple", "banana"), which is correct. val mySet = setOf<String>("apple", "banana") uses setOf which creates an immutable set. val mySet = mutableSet("apple", "banana") uses a non-existent function mutableSet. val mySet = mutableSetOf("apple", "banana") has a syntax error with an extra quote.

3. Final Answer:

   val mySet = mutableSetOf<String>("apple", "banana") -> Option A

4. Quick Check:

   mutableSetOf syntax correct = val mySet = mutableSetOf<String>("apple", "banana") [OK]

Hint: Use mutableSetOf() to create changeable sets [OK]

Common Mistakes:

• Using setOf instead of mutableSetOf for mutable sets
• Misspelling mutableSetOf
• Syntax errors with quotes or parentheses

3. What will be the output of this Kotlin code?

val numbers = mutableSetOf(1, 2, 3)
numbers.add(2)
numbers.add(4)
println(numbers)

medium

A. Compilation error

B. [1, 2, 3, 2, 4]

C. [1, 2, 3]

D. [1, 2, 3, 4]

Solution

1. Step 1: Understand mutableSetOf and add behavior

   The set starts with 1, 2, 3. Adding 2 again does nothing because sets ignore duplicates. Adding 4 adds a new element.

2. Step 2: Determine final set contents

   After additions, the set contains 1, 2, 3, and 4.

3. Final Answer:

   [1, 2, 3, 4] -> Option D

4. Quick Check:

   Sets ignore duplicates, so 2 is not added twice [OK]

Hint: Adding duplicates to sets does nothing [OK]

Common Mistakes:

• Expecting duplicates to appear in output
• Confusing set print format with list
• Thinking add returns error on duplicates

4. Identify the error in this Kotlin code snippet:

val fruits = setOf("apple", "banana")
fruits.add("orange")
println(fruits)

medium

A. Syntax error in setOf declaration

B. Cannot add elements to an immutable set

C. Missing import for setOf

D. No error, code runs fine

Solution

1. Step 1: Check mutability of setOf

   setOf creates an immutable set that cannot be changed after creation.

2. Step 2: Analyze the add operation

   Calling add on an immutable set causes a compilation error because the set cannot be modified.

3. Final Answer:

   Cannot add elements to an immutable set -> Option B

4. Quick Check:

   setOf = immutable, add() not allowed [OK]

Hint: Use mutableSetOf to add or remove items [OK]

Common Mistakes:

• Trying to modify immutable sets
• Confusing setOf with mutableSetOf
• Ignoring compiler error messages

5. You want to create a mutable set of integers from a list but only include numbers greater than 5. Which Kotlin code correctly does this?

hard

A. val nums = mutableSetOf(1, 6, 8, 3, 7).filterTo(mutableSetOf()) { it > 5 }

B. val nums = setOf(1, 6, 8, 3, 7).filter { it > 5 }.toSet()

C. val nums = mutableSetOf(1, 6, 8, 3, 7).filter { it > 5 }

D. val nums = mutableSetOf(1, 6, 8, 3, 7).filter { it > 5 }.toSet()

Solution

1. Step 1: Understand filtering and set creation

   We want a mutable set with only numbers > 5. Using filterTo with a mutable set collects filtered items directly into a mutable set.

2. Step 2: Evaluate each option

   val nums = mutableSetOf(1, 6, 8, 3, 7).filter { it > 5 } returns a List, not a mutable set. val nums = mutableSetOf(1, 6, 8, 3, 7).filterTo(mutableSetOf()) { it > 5 } correctly filters into a mutable set. val nums = setOf(1, 6, 8, 3, 7).filter { it > 5 }.toSet() creates an immutable set first, then filters to list and toSet(), producing an immutable set, not mutable. val nums = mutableSetOf(1, 6, 8, 3, 7).filter { it > 5 }.toSet() filters to a list then toSet(), producing an immutable set, not mutable.

3. Final Answer:

   val nums = mutableSetOf(1, 6, 8, 3, 7).filterTo(mutableSetOf()) { it > 5 } -> Option A

4. Quick Check:

   filterTo with mutableSetOf creates mutable set directly [OK]

Hint: Use filterTo(mutableSetOf()) for filtered mutable sets [OK]

Common Mistakes:

• Using filter() returns list, not set
• Not converting to mutable set after filtering
• Confusing setOf and mutableSetOf usage