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

Array of Objects to Matrix

Number: 2769

Difficulty: Hard

Paid? Yes

Companies: N/A

Problem Description

Given an array of objects (or arrays) that may have deeply nested structures, convert the input into a matrix. The first row of the output matrix must contain the unique column names, where nested keys are represented as dot-separated paths. Each subsequent row represents an object from the input. If an object does not have a value for a particular column, the corresponding cell should be an empty string. The column names must be ordered in lexicographically ascending order.

Key Insights

  • Recursively traverse each object/array to flatten nested structures into key paths.
  • Treat arrays as objects where indices are used as keys.
  • Use a set or similar data structure to collect all unique column names.
  • After processing, sort the column names lexicographically.
  • For each object, create a row in the resulting matrix with values corresponding to the sorted column keys; default to an empty string for missing keys.

Space and Time Complexity

Time Complexity: O(n * m * k) where n is the number of objects, m is the average number of keys per object (accounting for nesting), and k is the average length of the paths. Space Complexity: O(U + n * m) where U is the number of unique keys, and n * m accounts for storing the flattened representations and the final matrix.

Solution

The solution employs a recursive depth-first search (DFS) to flatten each nested object. The helper function handles both objects and arrays by augmenting the current path (using dot notation) and stores primitive values (including null) against these paths. As we process each item in the input array, we collect all flattened key paths into a set and keep a per-object mapping of key-paths to values. Once every object is processed, the unique keys are sorted lexicographically to form the header row. Each object then produces a row in the matrix, with empty strings populating cells for missing keys.

Data structures used include dictionaries (or maps) for storing flattened key-value pairs, a set for tracking unique keys, and lists (or arrays) for constructing the final matrix. The algorithm's core is the DFS for flattening nested structures, which systematically builds the correct key path for every value.

Code Solutions

# Python solution with inline comments

def array_to_matrix(arr):
    # Helper function to flatten nested objects/arrays into key paths.
    def flatten(item, prefix="", result=None):
        if result is None:
            result = {}
        # If the item is a dictionary, traverse its keys
        if isinstance(item, dict):
            for key, value in item.items():
                new_key = f"{prefix}.{key}" if prefix else key
                flatten(value, new_key, result)
        # If the item is a list, use indices as keys
        elif isinstance(item, list):
            for index, value in enumerate(item):
                new_key = f"{prefix}.{index}" if prefix else str(index)
                flatten(value, new_key, result)
        # For primitives (including null), assign the current key path.
        else:
            result[prefix] = item
        return result

    flat_list = []  # List to hold flattened dictionaries for each object in arr.
    all_keys = set()  # Set to gather all unique flattened key paths.

    # Process every element in arr.
    for item in arr:
        flat = flatten(item) if item is not None else {}
        flat_list.append(flat)
        all_keys.update(flat.keys())

    # Order the keys lexicographically to form the header.
    sorted_keys = sorted(all_keys)

    # Build the resulting matrix with the header first.
    matrix = [sorted_keys]
    for flat in flat_list:
        row = [flat.get(key, "") for key in sorted_keys]
        matrix.append(row)
    return matrix

# Example usage:
arr = [
    {"a": {"b": 1, "c": 2}},
    {"a": {"b": 3, "d": 4}}
]
print(array_to_matrix(arr))
← Back to All Questions