Null safety in collections in Kotlin - Time & Space Complexity

Time Complexity: Null safety in collections

O(n)

Understanding Time Complexity

When working with collections in Kotlin, null safety helps avoid errors by controlling which elements can be null.

We want to see how checking for nulls in collections affects the time it takes to run the code.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

fun countNonNull(items: List): Int {
    var count = 0
    for (item in items) {
        if (item != null) {
            count++
        }
    }
    return count
}

This code counts how many non-null strings are in a list that may contain null values.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each element in the list once.
• How many times: Exactly once for every item in the list.

How Execution Grows With Input

As the list gets bigger, the code checks each item one by one.

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

Pattern observation: The number of operations grows directly with the size of the list.

Final Time Complexity

Time Complexity: O(n)

This means the time to count non-null items grows in a straight line as the list gets bigger.

Common Mistake

[X] Wrong: "Checking for nulls inside the loop makes the code slower by a lot."

[OK] Correct: The null check is very quick and happens once per item, so it doesn't change the overall growth pattern.

Interview Connect

Understanding how null safety checks affect performance shows you can write safe and efficient Kotlin code, a skill valued in many coding tasks.

Self-Check

"What if we used a nested list of nullable strings instead of a single list? How would the time complexity change?"

Practice

1. What does Kotlin's null safety feature ensure when working with collections like List or Set?

easy

A. It prevents storing null values in collections declared without nullable types.

B. It automatically converts all null values to empty strings in collections.

C. It allows null values in any collection without restrictions.

D. It disables the use of collections if they contain null values.

Solution

1. Step 1: Understand Kotlin's null safety in collections

   Kotlin distinguishes between nullable and non-nullable types. Collections declared with non-nullable types cannot hold null values.

2. Step 2: Apply this to collection elements

   If a collection is declared as List<String>, it cannot contain null. To allow null, it must be declared as List<String?>.

3. Final Answer:

   It prevents storing null values in collections declared without nullable types. -> Option A

4. Quick Check:

   Null safety = no null in non-nullable collections [OK]

Hint: Non-nullable collections disallow null elements [OK]

Common Mistakes:

• Assuming all collections allow null by default
• Confusing null safety with automatic null replacement
• Thinking null safety disables collections with nulls

2. Which of the following is the correct way to declare a list that can hold nullable integers in Kotlin?

easy

A. val numbers: List<Int> = listOf(1, 2, null)

B. val numbers: List<Int> = listOf(null, null, null)

C. val numbers: List = listOf(1, 2, 3)

D. val numbers: List = listOf(1, 2, null)

Solution

1. Step 1: Identify nullable type declaration

   To allow null in a list, the element type must be nullable, written as Int?.

2. Step 2: Check list initialization

   listOf(1, 2, null) is valid only if the list type is List<Int?>. val numbers: List = listOf(1, 2, null) matches this.

3. Final Answer:

   val numbers: List<Int?> = listOf(1, 2, null) -> Option D

4. Quick Check:

   Nullable type uses Int? for null elements [OK]

Hint: Use Type? to allow nulls in collections [OK]

Common Mistakes:

• Declaring list as List<Int> but adding nulls
• Using List<Int> with null elements causes error
• Confusing nullable element type with nullable list

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

val list: List = listOf("apple", null, "banana")
val filtered = list.filterNotNull()
println(filtered)

medium

A. ["apple", null, "banana"]

B. [null]

C. ["apple", "banana"]

D. Compilation error

Solution

1. Step 1: Understand filterNotNull() behavior

   This function removes all null elements from a collection, returning a list of non-null elements.

2. Step 2: Apply filterNotNull() on the list

   Original list has "apple", null, "banana". After filtering, only "apple" and "banana" remain.

3. Final Answer:

   ["apple", "banana"] -> Option C

4. Quick Check:

   filterNotNull() removes nulls [OK]

Hint: filterNotNull() removes all nulls from collections [OK]

Common Mistakes:

• Expecting nulls to remain after filterNotNull()
• Thinking filterNotNull() causes compile error
• Confusing filterNotNull() with filter()

4. Identify the error in this Kotlin code snippet:

val list: List<Int> = listOf(1, 2, null, 4)

medium

A. The list declaration syntax is incorrect.

B. The list cannot contain null because Int is non-nullable.

C. The listOf function cannot be used with integers.

D. There is no error; the code compiles fine.

Solution

1. Step 1: Check element type and values

   The list is declared as List<Int>, which means elements cannot be null.

2. Step 2: Identify the presence of null

   The list contains a null value, which is not allowed for non-nullable types, causing a compilation error.

3. Final Answer:

   The list cannot contain null because Int is non-nullable. -> Option B

4. Quick Check:

   Non-nullable list disallows null elements [OK]

Hint: Non-nullable types disallow null values in collections [OK]

Common Mistakes:

• Assuming null is allowed in List<Int>
• Thinking listOf syntax is wrong
• Ignoring Kotlin's null safety rules

5. Given a list of nullable strings val items: List = listOf("a", null, "b", null, "c"), how can you create a map where keys are the strings and values are their lengths, excluding null values safely?

hard

A. items.filterNotNull().associateWith { it.length }

B. items.associateWith { it!!.length }

C. items.associate { it to it.length }

D. items.map { it.length }.toMap()

Solution

1. Step 1: Remove null values safely

   Use filterNotNull() to exclude null elements before mapping.

2. Step 2: Create map with strings as keys and lengths as values

   Use associateWith { it.length } on the filtered list to map each string to its length.

3. Final Answer:

   items.filterNotNull().associateWith { it.length } -> Option A

4. Quick Check:

   Filter nulls first, then associate [OK]

Hint: Filter nulls before mapping to avoid errors [OK]

Common Mistakes:

• Using !! operator risking NullPointerException
• Trying to associate null keys or values
• Mapping lengths without filtering nulls first