2705. Compact Object


Problem Description

In this problem, we are given an input that could be either an object or an array, referred to as obj. Our task is to produce a "compact" version of this object. By "compact", what is meant is that we need to remove any key-value pairs from the object where the value is falsy. A falsy value is one that, when converted to a boolean, equals false. Examples of falsy values in JavaScript include 0, null, undefined, false, NaN, and "" (an empty string).

To clarify further, this process must apply recursively to all nested objects within obj. If obj is an array, we should treat it similarly to an object, wherein the indices are keys; hence, any element with a falsy value should be removed. We can assume that obj contains only valid JSON data types since it is stated that obj could be the result of JSON.parse.

Intuition

To tackle this challenge, we need a recursive approach because objects can be nested within objects, and we need to ensure that we're removing falsy values at all levels.

For arrays, the solution entails iterating over all elements, keeping only the truthy values, and if an element is itself an object or array, calling the compactObject function recursively to compact that element before adding it back to the array.

For objects, we iterate over each key-value pair. When we encounter a falsy value, we remove the key from the object. If the value is an object (nested object or array), we make a recursive call to compactObject to deal with nested structures before assigning the compacted object back to the key.

Here is the intuitive step-by-step manner in which the solution works:

  1. Check if the input obj is an array using Array.isArray().
  2. If it is an array:
    • Create a temporary array to store the non-falsy values.
    • Loop through each element in the original array.
    • For each element, check if it is truthy.
    • If the truthy element is an object, call compactObject on it, then push the compacted object to the temp array.
    • If the element is truthy and not an object, directly push it to the temp array.
    • After the loop, return the temp array, which contains only non-falsy values or compacted objects.
  3. If obj is an object (and not an array):
    • Loop through each key-value pair using Object.entries() to access both key and value.
    • Check if the value is falsy. If so, delete the key from the object.
    • If the value is an object, make a recursive call to compactObject(value) and assign the result back to obj[key].
    • Once all the keys have been processed, return the object.

At the end of this process, we are left with a "compact" version of the original object or array, devoid of any falsy values.

Solution Approach

The implementation follows a recursive strategy, which is commonly used for problems involving nested data structures like objects or arrays. The solution exploits the ability in JavaScript to differentiate between arrays and objects and handle them appropriately.

Here's how the implementation unfolds:

  1. We define a TypeScript type Obj which represents a record with keys of any type and values of any type. In JavaScript, objects serve as associative arrays or hash maps, allowing for the storage and retrieval of data through key-value pairs.

  2. The compactObject function takes in an object of type Obj and returns an object of the same type. The initial check determines whether the input is an array or not.

  3. If it's an array, a temporary array temp is created. We iterate over each element of the original array, and we have two cases to handle:

    • If the current item is truthy, and...
      • It is an object (which includes arrays in JavaScript since arrays are a special kind of object), then we recursively call compactObject(item) to compact the object, and we push the result into our temp array.
      • It is not an object (e.g., a number, string that's not empty, etc.), then we directly push this item into our temp array.
  4. If the input obj is not an array, it must be an object. We then use Object.entries(obj) to iterate over the key-value pairs in the object. For each pair, we have two cases:

    • If the value is falsy (!value returns true), we remove the key from the object using delete obj[key].
    • If the value is truthy and an object (or an array), we recursively call our compactObject function on this value. The compacted object (or array) is then assigned back to the current key in our original object with obj[key] = compactObject(value).
  5. Finally, for both the array and the object case, the function returns the newly created temp array or the modified original object obj, respectively, both of which are now compacted versions of the input, free of falsy values.

The chosen algorithm is depth-first in nature because it calls itself recursively to deal with any nested objects before it moves on to the next sibling at the same level. This depth-first approach ensures that all levels of nested data structures are adequately compacted before finalizing any one level.

This approach works well with JSON objects/array structure, ensuring that no matter how deeply nested an object or array might be, all keys associated with falsy values are pruned.

Here is part of the TypeScript code, which is essentially JavaScript with type annotations for better developer readability and error checking, explaining the key parts of the recursive function:

1function compactObject(obj: Obj): Obj {
2    // Checks if the object is an array
3    if (Array.isArray(obj)) {
4        const temp = [];
5        // Process each element if it's an array
6        // ...
7        return temp;
8    }
9    // Not an array, so an object; process each key-value pair
10    for (const [key, value] of Object.entries(obj)) {
11        if (!value) delete obj[key];  // Delete falsy value
12        else if (typeof value === 'object') obj[key] = compactObject(value);  // Recursive call
13    }
14    return obj;
15}

This code snippet demonstrates the conditional paths for arrays versus objects and includes the key operations of filtering out falsy values and the recursive calls necessary for nested structures.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following is a good use case for backtracking?

Example Walkthrough

Let's consider a simple example to illustrate the solution approach. Suppose we have the following obj, a mixed array that contains various elements, including falsy values and nested objects:

1let obj = [0, 1, false, { a: null, b: "string", c: { d: undefined, e: 2 } }, "", [], [3, null]];

We want to compact this array, removing any elements with falsy values and ensuring that any nested arrays or objects are also compacted.

  1. The compactObject function is called with obj. It discovers that obj is an array.

  2. It creates a temporary array temp to store non-falsy values.

  3. It starts iterating over obj. It encounters the following:

    • 0 (falsy) — Skipped and not added to temp.
    • 1 (truthy) — Added to temp.
    • false (falsy) — Skipped.
    • The next element is an object { a: null, b: "string", c: { d: undefined, e: 2 }}.
      • It makes a recursive call to compactObject for this nested object.
        • In this recursive call:
          • a: null (falsy) — This key-value pair is removed.
          • b: "string" (truthy) — Kept.
          • c: { d: undefined, e: 2 } — Another recursive call is made.
            • d: undefined (falsy) — Removed.
            • e: 2 (truthy) — Kept.
          • The object { b: "string", c: { e: 2 }} is returned and added to temp.
    • "" (falsy) — Skipped.
    • [] (truthy, but empty array) — Added to temp as is.
    • [3, null] — A recursive call compacts it to [3], and this array is added to temp.
  4. After the iteration, temp holds [1, { b: "string", c: { e: 2 }}, [], [3]].

  5. The function returns the compacted temp array.

Our original obj has been transformed into its compact version [1, { b: "string", c: { e: 2 }}, [], [3]]. Thus, the implementation correctly removes all falsy values, including those nested in objects and arrays, resulting in a cleaner and more concise data structure.

Solution Implementation

1def compact_object(obj):
2    """
3    Removes falsy values from a dictionary or a list.
4    Recursive for nested dictionaries and lists.
5  
6    :param obj: The dictionary or list to compact.
7    :return: The dictionary or list with falsy values removed.
8    """
9    # If the input is a list, compact the list.
10    if isinstance(obj, list):
11        compacted_list = []
12        for item in obj:
13            # Check if the item is truthy.
14            if item:
15                # If the item itself is an object (list or dict), recurse.
16                # Otherwise, add the item to the compacted list.
17                compacted_list.append(compact_object(item) if isinstance(item, (dict, list)) else item)
18        return compacted_list
19
20    # If the input is a dictionary, compact the dictionary.
21    elif isinstance(obj, dict):
22        # Create a copy to avoid modifying the input dictionary while iterating.
23        keys_to_delete = []
24        for key, value in obj.items():
25            # Check if the value is falsy.
26            if not value:
27                # Mark the key for removal if the value is falsy.
28                keys_to_delete.append(key)
29            elif isinstance(value, (dict, list)):
30                # If the value itself is an object (list or dict), apply recursion.
31                obj[key] = compact_object(value)
32
33        # Delete the marked keys from the dictionary.
34        for key in keys_to_delete:
35            del obj[key]
36
37        return obj
38
39    else:
40        # If the obj is neither a list nor a dictionary, just return it.
41        return obj
42
1import java.util.HashMap;
2import java.util.Map;
3import java.util.List;
4import java.util.ArrayList;
5
6public class ObjectCompactor {
7
8    /**
9     * Removes falsy values from an object or a list.
10     * Recursive for nested objects and lists.
11     *
12     * @param object - The object or list to compact.
13     * @return - The object or list with falsy values removed.
14     */
15    public static Object compactObject(Object object) {
16        // If the input is a list, compact the list.
17        if (object instanceof List) {
18            List<?> originalList = (List<?>) object;
19            List<Object> compactedList = new ArrayList<>();
20
21            for (Object item : originalList) {
22                if (isTruthy(item)) {
23                    // If the item is a Map or List, recurse.
24                    // Otherwise, add the item to the compactedList.
25                    compactedList.add((item instanceof Map || item instanceof List) ? compactObject(item) : item);
26                }
27            }
28            return compactedList;
29        } else if (object instanceof Map) { // If the input is a Map, compact the Map.
30            Map<?, ?> originalMap = (Map<?, ?>) object;
31            Map<Object, Object> compactedMap = new HashMap<>();
32
33            for (Map.Entry<?, ?> entry : originalMap.entrySet()) {
34                if (isTruthy(entry.getValue())) {
35                    // If the value is a Map or List, apply recursion.
36                    compactedMap.put(entry.getKey(), (entry.getValue() instanceof Map || entry.getValue() instanceof List) ? compactObject(entry.getValue()) : entry.getValue());
37                }
38            }
39            return compactedMap;
40        } else {
41            // If the input is neither a List nor a Map, simply return the object
42            return object;
43        }
44    }
45
46    /**
47     * Helper method to determine if an object is "truthy" (not null and not false).
48     *
49     * @param obj - The object to check.
50     * @return true if the object is "truthy", false otherwise.
51     */
52    private static boolean isTruthy(Object obj) {
53        return obj != null && !Boolean.FALSE.equals(obj);
54    }
55}
56
1#include <vector>
2#include <map>
3#include <string>
4#include <any>
5#include <type_traits>
6
7// Compact the given std::map or std::vector by removing falsy values.
8// This function is overloaded to handle both containers.
9std::map<std::string, std::any> compactObject(const std::map<std::string, std::any>& object);
10std::vector<std::any> compactObject(const std::vector<std::any>& array);
11
12// Helper function to check if an std::any object is falsy.
13bool isFalsy(const std::any& value) {
14    try {
15        if (value.type() == typeid(bool)) {
16            return !std::any_cast<bool>(value);
17        } else if (value.type() == typeid(int)) {
18            return std::any_cast<int>(value) == 0;
19        } else if (value.type() == typeid(double)) {
20            return std::any_cast<double>(value) == 0.0;
21        } else if (value.type() == typeid(std::string)) {
22            return std::any_cast<std::string>(value).empty();
23        } else {
24            // Consider any other type as not falsy.
25            return false;
26        }
27    } catch (const std::bad_any_cast&) {
28        // If any_cast throws, the type is not falsy.
29        return false;
30    }
31}
32
33// Compacts the given std::vector by removing falsy values, and
34// applies recursion if an element is another container.
35std::vector<std::any> compactObject(const std::vector<std::any>& array) {
36    std::vector<std::any> compactedArray;
37    for (const auto& item : array) {
38        if (!isFalsy(item)) {
39            if (item.type() == typeid(std::map<std::string, std::any>)) {
40                compactedArray.push_back(compactObject(std::any_cast<std::map<std::string, std::any>>(item)));
41            } else if (item.type() == typeid(std::vector<std::any>)) {
42                compactedArray.push_back(compactObject(std::any_cast<std::vector<std::any>>(item)));
43            } else {
44                compactedArray.push_back(item);
45            }
46        }
47    }
48    return compactedArray;
49}
50
51// Compacts the given std::map by removing falsy values, and
52// applies recursion if a value is another container.
53std::map<std::string, std::any> compactObject(const std::map<std::string, std::any>& object) {
54    std::map<std::string, std::any> compactedObject;
55    for (const auto& [key, value] : object) {
56        if (!isFalsy(value)) {
57            if (value.type() == typeid(std::map<std::string, std::any>)) {
58                compactedObject[key] = compactObject(std::any_cast<std::map<std::string, std::any>>(value));
59            } else if (value.type() == typeid(std::vector<std::any>)) {
60                compactedObject[key] = compactObject(std::any_cast<std::vector<std::any>>(value));
61            } else {
62                compactedObject[key] = value;
63            }
64        }
65    }
66    return compactedObject;
67}
68
1// Type definition for a generic object with any key type and any value type.
2type GenericObject = Record<string, unknown>;
3
4/**
5 * Removes falsy values from an object or an array.
6 * Recursive for nested objects and arrays.
7 * 
8 * @param {GenericObject | unknown[]} object - The object or array to compact.
9 * @return {GenericObject | unknown[]} - The object or array with falsy values removed.
10 */
11function compactObject(object: GenericObject | unknown[]): GenericObject | unknown[] {
12    // If the input is an array, compact the array.
13    if (Array.isArray(object)) {
14        const compactedArray = [];
15        for (const item of object) {
16            if (item) {
17                // If the item is an object, recurse.
18                // Otherwise, add the item to the compacted array.
19                compactedArray.push(typeof item === 'object' ? compactObject(item as GenericObject) : item);
20            }
21        }
22        return compactedArray;
23    } else { // If the input is an object, compact the object.
24        for (const [key, value] of Object.entries(object)) {
25            if (!value) {
26                // Remove the key if the value is falsy.
27                delete object[key];
28            } else if (typeof value === 'object') {
29                // If the value is an object, apply recursion
30                object[key] = compactObject(value as GenericObject);
31            }
32        }
33        return object;
34    }
35}
36

Time and Space Complexity

Time Complexity:

The function compactObject operates by checking each element of the input obj. If obj is an array, it iterates through every element, and if an element is truthy and an object, it calls itself recursively; otherwise, it pushes the item into a new array. When obj is a regular object, it iterates through all key-value pairs, deleting falsy values or recursively calling itself on sub-objects.

Let n be the combined number of elements and properties in all nested structures within the input object (including arrays and sub-objects). The worst-case time complexity is O(n) because each element or property is visited at most once. Even though there is recursion, each call processes a different part of the object without revisiting any elements or properties.

However, note that JavaScript objects have some overhead for property access and deletion, which does not significantly affect the big O notation but may impact real-world performance.

Space Complexity:

The space complexity is also O(n) in the worst case. This is due to several factors:

  1. Each recursive call to compactObject occupies additional space on the call stack.
  2. New arrays and objects are created to store the compacted versions of the input.
  3. Temporary arrays are created to store non-falsy items when input is an array.

The actual space used depends on the depth of the nested structures and the number of non-falsy elements kept after compaction. The space is linearly proportional to the number of items and nested objects in the input due to the recursion stack and new structures created.

Note that in JavaScript, objects and arrays are reference types. Hence the size of pointers is considered rather than the size of the actual values when calculating space complexity.


Fast Track Your Learning with Our Quick Skills Quiz:

How does merge sort divide the problem into subproblems?


Recommended Readings


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


🪄