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.
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 <= 105fn returns a stringThe core idea behind Group By is to organize elements of an array into collections based on a key generated from each element. Instead of comparing every pair of elements, an efficient strategy is to iterate through the array once and place each element into a bucket determined by a key function.
A common approach is to use a hash map (or object/dictionary) where the key is the result of applying the grouping function fn(element). For every element, compute the key and append the element to the corresponding list in the map. If the key does not yet exist, initialize a new array for that key.
This technique avoids nested loops and ensures efficient grouping. Since each element is processed exactly once, the solution runs in linear time. The additional space used depends on the number of unique groups created.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Hash Map / Object-based Grouping | O(n) | O(n) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
First declare an object that will eventually be returned.
Iterate of each element in the array. You can access the array with the "this" keyword.
The key is fn(arr[i]). If the key already exists on the object, set the value to be an empty array. Then push the value onto the array at the key.
This approach involves iterating over each element of the array, applying the provided function to determine the key for each element, and then organizing elements in an object based on these keys.
Time Complexity: O(n * m) where n is the number of elements and m is the average length of strings (due to strcmp operation).
Space Complexity: O(n) for storage of key-value mappings.
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4
5typedef struct Element {
6 char *key;
7 void **values;
8 size_t size;
9} Element;
10
11Element *groupBy(void **array, size_t array_size, char *(*fn)(void*), size_t *returned_size) {
12 Element *groups = malloc(array_size * sizeof(Element));
13 size_t group_count = 0;
14
15 for (size_t i = 0; i < array_size; i++) {
16 char *key = fn(array[i]);
17 size_t j;
18 for (j = 0; j < group_count; j++) {
19 if (strcmp(groups[j].key, key) == 0) {
20 groups[j].values = realloc(groups[j].values, (groups[j].size + 1) * sizeof(void*));
21 groups[j].values[groups[j].size++] = array[i];
22 break;
23 }
24 }
25 if (j == group_count) {
26 groups[group_count].key = key;
27 groups[group_count].values = malloc(sizeof(void*));
28 groups[group_count].values[0] = array[i];
29 groups[group_count].size = 1;
30 group_count++;
31 }
32 }
33
34 *returned_size = group_count;
35 return groups;
36}This solution represents the grouping result using a list of structures in C. Each structure holds a key and a dynamically sized array of values. The code iterates through the input array, applies the function to get keys, and organizes them accordingly.
This approach recursively divides the array, processes elements with memoization to store previously encountered keys, thus reducing redundant calculations, which optimizes processing of large arrays.
Time Complexity: O(n * m), where m is affected by recursion depth.
Space Complexity: O(n) for memo storage and call stack.
1#
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
Yes, grouping and hashing problems are common in technical interviews at FAANG-level companies. They test your understanding of hash maps, data transformation, and efficient iteration patterns.
The optimal approach uses a hash map or dictionary to store grouped elements. For each array element, compute the key using the provided function and append the element to the corresponding list. This ensures linear time processing without nested iterations.
A hash map allows quick access to groups using keys generated by the grouping function. Since each element is processed once and inserted into a bucket in constant time on average, the overall algorithm remains highly efficient.
A hash map (or object in JavaScript) is the most suitable data structure. It allows constant-time insertion and lookup, making it efficient to create and manage groups dynamically while iterating through the array.
In this recursive implementation, the function would conceptually keep a cache of already encountered keys, to avoid recalculating them. As memory allocation and proper recursive function configuration is complex in C, it's a theoretical implementation.