Group By solution and explanation
7 more videos on this problem
Group By - Leetcode 2631 - JavaScript 30-Day ChallengeNeetCodeIO · 7:35 · 5K views
Group By | Leetcode 2631 | JSON | 30 Days of JavaScript #javascript #leetcodeLearn With Chirag · 8:49 · 1K views
#day23 | 2631. Group By | 30 Days of JavaScript | Leetcode-2631 | 30 Days | JSON | this keywordCoding with Ankita · 14:37 · 411 views
2631. Group By - Day 24/30 Leetcode Javascript ChallengeProgramming Live with Larry · 2:39 · 235 views
Mastering Array Grouping in JavaScript: LeetCode Challenge 24 / 30 Day Prototype Group By 2631vanAmsen · 4:29 · 170 views
Group By - LeetCode 2631 - JavaScript - JS 30 Day Challenge Day 24Alpha-Code · 13:05 · 92 views
#2631 Group By | 30 Days of JavaScript | #javascript #leetcodesolution #javascriptdevelopersProgrammers choice · 7:19 · 26 views
Day 23 of My 30 Days of JavaScript Challenge — LeetCode 2631 Group By 🔍📦Code and Click · 3:21 · 3 views
The 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.
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 <= 105fnreturns a string
Approach overview
Problem 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 1: Iterative Grouping
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.
def group_by(array, fn):
grouped = {}
for item in array:
key = fn(item)
if key not in grouped:
grouped[key] = []
grouped[key].append(item)
return groupedimport java.util.*;
public class GroupBy {
public static Map<String, List<Object>> groupBy(List<Object> list, Function<Object, String> fn) {
Map<String, List<Object>> grouped = new HashMap<>();
for (Object obj : list) {
String key = fn.apply(obj);
grouped.computeIfAbsent(key, k -> new ArrayList<>()).add(obj);
}
return grouped;
}
}#include <iostream>
#include <vector>
#include <unordered_map>
#include <string>
std::unordered_map<std::string, std::vector<void*>> groupBy(std::vector<void*> array, std::string (*fn)(void*)) {
std::unordered_map<std::string, std::vector<void*>> grouped;
for (auto& item : array) {
std::string key = fn(item);
grouped[key].emplace_back(item);
}
return grouped;
}Array.prototype.groupBy = function(fn) {
return this.reduce((grouped, item) => {
const key = fn(item);
if (!grouped[key]) {
grouped[key] = [];
}
grouped[key].push(item);
return grouped;
}, {});
};#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Element {
char *key;
void **values;
size_t size;
} Element;
Element *groupBy(void **array, size_t array_size, char *(*fn)(void*), size_t *returned_size) {
Element *groups = malloc(array_size * sizeof(Element));
size_t group_count = 0;
for (size_t i = 0; i < array_size; i++) {
char *key = fn(array[i]);
size_t j;
for (j = 0; j < group_count; j++) {
if (strcmp(groups[j].key, key) == 0) {
groups[j].values = realloc(groups[j].values, (groups[j].size + 1) * sizeof(void*));
groups[j].values[groups[j].size++] = array[i];
break;
}
}
if (j == group_count) {
groups[group_count].key = key;
groups[group_count].values = malloc(sizeof(void*));
groups[group_count].values[0] = array[i];
groups[group_count].size = 1;
group_count++;
}
}
*returned_size = group_count;
return groups;
}using System;
using System.Collections.Generic;
public class GroupBy {
public static Dictionary<string, List<T>> GroupBy<T>(List<T> list, Func<T, string> fn) {
var grouped = new Dictionary<string, List<T>>();
foreach (var item in list) {
var key = fn(item);
if (!grouped.ContainsKey(key)) {
grouped[key] = new List<T>();
}
grouped[key].Add(item);
}
return grouped;
}
}This Python solution uses a dictionary to perform grouping. It iterates over items, applies the function to determine keys, and aggregates accordingly.
Time Complexity: O(n).
Space Complexity: O(n).
Approach 2: Recursive Grouping with Memoization
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.
def recursive_group(array, fn, memo=None):
if memo is None:
memo = {}
if not array:
return memo
item = array[0]
key = fn(item)
if key not in memo:
memo[key] = []
memo[key].append(item)
return recursive_group(array[1:], fn, memo)import java.util.*;
public class RecursiveGroupBy {
public static Map<String, List<Object>> recursiveGroup(List<Object> list, Function<Object, String> fn, Map<String, List<Object>> memo) {
if (list.isEmpty()) return memo;
Object obj = list.remove(0);
String key = fn.apply(obj);
memo.computeIfAbsent(key, k -> new ArrayList<>()).add(obj);
return recursiveGroup(list, fn, memo);
}
}#include <iostream>
#include <vector>
#include <unordered_map>
#include <string>
#include <unordered_set>
std::unordered_map<std::string, std::vector<void*>> recursiveGroup(std::vector<void*> &array, std::string (*fn)(void*), std::unordered_map<std::string, std::vector<void*>> &memo) {
// Check if the array to group is empty
if (array.empty()) return memo;
auto front = array.back();
array.pop_back();
std::string key = fn(front);
memo[key].emplace_back(front);
return recursiveGroup(array, fn, memo);
}function recursiveGroupBy(array, fn, memo = {}) {
if (array.length === 0) return memo;
const [head, ...tail] = array;
const key = fn(head);
if (!memo[key]) {
memo[key] = [];
}
memo[key].push(head);
return recursiveGroupBy(tail, fn, memo);
}#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct KeyValue {
char *key;
void **values;
size_t size;
} KeyValue;
KeyValue * recursiveGroupBy(void **arr, size_t size, char *(*fn)(void*), size_t *resultSize) {
// Recursive grouping logic with memoization should be implemented here
}using System;
using System.Collections.Generic;
public class RecursiveGroupBy {
public static Dictionary<string, List<T>> RecursiveGroup<T>(List<T> list, Func<T, string> fn, Dictionary<string, List<T>> memo = null) {
if (memo == null) memo = new Dictionary<string, List<T>>();
if (list.Count == 0) return memo;
T item = list[0];
string key = fn(item);
if (!memo.ContainsKey(key)) {
memo[key] = new List<T>();
}
memo[key].Add(item);
return RecursiveGroup(list.GetRange(1, list.Count - 1), fn, memo);
}
}The Python recursive solution shrinks the list recursively while deploying a dictionary memo that catalogs keys and values in progress.
Time Complexity: O(n) with potential overhead from list slicing.
Space Complexity: O(n) accounting for memoization structure and recursion call depth.
Approach 3: Default Approach
declare global {
interface Array<T> {
groupBy(fn: (item: T) => string): Record<string, T[]>;
}
}
Array.prototype.groupBy = function (fn) {
return this.reduce((acc, item) => {
const key = fn(item);
if (acc[key]) {
acc[key].push(item);
} else {
acc[key] = [item];
}
return acc;
}, {});
};
/**
* [1,2,3].groupBy(String) // {"1":[1],"2":[2],"3":[3]}
*/Complexity comparison
| Approach | Complexity |
|---|---|
| Iterative Grouping | Time Complexity: |
| Recursive Grouping with Memoization | Time Complexity: |
| Default Approach | – |
Complexity analysis
| 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. |
Frequently asked questions
Is Group By easy or hard?
The problem is typically rated Medium because it tests understanding of hash map grouping patterns rather than complex algorithms. The logic is straightforward, but recognizing the aggregation pattern quickly is the key skill being evaluated.
Group By Python/Java solution
In Python, a dictionary maps keys to lists and elements are appended using dict.setdefault or defaultdict. In Java, a HashMap maps keys to ArrayLists with computeIfAbsent used to initialize groups. Both implementations follow the same O(n) hash-based grouping strategy.
How to solve Group By in O(n)?
Traverse the array once and maintain a hash map where the key is the result of the grouping function. For each element, compute the key, check if the key exists in the map, and append the value to the corresponding array. This single-pass aggregation ensures O(n) time complexity.
What is the best approach for Group By?
The optimal approach uses a hash map to group elements in a single pass. Iterate through the array, compute a key using the provided function, and append the element to the corresponding list in the map. This runs in O(n) time with O(n) space and is the standard solution expected in interviews.
Is Group By asked at Google/Amazon/Meta?
Grouping problems appear frequently in interviews at large tech companies because they test understanding of hash maps and data aggregation patterns. Variants show up in questions involving log analysis, categorization, and frequency grouping.
What data structure is used in Group By?
A hash map (dictionary or object) is the core data structure. It maps each computed key to a list of elements that share that key. The hash map enables constant-time insertion and lookup, which keeps the overall algorithm linear.
What is the time complexity of Group By?
The optimal solution runs in O(n) time because each element is processed exactly once and hash map operations are O(1) on average. Space complexity is O(n) since every element must appear in a grouped list in the output structure.