Time Complexity: Zip for combining collections
O(n)
0
0
Zip for combining collections in Kotlin - Time & Space Complexity
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?"