Array of Objects to Matrix - Solution & Explanation

Problem 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.