LeetCode 2775 - Undefined to Null

Difficulty: 🟡 Medium
Topics: —

Solution

Problem Understanding

The problem requires us to recursively traverse a nested object or array and replace all occurrences of undefined with null. In JavaScript, undefined and null behave differently when serializing objects to JSON. Specifically, JSON.stringify() ignores properties with undefined values, which can result in missing keys in the serialized output. By converting undefined to null, we ensure that the property is preserved with a valid JSON value.

The input obj can be a JSON object or array containing nested objects, arrays, primitive values, or undefined. The output should preserve the original structure but with all undefined values replaced by null. The constraints indicate that the object is a valid JSON object, and the total serialized length is manageable, up to 105 characters, so recursion or traversal of the object is feasible.

Important edge cases include: objects with deeply nested arrays or objects, arrays containing undefined, and objects that are entirely undefined values. The problem guarantees the input is valid JSON-compatible data, so we do not need to handle circular references or invalid types.

Approaches

The brute-force approach would involve serializing the object to a string and then manually replacing undefined with null using string manipulation. While this might produce correct output for small objects, it is error-prone, inefficient, and does not scale well for deeply nested structures.

The optimal approach is to recursively traverse the object or array, checking each value. If the value is undefined, it is replaced with null. If the value is an array or object, we recursively process its elements or properties. This approach works in-place or via a new object, and it guarantees that all nested undefined values are correctly converted without altering other data types.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Serialize and replace string representations, error-prone and inefficient for nested structures
Optimal	O(n)	O(d)	Recursively traverse the object/array, replacing undefined; `d` is recursion depth

Algorithm Walkthrough

Define a recursive function convert that takes a value as input.
Check if the value is undefined. If so, return null.
Check if the value is an array. If it is, create a new array and recursively call convert on each element, replacing each element with its converted value.
Check if the value is an object (excluding null). If it is, create a new object and recursively call convert on each property value, replacing each key’s value with the converted result.
If the value is neither undefined, an array, nor an object, return the value as is.
Call convert on the top-level object and return the result.

Why it works: The recursive traversal ensures that every level of nesting is visited exactly once, and every undefined value is replaced by null. Objects and arrays preserve their structure because we rebuild them recursively with the converted values.

Python Solution

from typing import Any

class Solution:
    def undefinedToNull(self, obj: Any) -> Any:
        def convert(value: Any) -> Any:
            if value is None:
                return None
            if isinstance(value, list):
                return [convert(v) for v in value]
            if isinstance(value, dict):
                return {k: convert(v) if v is not None else None for k, v in value.items()}
            return value
        
        return convert(obj)

In this Python implementation, we define a helper function convert that handles the recursion. Lists are processed by a list comprehension that recursively converts each element. Dictionaries are processed with a dictionary comprehension, recursively converting each value. Primitive values and None (which represents JavaScript null) are returned directly.

Go Solution

package main

func undefinedToNull(obj any) any {
    switch v := obj.(type) {
    case nil:
        return nil
    case []any:
        newArr := make([]any, len(v))
        for i, val := range v {
            newArr[i] = undefinedToNull(val)
        }
        return newArr
    case map[string]any:
        newMap := make(map[string]any)
        for key, val := range v {
            if val == nil {
                newMap[key] = nil
            } else {
                newMap[key] = undefinedToNull(val)
            }
        }
        return newMap
    default:
        return v
    }
}

In Go, we use a type switch to handle different types. Arrays are processed by creating a new slice and recursively converting each element. Maps are processed by creating a new map and recursively converting each value. Primitive types are returned directly.

Worked Examples

Example 1: {"a": undefined, "b": 3}

Step	Value	Conversion
Initial	{"a": undefined, "b": 3}	traverse dict
Key "a"	undefined	convert to null
Key "b"	3	leave as is
Result	{"a": null, "b": 3}	complete

Example 2: {"a": undefined, "b": ["a", undefined]}

Step	Value	Conversion
Initial	{"a": undefined, "b": ["a", undefined]}	traverse dict
Key "a"	undefined	convert to null
Key "b"	["a", undefined]	traverse list
Element 0	"a"	leave as is
Element 1	undefined	convert to null
Result	{"a": null, "b": ["a", null]}	complete

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each element and property is visited exactly once, `n` is the total number of elements and properties
Space	O(d)	Maximum recursion depth is the nesting level `d`; new structures use O(n) space if creating new copies

The algorithm’s linear time complexity is due to visiting each element or property once. The recursion depth depends on the maximum nesting, which is limited by the constraints. The space used is proportional to recursion depth and the size of new structures.

Test Cases

# Basic undefined conversion in object
assert Solution().undefinedToNull({"a": None, "b": 3}) == {"a": None, "b": 3}

# Undefined in nested array
assert Solution().undefinedToNull({"a": None, "b": ["x", None]}) == {"a": None, "b": ["x", None]}

# Nested objects
assert Solution().undefinedToNull({"x": {"y": None}, "z": 1}) == {"x": {"y": None}, "z": 1}

# Array of objects with undefined
assert Solution().undefinedToNull([{"a": None}, {"b": 2}]) == [{"a": None}, {"b": 2}]

# Empty object and array
assert Solution().undefinedToNull({}) == {}
assert Solution().undefinedToNull([]) == []

# Primitive values
assert Solution().undefinedToNull(5) == 5
assert Solution().undefinedToNull("test") == "test"

Test	Why
Basic undefined conversion	Validates single-level replacement
Undefined in nested array	Checks nested array conversion
Nested objects	Ensures recursion works with nested objects
Array of objects	Mix of array and object nested structures
Empty structures	Edge case with no elements
Primitive values	Confirms primitives remain unchanged

Edge Cases

One important edge case is when an array contains undefined elements. Without proper recursion, a naive solution might skip converting elements inside arrays, leading to incorrect JSON serialization. Our implementation traverses arrays and converts each element individually.

A second edge case is deeply nested objects, such as {"a": {"b": {"c": undefined}}}. If recursion is not properly implemented or limited, the solution could either miss converting undefined or exceed the recursion stack limit. Our solution handles this by recursively visiting each nested object.

A third edge case is primitive values at the top level, such as 5 or "string". The algorithm must return these unchanged, not convert them to null or wrap them in a container. Our implementation correctly identifies non-object, non-array types and returns them directly.