2823. Deep Object Filter

Problem Description

The goal of this problem is to write a function deepFilter that takes an object or an array (obj) and a filter function (fn). This function should return a new object or array (filteredObject) where only the elements or properties that pass the filter function (fn) are retained. It is called "deep" because the filtering should apply not just to the top-level elements, but to all nested objects or arrays as well.

However, there's a special rule in this filtering operation: if after filtering, an object or array does not contain any elements or properties, it should not remain as an empty structure. Instead, it should not exist at all in the resulting structure. This means that if a nested object or array becomes empty after filtering, it should be removed. And if the top-level object or array ends up having no content, the function should return undefined.

This problem requires us to visit all elements deeply (recursively) and apply the filter function, while also making sure to prune the structure of any empty parts that result from the filter operation.

Intuition

To solve this problem, we need to perform a deep traversal of the given object or array, applying the provided filter function to each value. For objects or arrays, we also need to check the results of filtering their children and remove any that are empty after the filtering process.

We can approach this recursively using a Depth-First Search (DFS) strategy. Here's how the intuition translates into a solution approach:

• If we encounter an array, we recursively call our dfs function on each of its elements, using map. Then, we filter out any undefined values (indicating filtered or empty elements). If the resulting array is empty, we return undefined.
• If we come across an object, we traverse its keys and recursively apply dfs on each property's value. Here too, we only keep keys whose values are not undefined after filtering. If the resulting object has no keys, we return undefined.
• For other data types (primitives like numbers or strings), we apply the filter function fn directly. If the filter function returns false, we return undefined.
• At the top level, we simply call our dfs function on the input obj and return the result, which could be undefined if the original obj is completely filtered out.

The recursive handling of arrays and objects makes sure we correctly prune away empty structures after filtering, while the use of map and filtering for arrays, and hasOwnProperty checking for objects, maintains the integrity of the original data structure (not affecting the original obj).

The use of a helper function dfs within deepFilter keeps our recursive logic clean and contained, relying on the consistent behaviour that returning undefined signifies an element or structure should not be present in the final filtered result.

Solution Approach

The solution for filtering an object or array deeply relies on a recursive approach, which is applied via a Depth-First Search (DFS) algorithm. Here is a step-by-step breakdown of the implementation:

• The main function deepFilter defines a recursive helper function dfs that is designed to traverse (obj) and apply the filtering logic at every level.
• DFS Algorithm:
  • Arrays: When encountering an array, the helper function dfs uses .map() to call itself on every element, which ensures that every nested object or array is visited. The .filter() method is then used after the map operation to remove any undefined values that represent elements that did not pass the filter function or became empty. If the resulting array is empty, it should not be included in the filtered output, so it returns undefined.
  • Objects: When dfs finds an object, it iterates over the object's keys with a for...in loop. For each key, it calls itself on the associated value, again ensuring deep traversal. If the returned value for any key is undefined, that key is omitted from the result. If all keys result in undefined, indicating that the whole object should be filtered out or is empty, dfs returns undefined for the entire object.
  • Primitive values: For primitives (non-objects/non-arrays), the provided filter function fn is applied directly. If fn returns false, it indicates the value should be filtered out, and dfs returns undefined. If fn returns true, the value is retained.
• At each recursive step, care is taken not to include empty objects or arrays in the result, achieving the deep filtering aspect of the problem.
• The implementation takes advantage of JavaScript's truthiness semantics, such that an empty array and an empty object both produce a 'falsey' evaluation that simplifies the check for whether to exclude them from the result.
• To check whether an object has any retained keys after filtering, Object.keys(res).length > 0 is used. If no keys remain post-filtering, undefined is returned.

Here is the pseudocode that demonstrates the DFS algorithm:

1function deepFilter(obj, fn):
2    define dfs(data):
3        if data is an array:
4            let res = map each item in data to dfs(item), then filter out undefined
5            return res if it's non-empty, else return undefined
6
7        else if data is an object:
8            let res = {}
9            for each key in data:
10                if own property key in data:
11                    let filteredValue = dfs(data[key])
12                    if filteredValue is not undefined:
13                        res[key] = filteredValue
14            return res if it has keys, else return undefined
15
16        else:
17            return data if fn(data) is true, else return undefined
18
19    return dfs(obj)

The deepFilter function then simply calls the dfs helper function with the original obj and returns whatever the helper function returns.

By encapsulating the filtering logic within the dfs function, the solution elegantly deals with the complexity of deep filtering and adheres to the requirement of pruning empty arrays and objects, thus providing a comprehensive and efficient method to deep filter data structures in JavaScript.

Example Walkthrough

Let's use a small example to illustrate the solution approach with a hypothetical object and a simple filter function that retains values which are odd numbers.

Consider the following object with nested arrays and objects:

1let obj = {
2  a: 1,
3  b: [2, 3, { x: 4, y: 5 }],
4  c: {
5    inner: 6,
6    another: [7, 8, 9]
7  }
8};

And a filter function:

1function isOdd(value) {
2  if (typeof value === 'number') {
3    return value % 2 !== 0; // Check for odd numbers
4  }
5  return true; // Non-number values are passed through
6}

We apply the deepFilter function to this object.

1. deepFilter starts by calling dfs(obj).

2. The dfs function sees that obj is an object, and it iterates over each of its keys (a, b, c).

   • For key a, since it is a number, the filter isOdd is applied, and the value 1 is retained as it is odd.
   • For key b, it finds an array and maps each element through dfs.
     • The number 2 is removed as it is even.
     • The number 3 is kept as it is odd.
     • The object { x: 4, y: 5 } is processed:
       • The key x is paired with 4, which is filtered out as it is even.
       • The key y is paired with 5, which is kept.
     • After processing, the array for key b looks like [3, { y: 5 }].
   • For key c, it encounters another object.
     • The key inner with value 6 is filtered out as even.
     • The key another has an array [7, 8, 9], which, after processing, becomes [7, 9] as 8 is filtered out.

3. After dfs processes all keys, the original obj is transformed into:

1{
2  a: 1,
3  b: [3, { y: 5 }],
4  c: {
5    another: [7, 9]
6  }
7}

4. Note that any keys that were paired with even numbers have been removed from the resulting object and array, and inner, which was an object key with an even number, resulted in the key itself being removed since it became empty after filtering.

5. The deepFilter function then returns this filtered object. If all values inside obj had been filtered out, it would have returned undefined.

Through the recursive nature of dfs, the deepFilter function successfully drills down into nested data structures and applies the provided filter function, while also maintaining the integrity of the original structure by only removing entries that don't pass the filter or pruning empty arrays/objects that result from the filtering process.

Solution Implementation

Time and Space Complexity

The code defines a function deepFilter that takes an object as input and applies a given predicate function fn to filter its values, including those deeply nested inside other objects or arrays. The function is implemented using DFS (Depth-First Search) recursion.

Time Complexity

The time complexity of the deepFilter function mainly depends on the number of elements in the input object, including all nested objects and arrays. It applies the fn predicate to every element and also spends time on constructing new arrays or objects when a condition matches.

• For every non-object and non-array element, it simply applies the fn predicate, which happens once for each such element in the input object. Let's denote the number of all such elements as N.

• For objects and arrays, the function recursively processes each element or property. If M is the total number of elements in all nested arrays and the total number of properties in all nested objects, then in the worst case, the time spent on these structures would also be proportional to M.

Let's sum it up: For each inner structure (either array or object), there is an overhead of iteration and recursive calls. If we consider every element and property is visited exactly once and the recursion applies once per such element, the time complexity can be approximated to O(N + M).

But note that this analysis assumes fn's complexity is O(1); if fn has a higher complexity, it would affect the overall time complexity of deepFilter.

Space Complexity

The space complexity includes the recursive stack space and the space needed for storing the intermediate and final results.

• The recursive stack space would in the worst case be proportional to the depth of the object, let's denote this as D (the maximum nesting depth of arrays/objects).

• The function constructs potentially large intermediate arrays and objects. In the worst case, where none of the elements are filtered out, it would replicate the entire structure of the input object.

Given that it creates new structures rather than modifying them in place, the space complexity in the worst case would be O(N + M) due to the newly constructed arrays and objects. This is in addition to the recursive stack space which adds another O(D).

Combining the two, the worst-case space complexity can be approximately described as O(N + M + D), where N + M represents the size of the newly created structure, and D represents the depth of the recursive calls.