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.

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

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.