2675. Array of Objects to Matrix


Problem Description

The task is to write a function that converts an array of objects arr into a two-dimensional array, or matrix, m. The input array, arr, can contain objects that are nested, meaning that an object can have properties which are objects or arrays themselves. Additionally, these objects can have properties of different types including numbers, strings, booleans, and null values.

The first row of the resulting matrix m should contain column names. For non-nested objects, these names are simply the keys of the properties in the objects. For nested objects, the column names should represent the path to the property, with each level of nesting separated by a period ".".

Each subsequent row in the matrix corresponds to an object from the input array arr. The values are placed in the matrix in alignment with the column names. If an object does not have a value for a specific column, that matrix cell should be an empty string "".

Finally, the columns are to be sorted in lexicographically ascending order, which means dictionary order, considering the column names as strings.

Intuition

The proposed solution involves two main steps: First, it flattens the structure of the input objects to easily map them into rows of the matrix. Second, it constructs the matrix using column names in lexicographically ascending order.

For the flattening part, a depth-first search (DFS) algorithm is employed. DFS traverses nested objects and arrays and builds a flat key-value representation of the underlying data where the keys are the paths leading to each value. The paths reflect the structure of the original object with nested keys joined by a period ".".

Once flattened, the complete list of column names is derived from the keys of flattened objects. These keys are then deduplicated and sorted to form the first row of the matrix - the column header row.

The next part involves creating each row of the matrix corresponding to the input objects. For each object's flattened version, the values are filled in the appropriate columns, considering the sorted column names. If a value for a specific column is not found in the object, an empty string is inserted in that place.

By iterating through the entire array of objects and creating each row according to the gathered column names, the function builds the complete matrix, adhering to the requirements of the problem.

Solution Approach

The implementation of the solution can be broken down into several steps that reflect the thought process for handling the problem.

  1. Depth-First Search to Flatten Objects: To navigate through nested objects, a DFS algorithm is used. DFS is ideal for exploring all the paths through nested data as it goes as deep as possible down one path before backing up and trying another. Here, the dfs function is recursively called with a key (representing the current path) and obj, the object or value currently being explored.

    • It starts by checking if the obj is a leaf node, which in this context is a value that is not an object or an array – i.e., numbers, strings, booleans, or null. If it is, a single key-value pair is returned with the current key and the obj itself.

    • If the obj is another object or array, it iterates over the object entries and recursively calls dfs on each key-value pair, appending the current key to the new key for nested properties by newKey = key ? key.{key}.{k}:${k};, where k is the current object's key. The recursion ensures that all levels of nesting are accounted for in the final keys.

    • It accumulates and flattens these results to produce a single key-value pair for each property, regardless of how deeply nested it is in the original object.

  2. Creating a List of Unique Keys: After flattening each object into a collection of key-value pairs, all the keys are gathered into one array and then reduced to a unique set to eliminate duplicates. The unique keys are then sorted lexicographically using the .sort() method to define the column names for the matrix.

  3. Building the Matrix: With the list of keys prepared, the actual matrix construction begins. The sorted list of keys forms the first row of the matrix.

    • For each object (after flattening), the algorithm iterates over the list of sorted keys and checks if the object contains a value for each key. This is performed by searching the flattened objects for a property with that key. If the key is present, its value is inserted into the row; if not, an empty string "" is used as a placeholder.

    • The find function: row.find(r => r.hasOwnProperty(key))?.[key] is used to retrieve the value for a given key from the set of key-value pairs obtained after flattening.

    • The push method appends either the found value or an empty string to the newRow array, preparing a complete row of the matrix.

    • Each newRow is then added to the ans array, which accumulatively builds up the final matrix.

  4. Returning the Result: At the end of the iteration, the ans array contains the first row with the sorted column names and the subsequent rows representing objects' properties. The completed matrix is returned.

This approach efficiently handles the conversion of an array of potentially nested objects into a cleanly structured matrix, taking care to accommodate missing keys and ensuring the final columns are in the required lexicographic order.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What data structure does Breadth-first search typically uses to store intermediate states?

Example Walkthrough

Let's walk through a small example to illustrate the solution approach. Suppose we have the following array of objects:

1const arr = [
2  { name: 'Alice', age: 30, address: { city: 'Wonderland', zip: '12345' } },
3  { name: 'Bob', age: 22, contact: { email: '[email protected]', phone: '555-4132' } }
4];

Following our solution approach, we'd perform these steps:

  1. Depth-First Search to Flatten Objects:

    We use DFS to flatten each object in arr. For Alice, we would obtain:

    1{ 'name': 'Alice', 'age': 30, 'address.city': 'Wonderland', 'address.zip': '12345' }

    For Bob, similarly:

    1{ 'name': 'Bob', 'age': 22, 'contact.email': '[email protected]', 'contact.phone': '555-4132' }
  2. Creating a List of Unique Keys:

    Collect all keys from the flattened objects:

    1['name', 'age', 'address.city', 'address.zip', 'contact.email', 'contact.phone']

    Then, we remove duplicates and sort them lexicographically to get the column names for our matrix:

    1['address.city', 'address.zip', 'age', 'contact.email', 'contact.phone', 'name']
  3. Building the Matrix:

    With our sorted keys, we start building the matrix. The first row will be the column names:

    1[['address.city', 'address.zip', 'age', 'contact.email', 'contact.phone', 'name']]

    Then, we add rows for Alice and Bob. Since Alice does not have contact info, and Bob does not have an address, we put empty strings for those values:

    Alice's row:

    1['Wonderland', '12345', 30, '', '', 'Alice']

    Bob's row:

    1['', '', 22, '[email protected]', '555-4132', 'Bob']

    Adding these rows to our matrix results in:

    1[
    2  ['address.city', 'address.zip', 'age', 'contact.email', 'contact.phone', 'name'],
    3  ['Wonderland', '12345', 30, '', '', 'Alice'],
    4  ['', '', 22, '[email protected]', '555-4132', 'Bob']
    5]
  4. Returning the Result:

    Our final output is the completed matrix:

    1[
    2  ['address.city', 'address.zip', 'age', 'contact.email', 'contact.phone', 'name'],
    3  ['Wonderland', '12345', 30, '', '', 'Alice'],
    4  ['', '', 22, '[email protected]', '555-4132', 'Bob']
    5]

And this is how the solution approach breaks down a complex data structure into a structured matrix with sorted columns, dealing properly with nested objects and missing values.

Solution Implementation

1def json_to_matrix(json_array):
2    """
3    Converts JSON objects to a matrix representation. Each object's keys and values
4    are flattened into rows.
5    :param json_array: List of JSON objects
6    :return: Matrix (list of lists) with each row representing an object with flattened key-value pairs.
7    """
8
9    def flatten_object(prefix, value):
10        """
11        Helper function to flatten an object's keys and values.
12        Prefixes keys with their parent's keys for nesting.
13        :param prefix: String prefix for nested keys
14        :param value: The value to be processed, can be a dict or a primitive type
15        :return: Flattened representation of the object
16        """
17        # Directly return the value if it is primitive or null
18        if isinstance(value, (int, str, bool)) or value is None:
19            return {prefix: value}
20      
21        # Initialize an accumulator for flattened entries
22        result = []
23        # Iterate over the object properties if it is a dictionary
24        if isinstance(value, dict):
25            for key, val in value.items():
26                # Create a new key with the parent key prefix (if available)
27                new_key = f'{prefix}.{key}' if prefix else key
28                # Recursively flatten the object and accumulate results
29                result.extend(flatten_object(new_key, val))
30        # Flatten the list of results before returning and handle non-dict iterables
31        elif hasattr(value, '__iter__') and not isinstance(value, str):
32            for item in value:
33                result.extend(flatten_object(prefix, item))
34        else:
35            result.append({prefix: value})
36      
37        return result
38
39    # Map each JSON object in the input array to its flattened representation
40    flattened_entries = [flatten_object('', obj) for obj in json_array]
41
42    # Extract the unique keys across all flattened objects and sort them
43    unique_keys = sorted(set(
44        key for entry in flattened_entries for obj in entry for key in obj
45    ))
46
47    # Prepare the result matrix with the first row being the sorted keys
48    matrix = [unique_keys]
49
50    # Iterate over each flattened JSON object to create remaining matrix rows
51    for entry in flattened_entries:
52        matrix_row = []
53        # For each unique key, find the corresponding value in the current entry
54        for key in unique_keys:
55            # If a value for a key exists, push the value, otherwise push an empty string
56            found_entry = next((e for e in entry if key in e), None)
57            matrix_row.append(found_entry[key] if found_entry else '')
58        # Add the populated row to the matrix
59        matrix.append(matrix_row)
60
61    # Return the fully constructed matrix
62    return matrix
63
1import java.util.*;
2import java.util.stream.Collectors;
3
4public class JsonToMatrixConverter {
5
6    // Convert a JSON array to a matrix representation
7    public static List<List<Object>> jsonToMatrix(List<Map<String, Object>> jsonArray) {
8        // Map each JSON object to its flattened representation
9        List<Map<String, Object>> flattenedEntries = jsonArray.stream()
10                .map(obj -> flattenObject("", obj))
11                .collect(Collectors.toList());
12
13        // Extract the unique keys across all flattened objects and sort them
14        Set<String> uniqueKeysSet = new TreeSet<>();
15        for (Map<String, Object> entry : flattenedEntries) {
16            uniqueKeysSet.addAll(entry.keySet());
17        }
18        List<String> uniqueKeys = new ArrayList<>(uniqueKeysSet);
19
20        // Prepare the result matrix with the first row being the sorted keys
21        List<List<Object>> matrix = new ArrayList<>();
22        matrix.add(new ArrayList<>(uniqueKeys)); // Add the keys as the first row
23
24        // Iterate over each flattened JSON object to create the remaining matrix rows
25        for (Map<String, Object> entry : flattenedEntries) {
26            List<Object> matrixRow = new ArrayList<>();
27            // For each unique key, find the corresponding value in the current entry
28            for (String key : uniqueKeys) {
29                // If a value for a key exists, add the value, otherwise add an empty string
30                matrixRow.add(entry.getOrDefault(key, ""));
31            }
32            // Add the populated row to the matrix
33            matrix.add(matrixRow);
34        }
35
36        // Return the fully constructed matrix
37        return matrix;
38    }
39
40    // Helper function to flatten an object's keys and values with nested keys prefixed by their parent keys
41    private static Map<String, Object> flattenObject(String prefix, Object value) {
42        Map<String, Object> result = new HashMap<>(); // Initialize a map to hold the flattened results
43
44        // If the value is primitive or null, return it directly
45        if (value instanceof Number || value instanceof String || value instanceof Boolean || value == null) {
46            result.put(prefix, value);
47            return result;
48        }
49
50        // If the value is a Map, iterate over its entries
51        if (value instanceof Map) {
52            @SuppressWarnings("unchecked")
53            Map<String, Object> valueMap = (Map<String, Object>) value;
54            for (Map.Entry<String, Object> entry : valueMap.entrySet()) {
55                // For nested objects, create a new key with the parent key prefix
56                String newKey = prefix.isEmpty() ? entry.getKey() : prefix + "." + entry.getKey();
57                // Recursively flatten the object and merge the results into the 'result' map
58                result.putAll(flattenObject(newKey, entry.getValue()));
59            }
60        }
61
62        return result;
63    }
64
65    // Main method for testing
66    public static void main(String[] args) {
67        // Example JSON objects represented as maps
68        List<Map<String, Object>> exampleJsonArray = new ArrayList<>();
69        Map<String, Object> obj1 = new HashMap<>();
70        obj1.put("id", 1);
71        obj1.put("name", "John");
72        Map<String, Object> obj2 = new HashMap<>();
73        obj2.put("id", 2);
74        obj2.put("name", "Jane");
75        obj2.put("location", "NY");
76        exampleJsonArray.add(obj1);
77        exampleJsonArray.add(obj2);
78
79        // Convert the JSON array to a matrix
80        List<List<Object>> matrix = jsonToMatrix(exampleJsonArray);
81
82        // Print the matrix
83        for (List<Object> row : matrix) {
84            System.out.println(row);
85        }
86    }
87}
88
1#include <vector>
2#include <string>
3#include <map>
4#include <set>
5#include <nlohmann/json.hpp> // Assuming use of nlohmann::json library for JSON operations
6
7// Function to convert JSON objects to a matrix representation. Each object's keys and values are flattened into rows.
8std::vector<std::vector<std::variant<std::string, double, bool, std::nullptr_t>>> JsonToMatrix(const std::vector<nlohmann::json>& jsonArray) {
9    using json = nlohmann::json;
10    using Variant = std::variant<std::string, double, bool, std::nullptr_t>;
11
12    // Helper function to flatten an object's keys and values. Prefixes keys with their parent's keys for nesting.
13    std::function<std::map<std::string, Variant>(const std::string&, const json&)> FlattenObject = [&](const std::string& prefix, const json& value) -> std::map<std::string, Variant> {
14        std::map<std::string, Variant> resultMap;
15
16        if (value.is_primitive()) {
17            // Directly return the value if it is primitive or null.
18            return {{prefix, value}};
19        } 
20        // Check if the value is an object and iterate over properties.
21        else if (value.is_object()) {
22            for (auto it = value.begin(); it != value.end(); ++it) {
23                // Create a new key with the parent key prefix (if available).
24                const std::string newKey = prefix.empty() ? it.key() : prefix + "." + it.key();
25                // Recursively flatten the object and insert results into the map.
26                auto nestedMap = FlattenObject(newKey, it.value());
27                resultMap.insert(nestedMap.begin(), nestedMap.end());
28            }
29        }
30
31        return resultMap;
32    };
33
34    // Create a set to store unique keys and a vector of maps for flattened JSON objects.
35    std::set<std::string> uniqueKeys;
36    std::vector<std::map<std::string, Variant>> flattenedEntries;
37
38    // Map each JSON object in the input array to its flattened representation.
39    for (const auto& obj : jsonArray) {
40        auto flattenedEntry = FlattenObject("", obj);
41        flattenedEntries.push_back(std::move(flattenedEntry));
42        for (const auto& pair : flattenedEntries.back()) {
43            uniqueKeys.insert(pair.first);
44        }
45    }
46
47    // Prepare the result matrix with the first row being the sorted keys.
48    std::vector<std::vector<Variant>> matrix;
49    std::vector<Variant> headerRow;
50    for (const auto& key : uniqueKeys) {
51        headerRow.push_back(key);
52    }
53    matrix.push_back(headerRow);
54
55    // Iterate over each flattened JSON object to create remaining matrix rows.
56    for (const auto& entry : flattenedEntries) {
57        std::vector<Variant> matrixRow;
58      
59        // For each unique key, find the corresponding value in the current entry.
60        for (const auto& key : uniqueKeys) {
61            auto foundEntry = entry.find(key);
62            if (foundEntry != entry.end()) {
63                matrixRow.push_back(foundEntry->second);
64            } else {
65                matrixRow.push_back(""); // Use an empty string when the key is not found.
66            }
67        }
68        // Add the populated row to the matrix.
69        matrix.push_back(matrixRow);
70    }
71
72    // Return the fully constructed matrix.
73    return matrix;
74}
75// NOTE: To use std::variant and nlohmann::json library, C++17 and the JSON library need to be enabled and included respectively.
76
1// Function to convert JSON objects to a matrix representation. Each object's keys and values are flattened into rows.
2function jsonToMatrix(jsonArray: any[]): (string | number | boolean | null)[][] {
3    // Helper function to flatten an object's keys and values. Prefixes keys with their parent's keys for nesting.
4    const flattenObject = (prefix: string, value: any): { [key: string]: any } => {
5        // Directly return the value if it is primitive or null.
6        if (
7            typeof value === 'number' ||
8            typeof value === 'string' ||
9            typeof value === 'boolean' ||
10            value === null
11        ) {
12            return { [prefix]: value };
13        }
14        // Initialize an array to accumulate flattened entries.
15        const result: any[] = [];
16        // Iterate over the object properties.
17        for (const [key, val] of Object.entries(value)) {
18            // Create a new key with the parent key prefix (if available).
19            const newKey = prefix ? `${prefix}.${key}` : `${key}`;
20            // Recursively flatten the object and push results into the array.
21            result.push(flattenObject(newKey, val));
22        }
23        // Flatten the array of results before returning.
24        return result.flat();
25    };
26
27    // Map each JSON object in the input array to its flattened representation.
28    const flattenedEntries = jsonArray.map(obj => flattenObject('', obj));
29
30    // Extract the unique keys across all flattened objects and sort them.
31    const uniqueKeys = [...new Set(
32        flattenedEntries
33            .flat()
34            .map(obj => Object.keys(obj))
35            .flat()
36    )].sort();
37
38    // Prepare the result matrix with the first row being the sorted keys.
39    const matrix: (string | number | boolean | null)[][] = [uniqueKeys];
40
41    // Iterate over each flattened JSON object to create remaining matrix rows.
42    for (const entry of flattenedEntries) {
43        const matrixRow: (string | number | boolean | null)[] = [];
44        // For each unique key, find the corresponding value in the current entry.
45        for (const key of uniqueKeys) {
46            // If a value for a key exists, push the value, otherwise push an empty string.
47            const foundEntry = entry.find(e => e.hasOwnProperty(key));
48            matrixRow.push(foundEntry ? foundEntry[key] : '');
49        }
50        // Add the populated row to the matrix.
51        matrix.push(matrixRow);
52    }
53
54    // Return the fully constructed matrix.
55    return matrix;
56}
57

Time and Space Complexity

Time Complexity

To analyze the time complexity of the jsonToMatrix function, let's examine the steps involved:

  1. dfs function - The dfs (Depth-First Search) function is a recursive function which is called for each property in the object.

    • For each property that is a primitive value (number, string, boolean, or null), it performs a constant amount of work.
    • For nested objects, it iterates through all keys and calls itself recursively.
    • Assuming that the average depth of the objects is d and the average number of keys at each level is k, the time complexity of the dfs function is approximately O(k^d).
  2. arr.map call - The dfs function is called once for each item in the input array arr, with the length of the array being n, resulting in a time complexity of O(n * k^d) for this step.

  3. Generation of keys array - This involves flattening the array of key-value pairs and extracting keys. The flattening operation has a complexity of O(n * k^d) since it involves concatenating arrays returned by the dfs function. The creation of the Set to filter out unique keys is O(u) where u is the number of unique keys, which is less than or equal to n * k^d.

  4. The ans array - The nested loop involves iterating over each row and then each key. Assuming there are m unique keys, the complexity of this step is O(n * m).

Combining all these steps, the overall time complexity will be dominated by the arr.map call and the operations inside it. Therefore, the overall time complexity of the jsonToMatrix function is O(n * k^d + n * m) where:

  • n is the length of the input array arr,
  • k is the average number of keys in an object,
  • d is the average depth of nested objects,
  • m is the number of unique keys across all objects.

Space Complexity

The space complexity considers the memory used throughout the execution of the function:

  1. Recursive dfs calls - Each recursive call creates a new execution context, and the maximum depth of the recursive call stack will be d, so the space complexity due to recursion is O(d).

  2. kv and ans arrays - These arrays are used to store intermediate and final results. Since ans includes a row for each input object plus one row for the keys, its size is O(n * m). The kv array contains the results of the dfs function calls and has a similar size.

  3. keys array - Storing the unique keys requires a space of O(u), where u is the number of unique keys, which can be as much as O(n * k^d) in the worst case.

The main contributing factor to space complexity is the output array ans and the set of unique keys. Therefore, the overall space complexity of the jsonToMatrix function is O(n * m + n * k^d + d). Simplified, assuming m is bounded by n * k^d, the final space complexity is O(n * k^d + d) where:

  • d is the average depth of nested objects,
  • n is the length of the input array arr,
  • k is the average number of keys in an object.

Fast Track Your Learning with Our Quick Skills Quiz:

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


🪄