Watch 6 video solutions for Array of Objects to Matrix, a hard level problem. This walkthrough by NeetCodeIO has 3,794 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Write a function that converts an array of objects arr into a matrix m.
arr is an array of objects or arrays. Each item in the array can be deeply nested with child arrays and child objects. It can also contain numbers, strings, booleans, and null values.
The first row m should be the column names. If there is no nesting, the column names are the unique keys within the objects. If there is nesting, the column names are the respective paths in the object separated by ".".
Each of the remaining rows corresponds to an object in arr. Each value in the matrix corresponds to a value in an object. If a given object doesn't contain a value for a given column, the cell should contain an empty string "".
The columns in the matrix should be in lexographically ascending order.
Example 1:
Input:
arr = [
{"b": 1, "a": 2},
{"b": 3, "a": 4}
]
Output:
[
["a", "b"],
[2, 1],
[4, 3]
]
Explanation:
There are two unique column names in the two objects: "a" and "b".
"a" corresponds with [2, 4].
"b" coresponds with [1, 3].
Example 2:
Input:
arr = [
{"a": 1, "b": 2},
{"c": 3, "d": 4},
{}
]
Output:
[
["a", "b", "c", "d"],
[1, 2, "", ""],
["", "", 3, 4],
["", "", "", ""]
]
Explanation:
There are 4 unique column names: "a", "b", "c", "d".
The first object has values associated with "a" and "b".
The second object has values associated with "c" and "d".
The third object has no keys, so it is just a row of empty strings.
Example 3:
Input:
arr = [
{"a": {"b": 1, "c": 2}},
{"a": {"b": 3, "d": 4}}
]
Output:
[
["a.b", "a.c", "a.d"],
[1, 2, ""],
[3, "", 4]
]
Explanation:
In this example, the objects are nested. The keys represent the full path to each value separated by periods.
There are three paths: "a.b", "a.c", "a.d".
Example 4:
Input:
arr = [
[{"a": null}],
[{"b": true}],
[{"c": "x"}]
]
Output:
[
["0.a", "0.b", "0.c"],
[null, "", ""],
["", true, ""],
["", "", "x"]
]
Explanation:
Arrays are also considered objects with their keys being their indices.
Each array has one element so the keys are "0.a", "0.b", and "0.c".
Example 5:
Input:
arr = [
{},
{},
{},
]
Output:
[
[],
[],
[],
[]
]
Explanation:
There are no keys so every row is an empty array.
Constraints:
arr is a valid JSON array1 <= arr.length <= 1000unique keys <= 1000Problem Overview: Convert an array of objects (which may contain nested objects or arrays) into a matrix. Each unique flattened key becomes a column header. Every row represents one object, and missing values are filled with an empty string. Keys must be flattened using dot notation (for example a.b) and sorted lexicographically before building the matrix.
Approach 1: Brute Force Key Scanning (O(n * k * u) time, O(u) space)
The naive strategy repeatedly scans each object for every discovered key. First flatten every object into a map of key → value. Maintain a global set of all keys seen. After collecting keys, iterate through the key list for each object and perform lookups to fill the matrix. If a key is missing, insert an empty string. This works but involves repeated checks for each key across every object, which becomes inefficient when the number of unique keys grows.
Approach 2: Flatten + Key Union + Matrix Build (O(nk + u log u) time, O(nk + u) space)
This is the practical approach used in most solutions. Iterate through the array and flatten each object using DFS. During flattening, build paths using dot notation (for example parent.child). Store the flattened representation in a hash map and add every encountered key to a global set. After processing all objects, convert the key set into a sorted array to form the matrix header row. Then iterate through the flattened maps and build rows by reading values in the sorted key order. Missing entries are replaced with "". The flattening step handles nested objects and arrays uniformly by recursively visiting children.
This solution relies on constant-time lookups from a hash map and performs sorting only once for the union of keys. The flattening step processes each property exactly once, making it efficient even for deeply nested structures. The algorithm mainly uses hash map lookups and a recursive traversal similar to depth-first search. Sorting the final key list ensures the matrix columns remain deterministic, which is required for the output format and relies on standard sorting behavior.
Recommended for interviews: The flatten + key union approach is the expected solution. Interviewers want to see that you can normalize nested structures, track unique keys efficiently with a set, and construct the final matrix using deterministic ordering. Mentioning the brute force idea first shows you understand the baseline, while implementing the flattened hash-map approach demonstrates practical problem-solving and clean data transformation skills.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Key Scanning | O(n * k * u) | O(u) | Simple implementation when the number of unique keys is very small |
| Flatten + Key Union + Matrix Build | O(nk + u log u) | O(nk + u) | General case with nested objects and many keys; optimal practical solution |