2631. Group By


Problem Description

The given problem requires us to augment the prototype of the built-in Array object in JavaScript with a new method called groupBy. This groupBy method should be callable on any array instance. When activated, it takes a callback function fn as a parameter. This function is applied to each element of the array, and the return value of the callback function is used as a key to group the elements.

The result of the groupBy method is an object where each property key corresponds to the output of the callback function fn, and the associated property value is an array of all elements from the original array which, when fn was called on them, returned that key.

To reiterate, the requirements specify:

  • The fn function takes an array item as an argument and returns a string that is used as a key.
  • The object produced contains keys for every unique string returned by fn.
  • The values of the object are arrays of items for which the fn returned the corresponding key.
  • The items within each group (array) should remain in the same order they appeared in the original array.
  • The order of the keys in the grouped object does not matter.
  • Use of external libraries like lodash for the groupBy functionality is not allowed.

Intuition

The intuition behind the solution is to process each item in the array sequentially, apply the fn function to get a key, and then organize the items into groups based on that key.

Here's a step-by-step approach to arrive at the solution:

  1. Extending the Array Prototype: Since we need to enhance all arrays with the new groupBy method, we extend the Array prototype. This ensures that all array instances inherit this new method.

  2. Iterating Using reduce Method: We use the reduce method because it traverses the array, and for each element, it applies a reducer function. The reducer function lets us accumulate a single result - in this case, the grouped object - from the individual elements of the array.

  3. Applying the Callback Function: Within the reducer function, we invoke the provided callback fn on the current item to get the key. This helps determine the group to which the current item belongs.

  4. Building the Grouped Object: We check if the grouped object already has a property with the key. If it does, we push the current item to the corresponding array. If not, we initialize a new array with the current item in it. This step essentially constructs the output object with keys as the unique strings returned by fn and values as arrays of grouped items.

  5. Returning the Accumulated Grouped Object: After the reduction is complete, we return the accumulated object, which represents the grouped structure.

  6. Maintaining Order Within Groups: Since reduce traverses the array from left to right and we are appending items to groups as we encounter them, the order of items within each group is the same as in the original array.

The provided code demonstrates a neat implementation of this approach without using any external library, complying with the problem's requirements.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

Solution Approach

The solution provided involves extending the Array prototype and adding a new method groupBy. Here's a walkthrough of the solution's implementation details:

  • Extending Array Prototype: This is done to add a new method groupBy that becomes available to all instances of arrays. It's a common pattern in JavaScript known as monkey patching, which should be used with caution as it could lead to clashes if the JavaScript environment introduces a method with the same name in the future or if used with third-party libraries.
1declare global {
2    interface Array<T> {
3        groupBy(fn: (item: T) => string): Record<string, T[]>;
4    }
5}

Above, an interface declaration in TypeScript augments the global Array interface to include the groupBy method, ensuring that TypeScript is aware of the new method signature.

  • groupBy Method: The groupBy method is defined as a function on Array.prototype. This function uses the reduce method internally to iterate over the array elements and group them based on the callback function.
1Array.prototype.groupBy = function (fn) {
2    return this.reduce((acc, item) => {
3        // ...
4    }, {});
5};
  • The reduce Function: The reduce method takes two parameters: a reducer function and an initial value for the accumulator. Here, the initial value of the accumulator (acc) is an empty object {} because the desired output is an object with keys based on the return values of fn.
1    return this.reduce((acc, item) => {
2        //...
3    }, {});
  • Accumulating Groups: Inside the reduce method, for each item in the array, we first determine the group key by applying the callback function fn(item). Then, we check if the key already exists in the accumulator object. If it does, we push the current item onto the existing array. Otherwise, we create a new array with the current item.
1const key = fn(item);
2if (acc[key]) {
3    acc[key].push(item);
4} else {
5    acc[key] = [item];
6}
  • Final Output: Once all items have been processed, the reduce method returns the accumulator object acc, which now contains the grouped contents.

In terms of algorithms and patterns, the solution heavily relies on:

  • Functional Programming Patterns: Leveraging functions like reduce to build new data structures in an immutable fashion.
  • Duck Typing: Assuming the function fn will act in a predictable manner, as per the specifications (returning a string when invoked with an array element).
  • Higher-Order Functions: Using a function (fn) passed as an argument to another function (groupBy), to create a more specific and customized behavior.

And finally, to test the implemented method, the sample usage could be:

1/**
2 * [1,2,3].groupBy(String) // {"1":[1],"2":[2],"3":[3]}
3 */

In this example, each number in the array [1, 2, 3] is converted to a string by the String constructor function, which is passed as fn, and the resulting keys are strings of the numbers with arrays that contain the original numbers grouped accordingly.

1Array.prototype.groupBy = function (fn) {
2    return this.reduce((acc, item) => {
3        const key = fn(item);
4        if (acc[key]) {
5            acc[key].push(item);
6        } else {
7            acc[key] = [item];
8        }
9        return acc;
10    }, {});
11};

In summary, this code snippet aptly demonstrates how to inherently sort and group elements of an array into an object by a defined characteristic without relying on any external libraries.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Depth first search is equivalent to which of the tree traversal order?

Example Walkthrough

Let’s walk through a small example to illustrate the solution approach using the groupBy method:

Assume we have an array of objects representing different fruits with properties type and color:

1const fruits = [
2  { type: 'apple', color: 'green' },
3  { type: 'banana', color: 'yellow' },
4  { type: 'grape', color: 'green' },
5  { type: 'apple', color: 'red' },
6  { type: 'lemon', color: 'yellow' },
7];

We want to group these fruits by their color. To do that, we will use the new groupBy method we’ve added to the Array prototype. We’ll pass in a callback function that takes a fruit and returns its color which will serve as the group key.

1const groupedByColor = fruits.groupBy(fruit => fruit.color);

Here's what happens step-by-step when calling groupBy with our example array:

  1. The groupBy method is invoked on fruits.

  2. The reduce method starts executing with an empty object {} as the initial accumulator.

  3. The reduce callback runs for the first fruit:

    • It extracts the key 'green' using the provided callback (fruit => fruit.color).
    • Since 'green' doesn't exist on the accumulator yet, it creates a new property with this key and sets its value to an array containing the current fruit item [ { type: 'apple', color: 'green' } ].
  4. The reduce callback runs for the second fruit:

    • It extracts the key 'yellow'.
    • A new property 'yellow' is added to the accumulator with the current fruit item in a new array.
  5. This process repeats for each fruit item, appending to the existing array if a key already exists or creating a new one if it doesn't.

After the reduce function has processed all fruits, the accumulator object looks like this:

1{
2  'green': [
3    { type: 'apple', color: 'green' },
4    { type: 'grape', color: 'green' }
5  ],
6  'yellow': [
7    { type: 'banana', color: 'yellow' },
8    { type: 'lemon', color: 'yellow' }
9  ],
10  'red': [
11    { type: 'apple', color: 'red' }
12  ]
13}

The output is an object with color keys, each key pointing to an array of fruits that have that color. The groupBy feature works as intended, allowing us to flexibly group array items based on the characteristics we define.

Solution Implementation

1# Extend the list class with a new method 'group_by'.
2class ExtendedList(list):
3    # The group_by method takes a key_selector function that
4    # determines the key by which to group list elements.
5    def group_by(self, key_selector):
6        # Use a dictionary to accumulate groups.
7        # The keys are determined by the key_selector function,
8        # and the values are lists of items.
9        grouped = {}
10        for item in self:
11            # Obtain the key by passing the current item to the key_selector function.
12            key = key_selector(item)
13            # If the key does not exist in the dictionary, create a new list for it.
14            # Then append the item to the list corresponding to the key.
15            if key not in grouped:
16                grouped[key] = []
17            grouped[key].append(item)
18        # Return the dictionary containing the grouped items.
19        return grouped
20
21# To use the ExtendedList class, it must be instantiated with a list of items.
22# Example usage:
23# This call should group numbers by their string representation.
24# ExtendedList([1, 2, 3]).group_by(str) # {"1": [1], "2": [2], "3": [3]}
25
1import java.util.ArrayList;
2import java.util.HashMap;
3import java.util.List;
4import java.util.Map;
5import java.util.function.Function;
6import java.util.stream.Collectors;
7
8public class ArrayUtils {
9
10    /**
11     * Groups elements of a list by a key generated from the elements themselves.
12     * 
13     * @param <T> The type of elements in the list
14     * @param <K> The type of the key used for grouping elements
15     * @param list The list to be grouped
16     * @param keySelector A function that generates keys from list elements
17     * @return A map where each key is associated with a list of elements
18     */
19    public static <T, K> Map<K, List<T>> groupBy(List<T> list, Function<T, K> keySelector) {
20        Map<K, List<T>> groupedMap = new HashMap<>();
21        for (T element : list) {
22            K key = keySelector.apply(element);
23            // Get the current list of elements for this key, or initialize it if it does not exist
24            if (!groupedMap.containsKey(key)) {
25                groupedMap.put(key, new ArrayList<>());
26            }
27            groupedMap.get(key).add(element);
28        }
29        return groupedMap;
30    }
31  
32    public static void main(String[] args) {
33        // Example usage:
34        // Should group numbers by their string representation.
35        List<Integer> numbers = List.of(1, 2, 3);
36        Map<String, List<Integer>> grouped = groupBy(numbers, String::valueOf);
37        System.out.println(grouped); // Outputs: {"1"=[1], "2"=[2], "3"=[3]}
38    }
39}
40
1#include <vector>
2#include <string>
3#include <unordered_map>
4#include <functional>
5
6// Define a template function 'groupBy' that can be used with any vector of type T.
7template<typename T>
8std::unordered_map<std::string, std::vector<T>> groupBy(const std::vector<T>& items, std::function<std::string(const T&)> keySelector) {
9    // The 'groupBy' function returns a map from strings to vectors of items.
10    std::unordered_map<std::string, std::vector<T>> grouped;
11
12    // Iterate through all items in the input vector 'items'.
13    for (const T& item : items) {
14        // Obtain the key for the current item using the provided 'keySelector' function.
15        std::string key = keySelector(item);
16
17        // Insert the item into the map under the appropriate key.
18        // The map will automatically create a new vector if this is the first item for this key.
19        grouped[key].push_back(item);
20    }
21
22    // Return the resulting map of grouped items.
23    return grouped;
24}
25
26// Example usage:
27// Create a lambda function that converts integers to their string representation.
28auto intToString = [](const int& item) -> std::string {
29    return std::to_string(item);
30};
31
32// Call 'groupBy' on a vector of integers using the lambda function to group by number as string.
33std::vector<int> numbers = {1, 2, 3};
34auto groupedNumbers = groupBy(numbers, intToString); 
35// groupedNumbers will be a map that contains {"1": [1], "2": [2], "3": [3]}
36
1// Extend the Array prototype with a new method 'groupBy'.
2declare global {
3  interface Array<T> {
4    // The groupBy method is generic and takes a callback function that 
5    // determines the key by which to group array elements.
6    groupBy(keySelector: (item: T) => string): Record<string, T[]>;
7  }
8}
9
10// Implement the groupBy method for the Array prototype.
11Array.prototype.groupBy = function <T>(keySelector: (item: T) => string): Record<string, T[]> {
12  // Use the reduce method to accumulate groups. The accumulator 'grouped' is an object 
13  // whose keys are determined by the keySelector function and whose values are arrays of items.
14  return this.reduce<Record<string, T[]>>((grouped, item) => {
15    // Obtain the key by passing the current item to the keySelector function.
16    const key = keySelector(item);
17    // If the key already exists in the accumulator object, push the item into the existing array.
18    if (grouped[key]) {
19      grouped[key].push(item);
20    } else {
21      // If the key does not exist, create a new array with the item.
22      grouped[key] = [item];
23    }
24    // Return the updated accumulator object for the next iteration.
25    return grouped;
26  }, {}); // Initialize the accumulator as an empty object.
27};
28
29// Example usage:
30// This call should group numbers by their string representation.
31// [1,2,3].groupBy(String) // {"1":[1],"2":[2],"3":[3]}
32
Not Sure What to Study? Take the 2-min Quiz:

What data structure does Breadth-first search typically uses to store intermediate states?

Time and Space Complexity

Time Complexity

The time complexity of the groupBy method is O(n), where n is the number of elements in the array. This is because the method iterates over all elements in the array exactly once. Inside the iteration, the grouping function fn is called once for each element, and the key assignment along with the conditional check and array push operation can be considered to take constant time (O(1)). Therefore, the overall time complexity is determined by the loop, making it O(n).

Space Complexity

The space complexity of the groupBy method is also O(n), where n is the number of elements in the array. A new Record<string, T[]> object is created where the worst-case scenario involves every element being placed into its own unique key, requiring storage space for n keys and n singleton arrays. In the best case, all elements fall under one key, in which case there's one key with one array of size n. However, since the space required grows linearly with the input array size, it's considered O(n).

Fast Track Your Learning with Our Quick Skills Quiz:

What is the running time of the following code?

1int sqrt(int n) {
2  for (int guess = 1; guess * guess <= n; guess++) {
3    if (guess * guess == n) {
4      return guess;
5    }
6  }
7  return -1;
8}

Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫