Group By

Problem Statement

The goal is to enhance array functionality by adding a method named array.groupBy(fn). This method will transform an array into an object where each key corresponds to the result of a provided function fn applied to each item in the array. Each key in the resulting object will map to an array of elements that, when passed to fn, produce that key. The callback function fn takes an element of the array and returns a string, which is then used as a key. The sequence of elements within these grouped arrays should reflect their original order in the input array. The requirement is to accomplish this without using lodash's _.groupBy utility.

Examples

Example 1

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

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

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 <= 105
• fn returns a string

Approach and Intuition

1. Initialization: We begin by defining the method groupBy on the Array prototype. This allows all array instances to access this method directly.

2. Method Definition:

   • The method should take a function fn as an argument. This function is applied to each element of the array to determine the key under which the element will be grouped.
   • We initialize an empty object that will eventually be populated with keys and arrays as values.

3. Iterating Over Elements:

   • As we iterate through the array, for each element, we apply fn to generate a key.
   • If the key does not exist in our object, we initialize a new array for that key.
   • We then append the current element to the array that corresponds to this key.

4. Order Preservation: By simply appending elements to the arrays in the order they appear and using the resulting grouping directly from this iteration, we ensure that the order of elements in subarrays matches their original order in the input array.

5. Performance Considerations:

   • The solution requires efficient look-ups and insertions as it processes each element of the array once, leading to a run-time complexity of O(n), where n is the number of elements in the array.
   • Memory complexity is also O(n) in the worst-case scenario, where each item forms its own group.

6. Edge Cases:

   • The method should correctly handle the case of an empty array.
   • It should manage arrays with different data types since fn is expected to handle the logic of key extraction and should return a valid string key no matter the input type.

By extending the prototype of Array, this method will be universally available to all array instances, making it flexible and easy to use in various contexts as demonstrated in the examples. This approach sticks to JavaScript's dynamic nature, allowing for versatile key generation strategies determined by the function fn.

Solutions

Array.prototype.clusterBy = function(fn) {
  return this.reduce((collector, element) => {
    const key = fn(element);
    collector[key] = collector[key] || [];
    collector[key].push(element);
    return collector;
  }, {});
};