LeetCode 2675 - Array of Objects to Matrix

LeetCode Problem 2675

Difficulty: 🔴 Hard
Topics: —

Solution

Problem Understanding

The problem is asking us to transform a JSON-like array of objects or arrays into a matrix representation. Each row of the resulting matrix corresponds to one object (or array) in the input array, and the first row contains the column names. These column names are derived from the keys in the objects, and if the objects are nested, the keys are expressed as a path using dot notation. Arrays are treated as objects where the indices serve as keys. Missing values in an object should be represented by empty strings in the corresponding row. The columns themselves must be sorted lexicographically.

The input arr can be deeply nested and can contain primitive types like numbers, strings, booleans, or null. The constraints specify that the array length can be up to 1000 and the number of unique keys up to 1000, which is significant but manageable for modern algorithms. Edge cases include empty objects, nested structures, arrays instead of objects, or null/boolean values, all of which require careful handling to avoid index or type errors.

The key challenge is to flatten nested objects consistently into paths, collect all unique keys across all objects, sort them, and then populate the matrix while filling missing values with empty strings.

Approaches

A brute-force approach would be to iterate through each object, recursively flattening its keys and collecting them into a set. Then for each row, we would look up the value for each column key individually, recursively if necessary. While correct, this approach is inefficient because we repeatedly traverse nested structures for each cell of the matrix.

The optimal approach is based on the insight that we can pre-flatten all objects first and store them in dictionaries mapping the flattened paths to their values. By doing this, we traverse each object only once. Then, after collecting all keys and sorting them, we can populate the matrix by simple dictionary lookups, which ensures both correctness and efficiency.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * k * d)	O(k)	Recursively traverse objects for each cell in the matrix; d = max nesting depth
Optimal	O(n * k * d + k log k)	O(n * k)	Flatten each object once, collect keys, sort, and populate matrix

Algorithm Walkthrough

1. Initialize an empty set to collect all unique keys across all objects.
2. Define a recursive function flatten(obj, prefix) that traverses an object or array. If it encounters a nested object or array, it recursively constructs the full path key using dot notation. For leaf values, it stores them in a dictionary with the flattened key.
3. Iterate through the input array, flattening each object and storing the flattened representation in a list. Add all the keys to the set of unique keys.
4. Convert the set of unique keys into a list and sort it lexicographically. This list will be the first row of the matrix.
5. For each flattened object in the list, construct a row by iterating through the sorted column names and using the flattened object dictionary to fill in the value if it exists or "" otherwise.
6. Combine the column headers and the rows into the final matrix.

Why it works: Flattening each object ensures that all nested structures are represented consistently as paths. Collecting all keys guarantees that no column is missed, and sorting ensures the lexicographic order. The row construction ensures missing keys are handled correctly, producing a consistent matrix.

Python Solution

from typing import List, Any, Union

class Solution:
    def jsonToMatrix(self, arr: List[Any]) -> List[List[Any]]:
        def flatten(obj: Any, prefix: str = "") -> dict:
            flat = {}
            if isinstance(obj, dict):
                for k, v in obj.items():
                    new_key = f"{prefix}.{k}" if prefix else k
                    flat.update(flatten(v, new_key))
            elif isinstance(obj, list):
                for i, v in enumerate(obj):
                    new_key = f"{prefix}.{i}" if prefix else str(i)
                    flat.update(flatten(v, new_key))
            else:
                flat[prefix] = obj
            return flat
        
        all_keys = set()
        flat_objects = []
        for item in arr:
            flat = flatten(item)
            flat_objects.append(flat)
            all_keys.update(flat.keys())
        
        sorted_keys = sorted(all_keys)
        matrix = [sorted_keys]
        
        for flat in flat_objects:
            row = [flat.get(key, "") for key in sorted_keys]
            matrix.append(row)
        
        return matrix

The Python solution defines a recursive flatten function to convert nested objects into flat dictionaries with path keys. It collects all keys into a set, sorts them, and constructs the matrix by looking up each value in the flattened dictionaries.

Go Solution

package main

import (
	"sort"
	"strconv"
)

func jsonToMatrix(arr []interface{}) [][]interface{} {
	var flatten func(interface{}, string, map[string]interface{})
	flatten = func(obj interface{}, prefix string, flat map[string]interface{}) {
		switch val := obj.(type) {
		case map[string]interface{}:
			for k, v := range val {
				newKey := k
				if prefix != "" {
					newKey = prefix + "." + k
				}
				flatten(v, newKey, flat)
			}
		case []interface{}:
			for i, v := range val {
				newKey := strconv.Itoa(i)
				if prefix != "" {
					newKey = prefix + "." + newKey
				}
				flatten(v, newKey, flat)
			}
		default:
			flat[prefix] = val
		}
	}

	allKeysSet := make(map[string]struct{})
	flatObjects := make([]map[string]interface{}, len(arr))

	for i, item := range arr {
		flat := make(map[string]interface{})
		flatten(item, "", flat)
		flatObjects[i] = flat
		for k := range flat {
			allKeysSet[k] = struct{}{}
		}
	}

	allKeys := make([]string, 0, len(allKeysSet))
	for k := range allKeysSet {
		allKeys = append(allKeys, k)
	}
	sort.Strings(allKeys)

	matrix := make([][]interface{}, len(arr)+1)
	header := make([]interface{}, len(allKeys))
	for i, k := range allKeys {
		header[i] = k
	}
	matrix[0] = header

	for i, flat := range flatObjects {
		row := make([]interface{}, len(allKeys))
		for j, k := range allKeys {
			if v, ok := flat[k]; ok {
				row[j] = v
			} else {
				row[j] = ""
			}
		}
		matrix[i+1] = row
	}

	return matrix
}

The Go implementation mirrors the Python solution, with type assertions used to check whether an element is a map or slice. Keys are converted to strings for arrays. The struct{} set pattern ensures unique key collection, and slices are used for the final matrix.

Worked Examples

Example 1:

Input: [{"b":1,"a":2},{"b":3,"a":4}]

Flattened objects:

[{"b":1,"a":2}, {"b":3,"a":4}]

All keys: {"a","b"} → sorted ["a","b"]

Matrix construction:

[["a","b"], [2,1], [4,3]]

Example 3:

Input: [{"a":{"b":1,"c":2}}, {"a":{"b":3,"d":4}}]

Flattened objects:

[{"a.b":1,"a.c":2}, {"a.b":3,"a.d":4}]

All keys: {"a.b","a.c","a.d"} → sorted ["a.b","a.c","a.d"]

Matrix construction:

[["a.b","a.c","a.d"], [1,2,""], [3,"",4]]

Example 5:

Input: [{}, {}, {}]

Flattened objects: [{}, {}, {}]

All keys: {} → sorted []

Matrix: [[], [], [], []]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n * k * d + k log k)	Flatten each object once (n objects, k keys max, d depth), then sort keys
Space	O(n * k)	Store flattened objects for all n input objects

Flattening ensures that nested structures are processed efficiently, and sorting ensures lexicographical order. The space complexity is dominated by storing flattened objects.

Test Cases

# Provided examples
assert Solution().jsonToMatrix([{"b":1,"a":2},{"b":3,"a":4}]) == [["a","b"], [2,1], [4,3]]
assert Solution().jsonToMatrix([{"a":1,"b":2},{"c":3,"d":4}, {}]) == [["a","b","c","d"], [1,2,"",""], ["","",3,4], ["","","",""]]
assert Solution().jsonToMatrix([{"a":{"b":1,"c":2}}, {"a":{"b":3,"d":4}}]) == [["a.b","a.c","a.d"], [1,2,""], [3,"",4]]