Watch 7 video solutions for Group By, a medium level problem. This walkthrough by NeetCodeIO has 5,266 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 stringProblem Overview: You receive an array and a function fn. For every element in the array, the function returns a key. The task is to group elements that produce the same key and return them in a structure where each key maps to the list of corresponding elements.
Approach 1: Iterative Grouping (Hash Map) (Time: O(n), Space: O(n))
The straightforward approach iterates through the array once and builds groups using a hash map (or dictionary/object depending on the language). For each element x, compute the key using fn(x). Check whether that key already exists in the map. If it does, append the element to the existing list; otherwise create a new list and insert the element. This works because hash map lookups and insertions are constant time on average. After processing all elements, the map directly represents the grouped result. This approach is widely used in real systems for aggregation tasks such as categorizing logs or grouping records by attribute. It relies heavily on fast key lookups provided by a hash map and sequential traversal of the array.
Approach 2: Recursive Grouping with Memoization (Time: O(n), Space: O(n))
A recursive variant processes the array one index at a time while maintaining a shared memo structure that stores grouped results. The recursion processes element i, computes fn(arr[i]), inserts the value into the corresponding group, and then calls itself for i + 1. Memoization simply means the grouping map persists across recursive calls rather than being rebuilt. This produces the same final structure as the iterative solution but expresses the traversal through recursion. The recursion depth becomes n, which adds stack usage, making it slightly less practical in languages with strict recursion limits. This approach mainly demonstrates recursive problem decomposition and ties into concepts from recursion.
Recommended for interviews: The iterative hash map approach is what interviewers typically expect. It shows you recognize grouping as a hash map aggregation problem and can implement it in a single pass with O(n) time. Mentioning the recursive alternative demonstrates deeper understanding of traversal strategies, but the iterative method is clearer, safer for large inputs, and closer to production code.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Grouping (Hash Map) | O(n) | O(n) | Best general solution. Efficient single-pass grouping using constant-time hash lookups. |
| Recursive Grouping with Memoization | O(n) | O(n) + recursion stack | Useful for demonstrating recursion-based traversal or functional-style implementations. |