Problem

Write code that enhances all arrays such that you can call the array.groupBy(fn) method on any array and it will return a grouped version of the array.

A grouped array is an object where each key is the output of fn(arr[i]) and each value is an array containing all items in the original array which generate that key.

The provided callback fn will accept an item in the array and return a string key.

The order of each value list should be the order the items appear in the array. Any order of keys is acceptable.

Please solve it without lodash’s _.groupBy function.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

Input: 
array = [
  {"id":"1"},
  {"id":"1"},
  {"id":"2"}
], 
fn = function (item) { 
  return item.id; 
}
Output: 
{ 
  "1": [{"id": "1"}, {"id": "1"}],   
  "2": [{"id": "2"}] 
}
Explanation:
Output is from array.groupBy(fn).
The selector function gets the "id" out of each item in the array.
There are two objects with an "id" of 1. Both of those objects are put in the first array.
There is one object with an "id" of 2. That object is put in the second array.

Example 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

Input: 
array = [
  [1, 2, 3],
  [1, 3, 5],
  [1, 5, 9]
]
fn = function (list) { 
  return String(list[0]); 
}
Output: 
{ 
  "1": [[1, 2, 3], [1, 3, 5], [1, 5, 9]] 
}
Explanation:
The array can be of any type. In this case, the selector function defines the key as being the first element in the array. 
All the arrays have 1 as their first element so they are grouped together.
{
  "1": [[1, 2, 3], [1, 3, 5], [1, 5, 9]]
}

Example 3

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

Input: 
array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
fn = function (n) { 
  return String(n > 5);
}
Output:
{
  "true": [6, 7, 8, 9, 10],
  "false": [1, 2, 3, 4, 5]
}
Explanation:
The selector function splits the array by whether each number is greater than 5.

Constraints

  • 0 <= array.length <= 10^5
  • fn returns a string

Solution

Method 1 – Prototype Extension with Reduce

Intuition

We want to add a groupBy method to all arrays, which groups elements by a key returned from a callback. We can use reduce to build the grouped object efficiently.

Approach

  1. Extend Array.prototype with a groupBy method.
  2. The method takes a callback fn that returns a key for each element.
  3. Use reduce to iterate over the array:
    • For each element, call fn to get the key.
    • Add the element to the array at that key in the result object, creating the array if needed.
  4. Return the grouped object.

Code

1
2
3
4
5
6
7
8

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

declare global {
    interface Array<T> {
        groupBy(fn: (item: T) => string): Record<string, T[]>;
    }
}
Array.prototype.groupBy = function<T>(this: T[], fn: (item: T) => string): Record<string, T[]> {
    return this.reduce((ans: Record<string, T[]>, item: T) => {
        const key = fn(item);
        if (!ans[key]) ans[key] = [];
        ans[key].push(item);
        return ans;
    }, {});
};

Complexity

  • ⏰ Time complexity: O(n) — Each element is visited once.
  • 🧺 Space complexity: O(n) — Output object stores all elements grouped by key.