Zip for combining collections in Kotlin - Time & Space Complexity

Time Complexity: Zip for combining collections

O(n)

Understanding Time Complexity

When we combine two lists using zip, we want to know how the work grows as the lists get bigger.

How does the number of steps change when the input lists grow?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

val list1 = listOf(1, 2, 3, 4)
val list2 = listOf("a", "b", "c", "d")

val zipped = list1.zip(list2) { num, str -> "$num$str" }
println(zipped)
    

This code pairs each element from the first list with the corresponding element from the second list, creating a new list of combined strings.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Pairing elements from both lists one by one.
• How many times: Once for each element up to the length of the shorter list.

How Execution Grows With Input

Each element in the smaller list is combined with one element from the other list, so the work grows directly with the number of pairs.

Input Size (n)	Approx. Operations
10	10 pairs combined
100	100 pairs combined
1000	1000 pairs combined

Pattern observation: The number of operations grows in a straight line with the input size.

Final Time Complexity

Time Complexity: O(n)

This means the time to combine the lists grows directly in proportion to the number of elements being zipped.

Common Mistake

[X] Wrong: "Zipping two lists takes time proportional to the product of their sizes."

[OK] Correct: Zip only pairs elements one by one up to the smaller list size, so it does not multiply the sizes.

Interview Connect

Understanding how zip works helps you explain how combining data step-by-step scales, a useful skill for many coding tasks.

Self-Check

"What if we zipped three lists instead of two? How would the time complexity change?"

Practice

1. What does the zip function do when used with two lists in Kotlin?

easy

A. Combines all elements from both lists into one longer list.

B. Pairs elements from both lists into a list of pairs, stopping at the shorter list length.

C. Creates a map from the first list's elements to the second list's elements without pairing.

D. Filters elements that are common to both lists.

Solution

1. Step 1: Understand the zip function behavior

   The zip function pairs elements from two collections by their positions.

2. Step 2: Consider the length of the resulting list

   The resulting list length equals the smaller of the two input lists, pairing elements until one list runs out.

3. Final Answer:

   Pairs elements from both lists into a list of pairs, stopping at the shorter list length. -> Option B

4. Quick Check:

   Zip pairs elements up to shortest list length [OK]

Hint: Zip pairs elements by index, stops at shortest list length [OK]

Common Mistakes:

• Thinking zip concatenates lists instead of pairing
• Assuming zip returns a map automatically
• Believing zip pairs all elements ignoring list length

2. Which of the following is the correct syntax to zip two lists listA and listB in Kotlin?

easy

A. val zipped = listA + listB.zip()

B. val zipped = zip(listA, listB)

C. val zipped = listA.zip(listB)

D. val zipped = listA.zipWith(listB)

Solution

1. Step 1: Recall Kotlin's zip syntax

   The zip function is called as an extension on the first list, passing the second list as argument.

2. Step 2: Check each option

   val zipped = listA.zip(listB) matches the correct syntax: listA.zip(listB). Others are invalid or incorrect method calls.

3. Final Answer:

   val zipped = listA.zip(listB) -> Option C

4. Quick Check:

   Use listA.zip(listB) to zip two lists [OK]

Hint: Use listA.zip(listB) to combine two lists [OK]

Common Mistakes:

• Trying to call zip as a standalone function
• Using incorrect method names like zipWith
• Concatenating lists instead of zipping

3. What is the output of the following Kotlin code?

val nums = listOf(1, 2, 3)
val chars = listOf('a', 'b')
val zipped = nums.zip(chars)
println(zipped)

medium

A. [(1, a), (2, b), (3, null)]

B. [(a, 1), (b, 2)]

C. [(1, a), (2, b), (3, c)]

D. [(1, a), (2, b)]

Solution

1. Step 1: Identify the input lists and their lengths

   nums has 3 elements, chars has 2 elements.

2. Step 2: Understand zip output length and pairing

   Zip pairs elements by index until the shorter list ends, so only first 2 pairs: (1, 'a') and (2, 'b').

3. Final Answer:

   [(1, a), (2, b)] -> Option D

4. Quick Check:

   Zip length = shorter list length = 2 [OK]

Hint: Zip stops at shorter list length, pairs elements by index [OK]

Common Mistakes:

• Expecting zip to fill missing elements with null
• Assuming zip pairs all elements ignoring length
• Mixing order of elements in pairs

4. The following Kotlin code throws an error. What is the problem?

val list1 = listOf(1, 2, 3)
val list2 = listOf("a", "b", "c")
val zipped = list1.zip(list2) { a, b -> a + b }
println(zipped)

medium

A. Cannot add Int and String directly with + operator.

B. zip requires lists to be the same size.

C. The lambda syntax for zip is incorrect.

D. listOf cannot contain different types.

Solution

1. Step 1: Analyze the lambda inside zip

   The lambda tries to add a (Int) and b (String) using +.

2. Step 2: Understand Kotlin type rules

   Adding Int and String directly with + is not allowed; it causes a type error.

3. Final Answer:

   Cannot add Int and String directly with + operator. -> Option A

4. Quick Check:

   Int + String causes type error in Kotlin [OK]

Hint: Int + String needs explicit conversion or concatenation [OK]

Common Mistakes:

• Assuming zip needs equal list sizes
• Thinking lambda syntax is wrong
• Believing listOf can't hold different types

5. Given two lists val names = listOf("Anna", "Bob", "Cara") and val scores = listOf(90, 85), how can you create a list of strings like ["Anna: 90", "Bob: 85"] using zip with a lambda?

hard

A. names.zip(scores) { name, score -> "$name: $score" }

B. names.zip(scores).map { name, score -> "$name: $score" }

C. names.zipWith(scores) { name, score -> "$name: $score" }

D. names.zip(scores).toString { "$name: $score" }

Solution

1. Step 1: Use zip with a transform lambda

   The zip function can take a lambda to transform pairs directly into desired output.

2. Step 2: Format each pair as a string

   Using { name, score -> "$name: $score" } creates the string format needed.

3. Final Answer:

   names.zip(scores) { name, score -> "$name: $score" } -> Option A

4. Quick Check:

   Use zip with lambda to transform pairs [OK]

Hint: Use zip with lambda to format pairs directly [OK]

Common Mistakes:

• Using zipWith which doesn't exist in Kotlin
• Trying to call toString with a lambda
• Mapping after zip instead of using lambda inside zip