2775. Undefined to Null


Problem Description

The task is to write a function called undefinedToNull that accepts a parameter obj. This parameter could be a deeply nested object or an array. The purpose of this function is to traverse the entire structure of obj, and wherever an undefined value is found, it should be replaced with null. This process is essential because when JavaScript objects are serialized into a JSON string using JSON.stringify(), undefined values can cause problems while null does not. Ensuring all undefined values are converted to null can help avoid unexpected errors when the data is serialized.

Intuition

To solve this problem, we need to perform a deep traversal of the input object or array. We can use a recursive approach. The intuition is to iterate over each property if the input is an object or over each element if it's an array. If a property or element is another object or array, we should recursively call the same function on that sub-object or sub-array to handle any nested structures.

This process allows us to reach every level of nesting. When we encounter an undefined value at any level, we replace it with null. We continue this process until we have checked and possibly replaced every undefined value throughout the entire structure. The function then returns the modified object or array, which has all undefined values converted to null.

The solution provided does not check explicitly for arrays, assuming that an array is an object with numerical keys. However, this might have unintended side effects in TypeScript or JavaScript, considering Arrays have different characteristics than plain objects. For full robustness, the solution could be modified to handle arrays and objects distinctly.

Solution Approach

The solution uses a recursive function undefinedToNull to traverse the deeply nested objects or arrays and replace undefined values with null. The approach can be broken down into the following steps:

  1. Iterate through each property of the object using a for...in loop.
  2. Check if the current property's value is an object itself. If it is, we recursively call undefinedToNull on this sub-object to handle nested structures.
  3. After the recursive call (or immediately, if the property is not an object), check if the current property's value is undefined.
  4. If the value is undefined, update it to null.
  5. Once the loop is complete, which signifies that all properties have been checked and updated if necessary, return the modified object.

Key Points of the Implementation:

  • Recursive Function: The function undefinedToNull calls itself to handle nested objects or arrays. This allows the function to handle any level of nesting.
  • In-Place Updates: The function modifies the input object directly, which may or may not be desired. To avoid mutating the input, one would need to create a copy of each nested object or array before making modifications.
  • TypeScript Signatures: The function is written using TypeScript, with Record<any, any> used as the type signature. This indicates that the function expects an object-like structure with keys and values of any type.

Potential Improvements:

While this implementation achieves the task it sets out to do, a more robust implementation might consider the following:

  • Immutable Updates: Instead of modifying the input object, returning a new object with the applied changes to keep the function pure, avoiding side effects.
  • Array Checks: Adding explicit checks to determine if the object is Array to use array-specific methods might be necessary for some edge cases.
  • Handling Circular References: In its current form, the function would be trapped in an infinite loop if the object contains circular references. Handling such cases requires tracking visited objects.

The resolved solution effectively ensures that all undefined values within the nested structure are turned to null, a critical requirement when serializing the data with JSON.stringify(), as undefined values are not included, while null values are preserved in the serialized JSON.

💪
Level Up Your
Algo Skills

Example Walkthrough

Let's say we want to use the undefinedToNull function on a sample object to understand how it will replace undefined with null. Consider the following example object, which has multiple levels of nesting and contains both undefined and properly defined values:

1let sampleObject = {
2  level1: {
3    level2a: undefined,
4    level2b: {
5      level3: 'data',
6      level3_undefined: undefined
7    }
8  },
9  level1_array: [1, undefined, 3],
10  level1_undefined: undefined
11};

Now, let's walk through how the solution approach will handle this sampleObject:

  1. We start by calling undefinedToNull(sampleObject).
  2. The function begins iterating through the properties of sampleObject.
  3. The first property is level1, an object, so we call undefinedToNull on level1.
  4. Inside this call, we find level2a with a value of undefined. We replace it with null.
  5. Next, level2b is an object, so we call undefinedToNull on level2b.
  6. Here, we find level3_undefined set to undefined and update it to null. The level3 property is not modified as it's a string.
  7. Returning from the recursion, we are back at the top level and move to level1_array, an array.
  8. The array contains undefined at index 1, which we replace with null.
  9. Finally, we update level1_undefined to null since its value is undefined.

After all the recursive calls, sampleObject is directly modified, and the properties with undefined values have been replaced with null. The output would be:

1{
2  level1: {
3    level2a: null,
4    level2b: {
5      level3: 'data',
6      level3_undefined: null
7    }
8  },
9  level1_array: [1, null, 3],
10  level1_undefined: null
11}

With the defined approach, we successfully traverse the entire structure of the object, replacing all undefined values with null, readying our sampleObject for any serialization that may occur, without any errors related to undefined values.

Python Solution

1def undefined_to_null(obj):
2    """
3    Recursively converts all 'None' values within an object (dictionary) or a list to 'None'.
4  
5    :param obj: The object (dictionary) or list to be processed.
6    :return: The new object (dictionary) or list with 'None' instead of 'None' values.
7    """
8    # Check if 'obj' is a dictionary
9    if isinstance(obj, dict):
10        for key in obj:
11            # If the value is a dictionary or a list, apply recursion
12            if isinstance(obj[key], (dict, list)):
13                obj[key] = undefined_to_null(obj[key])
14            # If the value is 'None', replace with 'None'
15            if obj[key] is None:
16                obj[key] = None
17  
18    # Check if 'obj' is a list
19    elif isinstance(obj, list):
20        for index, value in enumerate(obj):
21            # If the element is a dictionary or a list, apply recursion
22            if isinstance(value, (dict, list)):
23                obj[index] = undefined_to_null(value)
24            # If the element is 'None', replace with 'None'
25            if value is None:
26                obj[index] = None
27
28    return obj
29
30# Usage examples:
31# print(undefined_to_null({"a": None, "b": 3})) # {"a": None, "b": 3}
32# print(undefined_to_null([None, None])) # [None, None]
33

Java Solution

1import java.util.List;
2import java.util.Map;
3
4public class UndefinedToNullConverter {
5
6    /**
7     * Recursively converts all null values within a map or list to a specific value.
8     *
9     * @param obj The map or list to be processed.
10     * @return The new map or list with nulls instead of undefined values.
11     */
12    public static Object undefinedToNull(Object obj) {
13        if (obj instanceof Map<?, ?>) {
14            Map<?, ?> map = (Map<?, ?>) obj;
15            for (Object key : map.keySet()) {
16                Object value = map.get(key);
17                if (value instanceof Map<?, ?> || value instanceof List<?>) {
18                    map.put(key, undefinedToNull(value));
19                }
20                if (value == null) {
21                    map.put(key, null);
22                }
23            }
24        } else if (obj instanceof List<?>) {
25            List<?> list = (List<?>) obj;
26            for (int i = 0; i < list.size(); i++) {
27                Object value = list.get(i);
28                if (value instanceof Map<?, ?> || value instanceof List<?>) {
29                    list.set(i, undefinedToNull(value));
30                }
31                if (value == null) {
32                    list.set(i, null);
33                }
34            }
35        }
36        return obj;
37    }
38
39    // Usage examples:
40    public static void main(String[] args) {
41        Map<String, Object> map = Map.of("a", null, "b", 3);
42        System.out.println(undefinedToNull(map)); // {a=null, b=3}
43
44        List<Object> list = List.of(null, null);
45        System.out.println(undefinedToNull(list)); // [null, null]
46    }
47}
48

C++ Solution

1#include <iostream>
2#include <map>
3#include <vector>
4#include <any>
5
6// Function template that works with both std::map and std::vector as a container.
7template <typename T>
8T undefinedToNull(T container) {
9    // Iterate over all keys if container is a map or over indices if it's a vector
10    for (auto& element : container) {
11        // std::any is used to hold any type, similar to the JavaScript object values
12        auto& value = element.second; // For maps, access the value part
13        if constexpr (std::is_same_v<T, std::vector<std::any>>) {
14            value = element; // For vectors, each element is the value itself
15        }
16
17        // If the value is an object (std::map) or an array (std::vector) itself, apply the function recursively
18        if (value.has_value() && value.type() == typeid(T)) {
19            value = std::any_cast<T>(value);
20            value = undefinedToNull(std::any_cast<T>(value));
21        }
22        // Convert any undefined (empty std::any) values to null (std::any with nullptr)
23        if (!value.has_value()) {
24            value = std::any(nullptr);
25        }
26    }
27
28    return container;
29}
30
31// Overload of undefinedToNull for std::map, since the original JavaScript function supports objects.
32template <typename K, typename V>
33std::map<K, V> undefinedToNull(std::map<K, V> obj) {
34    for (auto& [key, value] : obj) {
35        // If the value is an object (std::map) or an array (std::vector) itself, apply the function recursively
36        if (std::holds_alternative<std::map<K, V>>(value) || std::holds_alternative<std::vector<V>>(value)) {
37            value = std::visit([](auto&& arg) -> V { return undefinedToNull(arg); }, value);
38        }
39        // Convert any undefined (empty std::variant) values to null (std::variant with nullptr)
40        if (!std::holds_alternative<V>(value)) {
41            value = nullptr;
42        }
43    }
44
45    return obj;
46}
47
48// Example usage:
49int main() {
50    // Create a map with one element being undefined (empty std::any)
51    std::map<std::string, std::any> myMap = {{"a", std::any()}, {"b", 3}};
52    myMap = undefinedToNull(myMap);
53
54    // Create a vector with elements being undefined (empty std::any)
55    std::vector<std::any> myVector = {std::any(), std::any()};
56    myVector = undefinedToNull(myVector);
57
58    // Output sanitized containers
59    // To print the values from myMap and myVector, you would need to add custom code to handle the type-erased std::any values.
60
61    return 0;
62}
63

Typescript Solution

1/**
2 * Recursively converts all undefined values within an object or array to null.
3 * @param {Record<any, any> | any[]} obj - The object or array to be processed.
4 * @returns {Record<any, any> | any[]} The new object or array with nulls instead of undefined values.
5 */
6function undefinedToNull(obj: Record<any, any> | any[]): Record<any, any> | any[] {
7    // Iterate over all keys if obj is an object or over indices if it's an array
8    for (const key in obj) {
9        // If the value is an object or an array itself, apply the function recursively
10        if (obj[key] && typeof obj[key] === 'object') {
11            obj[key] = undefinedToNull(obj[key]);
12        }
13        // Convert any undefined values to null
14        if (obj[key] === undefined) {
15            obj[key] = null;
16        }
17    }
18  
19    return obj;
20}
21
22// Usage examples:
23// console.log(undefinedToNull({"a": undefined, "b": 3})); // {"a": null, "b": 3}
24// console.log(undefinedToNull([undefined, undefined])); // [null, null]
25

Time and Space Complexity

Time Complexity

The time complexity of the undefinedToNull function is essentially O(N), where N is the total number of elements and nested elements within the object. This is because the function must visit each element once to check for undefined and convert it to null.

Here's the breakdown:

  • The for loop iterates over each property in the input object.
  • The if (typeof obj[key] === 'object') check runs in constant time O(1) for each element.
  • The recursive call to undefinedToNull for objects ensures that every nested object is also traversed.

So if we have a single-level object with n keys, the complexity is O(n). For nested objects, the function will traverse into each nested object, which could contain up until n elements itself, resulting in the time complexity of O(n + n^2) for two levels of nesting, and so on, depending on the depth and structure of the nesting. Despite the potential for factorial growth with nested structures, it is more practical to consider this an O(n) operation, where n is the total count of elements including nested ones, because each is only visited once.

Space Complexity

The space complexity of the function is also O(N). Although the function runs in-place by altering the passed object, due to recursive calls, each call adds a new frame to the call stack with its own execution context; this leads to additional space usage in proportion to the depth of recursion.

For an object with a depth of d and branching factor b at each level (assuming each property is an object), we would effectively have a recursion depth of d, each adding to the space complexity. Hence, the space complexity could be considered to be O(d), where d is the depth of the object.

However, if we consider N to represent the total number of element and nested elements within the object (accounting for all levels of nesting), then the space complexity simplifies to O(N) since we accumulate a call stack frame for each element we visit.

😈
Become an
Algo Monster

Got a question? Ask the Teaching 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.


TA 👨‍🏫