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, usingmap
. Then, we filter out anyundefined
values (indicating filtered or empty elements). If the resulting array is empty, we returnundefined
. - 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 notundefined
after filtering. If the resulting object has no keys, we returnundefined
. - For other data types (primitives like numbers or strings), we apply the filter function
fn
directly. If the filter function returnsfalse
, we returnundefined
. - At the top level, we simply call our
dfs
function on the inputobj
and return the result, which could beundefined
if the originalobj
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 functiondfs
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 anyundefined
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 returnsundefined
. - Objects: When
dfs
finds an object, it iterates over the object's keys with afor...in
loop. For each key, it calls itself on the associated value, again ensuring deep traversal. If the returned value for any key isundefined
, that key is omitted from the result. If all keys result inundefined
, indicating that the whole object should be filtered out or is empty,dfs
returnsundefined
for the entire object. - Primitive values: For primitives (non-objects/non-arrays), the provided filter function
fn
is applied directly. Iffn
returnsfalse
, it indicates the value should be filtered out, anddfs
returnsundefined
. Iffn
returnstrue
, the value is retained.
- Arrays: When encountering an array, the helper function
- 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 EvaluatorExample 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.
-
deepFilter
starts by callingdfs(obj)
. -
The
dfs
function sees thatobj
is an object, and it iterates over each of its keys (a
,b
,c
).- For key
a
, since it is a number, the filterisOdd
is applied, and the value1
is retained as it is odd. - For key
b
, it finds an array and maps each element throughdfs
.- 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 with4
, which is filtered out as it is even. - The key
y
is paired with5
, which is kept.
- The key
- After processing, the array for key
b
looks like[3, { y: 5 }]
.
- The number
- For key
c
, it encounters another object.- The key
inner
with value6
is filtered out as even. - The key
another
has an array[7, 8, 9]
, which, after processing, becomes[7, 9]
as8
is filtered out.
- The key
- For key
-
After
dfs
processes all keys, the originalobj
is transformed into:
{ a: 1, b: [3, { y: 5 }], c: { another: [7, 9] } }
-
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. -
The
deepFilter
function then returns this filtered object. If all values insideobj
had been filtered out, it would have returnedundefined
.
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 asN
. -
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 toM
.
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.
Which data structure is used to implement recursion?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!