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:

function deepFilter(obj, fn):
    define dfs(data):
        if data is an array:
            let res = map each item in data to dfs(item), then filter out undefined
            return res if it's non-empty, else return undefined

        else if data is an object:
            let res = {}
            for each key in data:
                if own property key in data:
                    let filteredValue = dfs(data[key])
                    if filteredValue is not undefined:
                        res[key] = filteredValue
            return res if it has keys, else return undefined

        else:
            return data if fn(data) is true, else return undefined

    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.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

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:

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

And a filter function:

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

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:

{
  a: 1,
  b: [3, { y: 5 }],
  c: {
    another: [7, 9]
  }
}
  1. 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.

  2. 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

1def deep_filter(obj, predicate):
2    """
3    Recursively filters an object by applying the given predicate function to all
4    non-dictionary and non-list elements. If a property in an object or an element in
5    a list doesn't pass the predicate function, it is removed from the returned object.
6
7    :param obj: The dictionary to be recursively filtered.
8    :param predicate: The predicate function to apply to each element.
9    :return: A dictionary containing only the elements for which the predicate function returns True.
10    """
11  
12    def depth_first_search(data):
13        """
14        Internal helper function that performs depth-first search on the data structure,
15        applying the predicate function at the non-dictionary and non-list level.
16        """
17        # If data is a list, process each item recursively, and filter out undefined
18        if isinstance(data, list):
19            result = list(filter(lambda item: item is not None, [depth_first_search(item) for item in data]))
20            return result if len(result) > 0 else None
21      
22        # If data is a dictionary, process each key-value pair recursively
23        if isinstance(data, dict):
24            result = {}
25            for key, value in data.items():
26                filtered_value = depth_first_search(value)
27                # Include the key-value pair in the result if the value is not undefined
28                if filtered_value is not None:
29                    result[key] = filtered_value
30            return result if len(result) > 0 else None
31      
32        # For non-dictionary, non-list elements, apply the predicate function
33        return data if predicate(data) else None
34  
35    # Start the recursive filtering process
36    return depth_first_search(obj)
37
1import java.util.ArrayList;
2import java.util.HashMap;
3import java.util.List;
4import java.util.Map;
5
6public class DeepFilter {
7
8    /**
9     * Recursively filters an object by applying the given predicate function to all
10     * non-Map and non-List elements. If a property in a Map or an element in a List doesn't
11     * pass the predicate function, it is removed from the returned Map.
12     *
13     * @param obj       The object to be recursively filtered.
14     * @param predicate The predicate function to apply to each element.
15     * @return A Map containing only the elements for which the predicate function returns true.
16     */
17    public static Map<String, Object> deepFilter(Map<String, Object> obj, Predicate predicate) {
18        return (Map<String, Object>) depthFirstSearch(obj, predicate);
19    }
20
21    /**
22     * Internal function to perform depth-first search for filtering.
23     *
24     * @param data      The data to apply the filter on, can be a List, Map, or other Objects.
25     * @param predicate The predicate function to use for filtering.
26     * @return A filtered data, can be a List, Map or Object based on the input data.
27     */
28    private static Object depthFirstSearch(Object data, Predicate predicate) {
29        if (data instanceof List) {
30            List<?> originalList = (List<?>) data;
31            List<Object> resultList = new ArrayList<>();
32            for (Object item : originalList) {
33                Object result = depthFirstSearch(item, predicate);
34                if (result != null) {
35                    resultList.add(result);
36                }
37            }
38            return resultList.isEmpty() ? null : resultList;
39        }
40        else if (data instanceof Map) {
41            Map<?, ?> originalMap = (Map<?, ?>) data;
42            Map<String, Object> resultMap = new HashMap<>();
43            for (Map.Entry<?, ?> entry : originalMap.entrySet()) {
44                Object filteredValue = depthFirstSearch(entry.getValue(), predicate);
45                if (filteredValue != null) {
46                    resultMap.put(entry.getKey().toString(), filteredValue);
47                }
48            }
49            return resultMap.isEmpty() ? null : resultMap;
50        }
51        else {
52            // Apply predicate function to non-Map, non-List elements.
53            return predicate.test(data) ? data : null;
54        }
55    }
56
57    /**
58     * Functional interface for predicate logic to be applied on each element.
59     */
60    @FunctionalInterface
61    public interface Predicate {
62        boolean test(Object value);
63    }
64}
65
1#include <vector>
2#include <map>
3#include <string>
4#include <functional>
5#include <memory>
6#include <type_traits>
7
8// Alias for a JSON-like structure in C++ consisting of nested maps and vectors.
9using JsonValue = std::shared_ptr<std::variant<
10    std::string,            // String value
11    int,                    // Integer value
12    bool,                   // Boolean value
13    std::vector<JsonValue>, // Array of JsonValue
14    std::map<std::string, JsonValue> // Object with string keys and JsonValue
15>>;
16
17/**
18 * Recursively filters a JSON-like object by applying the given predicate function to all 
19 * non-object and non-array elements. If a property in an object or an element in an array 
20 * does not pass the predicate function, it is removed from the returned object.
21 *
22 * @param value The JSON-like object to be recursively filtered.
23 * @param predicate The predicate function to apply to each element.
24 * @returns A JsonValue containing only the elements for which the predicate function returns true.
25 */
26JsonValue DeepFilter(const JsonValue& value, const std::function<bool(const JsonValue&)>& predicate) {
27    // Helper function to perform depth-first traversal and filtering.
28    std::function<JsonValue(const JsonValue&)> depthFirstSearch = [&](const JsonValue& current) -> JsonValue {
29        // Check for array type and perform recursive filtering.
30        if (auto pArray = std::get_if<std::vector<JsonValue>>(&*current)) {
31            std::vector<JsonValue> result;
32            for (const auto& item : *pArray) {
33                auto filteredItem = depthFirstSearch(item);
34                if (filteredItem != nullptr) {
35                    result.push_back(filteredItem);
36                }
37            }
38            if (!result.empty()) {
39                return std::make_shared<std::variant<std::string, int, bool, std::vector<JsonValue>, std::map<std::string, JsonValue>>>(result);
40            }
41        }
42
43        // Check for object type and perform recursive filtering.
44        else if (auto pObject = std::get_if<std::map<std::string, JsonValue>>(&*current)) {
45            std::map<std::string, JsonValue> result;
46            for (const auto& pair : *pObject) {
47                auto filteredValue = depthFirstSearch(pair.second);
48                if (filteredValue != nullptr) {
49                    result[pair.first] = filteredValue;
50                }
51            }
52            if (!result.empty()) {
53                return std::make_shared<std::variant<std::string, int, bool, std::vector<JsonValue>, std::map<std::string, JsonValue>>>(result);
54            }
55        }
56
57        // Apply the predicate function to non-array, non-object elements.
58        else if (predicate(current)) {
59            return current;
60        }
61
62        // Return nullptr if the current value doesn't satisfy the predicate.
63        return nullptr;
64    };
65
66    // Start the recursive filtering process.
67    return depthFirstSearch(value);
68}
69
1/**
2 * Recursively filters an object by applying the given predicate function to all 
3 * non-object and non-array elements. If a property in an object or an element in 
4 * an array doesn't pass the predicate function, it is removed from the returned object.
5 *
6 * @param obj The object to be recursively filtered.
7 * @param predicate The predicate function to apply to each element.
8 * @returns An object containing only the elements for which the predicate function returns true.
9 */
10function deepFilter(obj: Record<string, any>, predicate: (value: any) => boolean): Record<string, any> | undefined {
11  // Internal function to perform depth-first search.
12  function depthFirstSearch(data: any): any {
13    // Handle the case where data is an array.
14    if (Array.isArray(data)) {
15      const result = data.map(depthFirstSearch).filter((item: any) => item !== undefined);
16      return result.length > 0 ? result : undefined;
17    }
18  
19    // Handle the case where data is an object.
20    if (typeof data === 'object' && data !== null) {
21      const result: Record<string, any> = {};
22      for (const key in data) {
23        if (Object.prototype.hasOwnProperty.call(data, key)) {
24          const filteredValue = depthFirstSearch(data[key]);
25          if (filteredValue !== undefined) {
26            result[key] = filteredValue;
27          }
28        }
29      }
30      return Object.keys(result).length > 0 ? result : undefined;
31    }
32  
33    // Apply predicate function to non-object, non-array elements.
34    return predicate(data) ? data : undefined;
35  }
36
37  // Start the recursive filtering process.
38  return depthFirstSearch(obj);
39}
40

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.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which data structure is used to implement recursion?


Recommended Readings

Want a Structured Path to Master System Design Too? Donā€™t Miss This!


Load More