Partition for splitting in Kotlin - Time & Space Complexity

Time Complexity: Partition for splitting

O(n)

Understanding Time Complexity

When we split a list into two parts based on a condition, we want to know how long it takes as the list grows.

How does the work increase when the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

val numbers = listOf(1, 2, 3, 4, 5, 6)
val (even, odd) = numbers.partition { it % 2 == 0 }
println("Even numbers: $even")
println("Odd numbers: $odd")
    

This code splits a list of numbers into two lists: one with even numbers and one with odd numbers.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking each number once to see if it is even or odd.
• How many times: Exactly once for every item in the list.

How Execution Grows With Input

As the list gets bigger, the program checks each number one time.

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

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

Final Time Complexity

Time Complexity: O(n)

This means the time to split the list grows in a straight line with the number of items.

Common Mistake

[X] Wrong: "Partitioning takes more time because it creates two lists and does extra work."

[OK] Correct: The main work is just checking each item once; creating two lists is done while checking, so it does not add extra loops.

Interview Connect

Understanding how partition works helps you explain how simple loops handle splitting data efficiently in real programs.

Self-Check

"What if we changed the condition to check each item twice inside the partition? How would the time complexity change?"

Practice

1. What does the partition function do in Kotlin when applied to a list?

easy

A. Converts the list into a map with indices as keys.

B. Sorts the list in ascending order.

C. Removes duplicate elements from the list.

D. Splits the list into two lists based on a condition, returning a Pair of lists.

Solution

1. Step 1: Understand the purpose of partition

   The partition function divides a list into two parts based on a condition.

2. Step 2: Recognize the return type

   It returns a Pair where the first list contains elements matching the condition, and the second list contains the rest.

3. Final Answer:

   Splits the list into two lists based on a condition, returning a Pair of lists. -> Option D

4. Quick Check:

   partition = split by condition [OK]

Hint: Remember: partition always returns two lists in a Pair [OK]

Common Mistakes:

• Thinking partition sorts the list
• Confusing partition with filtering
• Assuming partition removes duplicates

2. Which of the following is the correct syntax to use partition on a list numbers to split even and odd numbers?

easy

A. val (evens, odds) = numbers.partition { it % 2 == 0 }

B. val (evens, odds) = numbers.partition(it % 2 == 0)

C. val evens = numbers.partition { it % 2 == 0 }

D. val evens, odds = numbers.partition { it % 2 == 0 }

Solution

1. Step 1: Check the lambda syntax inside partition

   The condition must be inside curly braces with it representing each element.

2. Step 2: Verify destructuring declaration

   Partition returns a Pair, so use val (first, second) = ... to get both lists.

3. Final Answer:

   val (evens, odds) = numbers.partition { it % 2 == 0 } -> Option A

4. Quick Check:

   Correct lambda and destructuring = val (evens, odds) = numbers.partition { it % 2 == 0 } [OK]

Hint: Use val (a, b) = list.partition { condition } [OK]

Common Mistakes:

• Missing curly braces for lambda
• Not using destructuring for Pair
• Using parentheses instead of braces for lambda

3. What is the output of this Kotlin code?

val words = listOf("apple", "banana", "avocado", "berry")
val (aWords, otherWords) = words.partition { it.startsWith('a') }
println(aWords)
println(otherWords)

medium

A. ["apple", "avocado"]
["banana", "berry"]

B. ["banana", "berry"]
["apple", "avocado"]

C. ["apple"]
["banana", "avocado", "berry"]

D. ["avocado"]
["apple", "banana", "berry"]

Solution

1. Step 1: Apply the condition to each word

   Check which words start with 'a': "apple" and "avocado" match.

2. Step 2: Partition splits into two lists

   First list has words starting with 'a', second list has the rest: "banana", "berry".

3. Final Answer:

   ["apple", "avocado"] ["banana", "berry"] -> Option A

4. Quick Check:

   partition by startsWith('a') = ["apple", "avocado"] ["banana", "berry"] [OK]

Hint: Check condition on each element carefully [OK]

Common Mistakes:

• Mixing order of lists in output
• Forgetting that partition returns Pair of lists
• Confusing startsWith with contains

4. Identify the error in this Kotlin code using partition:

val nums = listOf(1, 2, 3, 4)
val evens, odds = nums.partition { it % 2 == 0 }
println(evens)
println(odds)

medium

A. partition cannot be used on lists of integers.

B. The lambda condition is incorrect; should be it % 2 != 0.

C. Missing parentheses around evens and odds for destructuring declaration.

D. println statements are missing string interpolation.

Solution

1. Step 1: Check destructuring declaration syntax

   Destructuring a Pair requires parentheses: val (evens, odds) = ....

2. Step 2: Confirm lambda and usage

   The lambda is correct for evens; partition works on lists of integers; println is fine.

3. Final Answer:

   Missing parentheses around evens and odds for destructuring declaration. -> Option C

4. Quick Check:

   Destructuring needs parentheses [OK]

Hint: Use val (a, b) = ... for destructuring Pair [OK]

Common Mistakes:

• Omitting parentheses in destructuring
• Changing correct lambda unnecessarily
• Thinking partition only works on strings

5. Given a list of mixed integers including zero and negatives, how can you use partition to separate positive numbers from zero and negatives? Choose the correct code snippet.

hard

A. val (positives, nonPositives) = numbers.partition { it < 0 }

B. val (positives, nonPositives) = numbers.partition { it > 0 }

C. val (positives, nonPositives) = numbers.partition { it >= 0 }

D. val (positives, nonPositives) = numbers.partition { it == 0 }

Solution

1. Step 1: Define the condition for positives

   Positive numbers are greater than zero, so condition is it > 0.

2. Step 2: Use partition with this condition

   Partition splits list into positives and the rest (zero and negatives).

3. Final Answer:

   val (positives, nonPositives) = numbers.partition { it > 0 } -> Option B

4. Quick Check:

   Partition by it > 0 separates positives [OK]

Hint: Use it > 0 to get positives, rest are zero/negatives [OK]

Common Mistakes:

• Using it >= 0 includes zero as positive
• Using it < 0 reverses groups
• Using it == 0 only selects zeros