We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Group By

Number: 2742

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Enhance all arrays so that you can call array.groupBy(fn) on any array. The method should take a function that returns a string key for each item in the array, and then return an object where keys are the results of the function and values are arrays containing all items from the original array that correspond to that key. The order of items in each group should be preserved.

Key Insights

  • Extend the Array prototype (or add a utility function) to include a groupBy method.
  • Iterate through the array only once to maintain O(n) time complexity.
  • Use an object (hash map) where keys are the output of the provided function and values are arrays.
  • Ensure that items are appended in order to maintain the input order within each group.

Space and Time Complexity

Time Complexity: O(n), where n is the number of elements in the array. Space Complexity: O(n), as we store all elements in the resulting grouped object.

Solution

We use an iterative approach that goes through each element in the array exactly once. For each element, we compute its key by calling the provided function. If the key is already present in the group object, we append the element to the existing array. Otherwise, we create a new array for that key with the current element.

For Python and JavaScript, we can modify the behavior by creating a utility function or extending a class. For Java and C++, we provide separate implementations that mimic similar behavior by using collections like HashMap or unordered_map.

Code Solutions

# Define a function that mimics the behavior of the groupBy method.
def group_by(array, fn):
    # Initialize an empty dictionary to hold the grouped data.
    grouped = {}  
    # Iterate through each element in the array.
    for item in array:
        # Compute the key using the passed function.
        key = fn(item)
        # If the key doesn't exist in the dictionary, initialize it with an empty list.
        if key not in grouped:
            grouped[key] = []
        # Append the current item to the list corresponding to the key.
        grouped[key].append(item)
    # Return the grouped dictionary.
    return grouped

# Example usage:
if __name__ == "__main__":
    # Example input:
    array = [{"id": "1"}, {"id": "1"}, {"id": "2"}]
    fn = lambda item: item["id"]
    # Call the function and print the result.
    print(group_by(array, fn))
← Back to All Questions