GroupBy for categorization in Kotlin - Time & Space Complexity

Time Complexity: GroupBy for categorization

O(n)

Understanding Time Complexity

When we use groupBy in Kotlin, we want to see how the time it takes changes as the list gets bigger.

We ask: How does grouping items by a key grow with more items?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

val items = listOf("apple", "banana", "apricot", "blueberry")
val grouped = items.groupBy { it.first() }
println(grouped)
    

This code groups a list of words by their first letter.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each item in the list once.
• How many times: Exactly once for each item (n times).

How Execution Grows With Input

As the list gets bigger, the time to group grows directly with the number of items.

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

Pattern observation: The work grows evenly as the list grows.

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

[X] Wrong: "Grouping takes longer than just looking at each item once because it creates many groups."

[OK] Correct: Grouping just looks at each item once and adds it to a group, so it doesn't multiply the work by the number of groups.

Interview Connect

Understanding how grouping scales helps you explain how data categorization works efficiently in real apps.

Self-Check

"What if the grouping key function itself took longer to compute for each item? How would the time complexity change?"

Practice

1. What does the groupBy function do in Kotlin?

easy

A. It sorts a list in ascending order.

B. It organizes a list into a map based on a key selector function.

C. It removes duplicate elements from a list.

D. It converts a list into a set.

Solution

1. Step 1: Understand the purpose of groupBy

   The groupBy function takes a list and groups its elements by a key, returning a map.

2. Step 2: Compare with other functions

   Sorting, removing duplicates, and converting to set do different things than grouping by a key.

3. Final Answer:

   It organizes a list into a map based on a key selector function. -> Option B

4. Quick Check:

   groupBy = organize by key [OK]

Hint: Remember: groupBy creates categories as map keys [OK]

Common Mistakes:

• Confusing groupBy with sorting functions
• Thinking groupBy removes duplicates
• Mixing groupBy with set conversion

2. Which of the following is the correct syntax to group a list of strings by their first character in Kotlin?

easy

A. val result = list.groupBy { it.first() }

B. val result = list.groupBy(it -> it.first())

C. val result = list.groupBy { it.first }

D. val result = list.groupBy { first(it) }

Solution

1. Step 1: Review Kotlin lambda syntax

   Kotlin uses curly braces with it for single-parameter lambdas: { it.first() }.

2. Step 2: Check each option

   val result = list.groupBy { it.first() } uses correct Kotlin syntax. val result = list.groupBy(it -> it.first()) uses arrow syntax which is invalid here. val result = list.groupBy { it.first } omits parentheses on first() method call, causing compile error. val result = list.groupBy { first(it) } calls undefined function first().

3. Final Answer:

   val result = list.groupBy { it.first() } -> Option A

4. Quick Check:

   Use curly braces and it.first() [OK]

Hint: Use curly braces and 'it' for lambda in groupBy [OK]

Common Mistakes:

• Using arrow syntax inside groupBy lambda
• Calling undefined functions like first(it)
• Omitting parentheses on first() method call

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

val numbers = listOf(1, 2, 3, 4, 5, 6)
val grouped = numbers.groupBy { if (it % 2 == 0) "even" else "odd" }
println(grouped)

medium

A. {odd=[1, 3, 5], even=[2, 4, 6]}

B. {1=[1], 2=[2], 3=[3], 4=[4], 5=[5], 6=[6]}

C. {true=[2, 4, 6], false=[1, 3, 5]}

D. SyntaxError

Solution

1. Step 1: Understand the grouping condition

   The lambda groups numbers by "even" if divisible by 2, else "odd".

2. Step 2: Group numbers accordingly

   Numbers 2,4,6 go to "even"; 1,3,5 go to "odd".

3. Final Answer:

   {odd=[1, 3, 5], even=[2, 4, 6]} -> Option A

4. Quick Check:

   Group by even/odd labels [OK]

Hint: Check grouping keys carefully for expected output [OK]

Common Mistakes:

• Confusing keys with values in output
• Expecting boolean keys instead of strings
• Thinking groupBy sorts the list

4. Identify the error in this Kotlin code snippet:

val words = listOf("apple", "banana", "apricot")
val grouped = words.groupBy { it[0] }
println(grouped)

medium

A. Indexing with it[0] is invalid for strings

B. Must convert characters to strings before grouping

C. groupBy requires a function, not a lambda

D. No error; code runs and groups by first character

Solution

1. Step 1: Check indexing on strings

   In Kotlin, strings support indexing with [0] to get first character.

2. Step 2: Validate groupBy usage

   The lambda { it[0] } is valid and groups words by their first character.

3. Final Answer:

   No error; code runs and groups by first character -> Option D

4. Quick Check:

   Strings support indexing; groupBy accepts lambdas [OK]

Hint: Remember strings can be indexed like arrays in Kotlin [OK]

Common Mistakes:

• Thinking indexing strings causes error
• Believing groupBy needs named functions only
• Assuming characters must be converted to strings

5. Given a list of people represented as pairs Pair<String, Int> where the first element is the name and the second is the age, how would you group them by age category "minor" (age < 18) or "adult" (age >= 18) using groupBy?

hard

A. people.groupBy { it.first }

B. people.groupBy { it.first.length }

C. people.groupBy { if (it.second < 18) "minor" else "adult" }

D. people.groupBy { it.second }

Solution

1. Step 1: Identify grouping key based on age

   We want to group by "minor" if age < 18, else "adult".

2. Step 2: Use groupBy with conditional key

   Access age with it.second and apply if-else to return category string.

3. Final Answer:

   people.groupBy { if (it.second < 18) "minor" else "adult" } -> Option C

4. Quick Check:

   Group by age category using conditional [OK]

Hint: Use if-else inside groupBy lambda for categories [OK]

Common Mistakes:

• Grouping by name or name length instead of age
• Grouping by exact age instead of categories
• Confusing first and second in Pair