Problem Description

This problem asks you to implement a deepFilter function that recursively filters an object or array based on a given filter function fn.

The function takes two parameters:

• obj: An object or array to be filtered
• fn: A filter function that returns true or false for primitive values

The filtering process works as follows:

1. For primitive values (numbers, strings, booleans, etc.): Apply the filter function fn. If fn returns false, the value should be removed.

2. For arrays: Recursively filter each element. After filtering, if the array becomes empty, it should be removed entirely (return undefined).

3. For objects: Recursively filter each property value. If a property's filtered value becomes undefined, remove that property. If the object becomes empty after filtering, it should be removed entirely (return undefined).

4. Return value: The function returns the filtered object/array, or undefined if the result is completely empty.

The key insight is that this is a deep filter - it doesn't just filter top-level properties, but recursively processes nested structures. Empty containers (objects with no properties or empty arrays) that result from the filtering process are considered invalid and should be removed from the parent structure.

For example, if you have an object like {a: 1, b: {c: 2}} and the filter function only accepts values greater than 5, the entire structure would return undefined because:

• 1 fails the filter
• 2 fails the filter, making {c: 2} become an empty object {}
• The empty object {} is removed
• The top-level object becomes empty and returns undefined

Intuition

The key insight is that we need to process the data structure from the bottom up - we can't know whether a container (object or array) should be kept until we've processed all its contents. This naturally suggests a recursive depth-first search (DFS) approach.

Think about it this way: if we have a nested structure like {a: {b: {c: 1}}}, we need to:

1. First check if 1 passes the filter
2. If it doesn't, {c: 1} becomes empty
3. An empty {} means {b: {}} also becomes empty
4. Finally, {a: {}} becomes empty too

This bottom-up evaluation means we need to recursively process children before deciding what to do with their parent container.

The solution uses a helper function dfs that handles three distinct cases:

1. Base case (primitives): When we hit a primitive value, we simply apply the filter function. This is our recursion termination point - return the value if fn(data) is true, otherwise return undefined.

2. Arrays: Map each element through recursive dfs calls, then filter out any undefined results. If the resulting array is empty, we return undefined to signal that this entire array should be removed from its parent.

3. Objects: Iterate through each key-value pair, recursively process the value, and only keep the key if the processed value isn't undefined. After processing all keys, check if we have any keys left - if not, return undefined.

The pattern of returning undefined to indicate "remove this from parent" is elegant because it works uniformly across all levels of nesting. Each level only needs to check if its child returned undefined to know whether to include it or not.

Solution Approach

The implementation uses a recursive depth-first search (DFS) pattern with a helper function to traverse and filter the data structure.

Main Function Structure:

function deepFilter(obj: Record<string, any>, fn: Function): Record<string, any> | undefined {
    const dfs = (data: any): any => {
        // Helper function logic
    };
    return dfs(obj);
}

The DFS Helper Function Implementation:

The dfs function handles three different data types:

1. Array Processing:

if (Array.isArray(data)) {
    const res = data.map(dfs).filter((item: any) => item !== undefined);
    return res.length > 0 ? res : undefined;
}

• Use map(dfs) to recursively process each element
• Filter out undefined values (elements that didn't pass the filter)
• Return the filtered array if it has elements, otherwise return undefined

2. Object Processing:

if (typeof data === 'object' && data !== null) {
    const res: Record<string, any> = {};
    for (const key in data) {
        if (data.hasOwnProperty(key)) {
            const filteredValue = dfs(data[key]);
            if (filteredValue !== undefined) {
                res[key] = filteredValue;
            }
        }
    }
    return Object.keys(res).length > 0 ? res : undefined;
}

• Create a new empty object res to store filtered results
• Iterate through each property using for...in loop
• Use hasOwnProperty to ensure we only process direct properties
• Recursively filter each property value with dfs(data[key])
• Only add properties whose filtered values are not undefined
• Return the object if it has properties, otherwise return undefined

3. Primitive Value Processing:

return fn(data) ? data : undefined;

• Apply the filter function directly to primitive values
• Return the value if fn(data) is truthy, otherwise return undefined

Key Design Decisions:

• Using undefined as a removal signal: When any level returns undefined, the parent level knows to exclude that value/property
• Bottom-up processing: The recursive nature ensures we process leaf nodes first, then work our way up
• Creating new objects/arrays: Instead of modifying in place, we create new filtered structures, maintaining immutability
• hasOwnProperty check: Ensures we don't accidentally process inherited properties from the prototype chain

The algorithm has a time complexity of O(n) where n is the total number of nodes (including all nested properties and array elements) since we visit each node exactly once.

Example Walkthrough

Let's walk through a concrete example to understand how the deepFilter function works:

Input:

obj = {
  a: 1,
  b: {
    c: 2,
    d: -1,
    e: {
      f: 3
    }
  },
  g: [1, 2, -3, {h: -4}]
}

fn = (val) => val > 0  // Keep only positive numbers

Step-by-step execution:

1. Start with root object - Call dfs(obj)

   • Since it's an object, iterate through each property

2. Process a: 1

   • Call dfs(1) → primitive value
   • Apply filter: fn(1) returns true (1 > 0)
   • Return 1 ✓

3. Process b: {c: 2, d: -1, e: {f: 3}}

   • Call dfs({c: 2, d: -1, e: {f: 3}}) → object, so recurse on each property

   3.1. Process c: 2

   • dfs(2) → fn(2) returns true → keep 2 ✓

   3.2. Process d: -1

   • dfs(-1) → fn(-1) returns false → return undefined ✗

   3.3. Process e: {f: 3}

   • dfs({f: 3}) → object, recurse

   • Process f: 3 → dfs(3) → fn(3) returns true → keep 3 ✓

   • Object {f: 3} has properties, so return {f: 3} ✓

   • After processing all of b's properties: {c: 2, e: {f: 3}} (d is removed)

4. Process g: [1, 2, -3, {h: -4}]

   • Call dfs([1, 2, -3, {h: -4}]) → array, so map each element

   4.1. dfs(1) → fn(1) returns true → 1 ✓

   4.2. dfs(2) → fn(2) returns true → 2 ✓

   4.3. dfs(-3) → fn(-3) returns false → undefined ✗

   4.4. dfs({h: -4}) → object

   • Process h: -4 → dfs(-4) → fn(-4) returns false → undefined ✗

   • Object becomes empty {} → return undefined ✗

   • After mapping: [1, 2, undefined, undefined]

   • After filtering out undefined: [1, 2] ✓

5. Final result:

{
  a: 1,
  b: {
    c: 2,
    e: {
      f: 3
    }
  },
  g: [1, 2]
}

Key observations from this walkthrough:

• Negative values (-1, -3, -4) are filtered out
• The object {h: -4} becomes empty after filtering and is removed entirely from the array
• The property d: -1 is removed from object b
• The recursive nature ensures all nested levels are properly filtered
• Empty containers are automatically removed (like the {h: -4} object)

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the total number of nodes (including all nested values) in the input object/array structure.

The algorithm performs a depth-first traversal of the entire data structure, visiting each node exactly once. For each node:

• If it's an array, we iterate through all elements once using map and filter
• If it's an object, we iterate through all key-value pairs once
• If it's a primitive value, we apply the filter function fn once

Since each node is processed with constant-time operations (aside from the filter function call which we assume is O(1)), and we visit all n nodes exactly once, the overall time complexity is O(n).

Space Complexity: O(d + m) where d is the maximum depth of the nested structure and m is the total number of nodes that pass the filter condition.

The space complexity consists of two components:

1. Recursion call stack: O(d) - The recursive dfs function can go as deep as the maximum nesting level of the input structure
2. Output data structure: O(m) - We create new objects and arrays to store the filtered results, where m represents the number of nodes (including container objects/arrays) that remain after filtering

In the worst case where all elements pass the filter and the structure is deeply nested, this becomes O(d + n). In the best case where no elements pass the filter, only the call stack space O(d) is used since the function returns undefined without creating new data structures.

Common Pitfalls

1. Not Handling None/null Values Correctly

A common mistake is treating None (Python) or null (JavaScript) as objects, which can cause runtime errors when trying to iterate over them.

Problematic Code:

def dfs(data):
    if isinstance(data, list):
        # handle list
    if isinstance(data, dict):  # This will fail for None values!
        # handle dict
    return data if fn(data) else None

Why it fails: In Python, None is not caught by isinstance(data, dict), but in some implementations, developers might forget that primitive checks should handle None explicitly, especially when the filter function might receive None as a valid input.

Solution:

def dfs(data):
    # Check for None explicitly before other type checks
    if data is None:
        return data if fn(data) else None
  
    if isinstance(data, list):
        # handle list
    elif isinstance(data, dict):
        # handle dict
    else:
        # handle other primitives
        return data if fn(data) else None

2. Modifying the Original Object

Another pitfall is accidentally modifying the original object instead of creating a new filtered copy.

Problematic Code:

def dfs(data):
    if isinstance(data, dict):
        for key, value in list(data.items()):  # Still dangerous!
            filtered_value = dfs(value)
            if filtered_value is None:
                del data[key]  # Modifying original!
            else:
                data[key] = filtered_value  # Modifying original!
        return data if len(data) > 0 else None

Why it fails: This modifies the input object in place, which can cause unexpected side effects if the original object is used elsewhere in the code.

Solution: Always create new objects/arrays (as shown in the correct implementation):

if isinstance(data, dict):
    filtered_dict = {}  # Create new dict
    for key, value in data.items():
        filtered_value = dfs(value)
        if filtered_value is not None:
            filtered_dict[key] = filtered_value
    return filtered_dict if len(filtered_dict) > 0 else None

3. Incorrect Handling of Falsy Values

A subtle but critical pitfall is confusing "falsy" values with values that should be filtered out.

Problematic Code:

def dfs(data):
    # ... other cases ...
  
    # Wrong: using falsy check instead of None check
    filtered_value = dfs(value)
    if filtered_value:  # This filters out 0, "", False, [] etc.!
        filtered_dict[key] = filtered_value

Why it fails: Values like 0, "" (empty string), False, or even empty arrays [] are falsy in Python, but they might be valid values that passed the filter function. Using a falsy check would incorrectly remove these values.

Solution: Always explicitly check for None:

filtered_value = dfs(value)
if filtered_value is not None:  # Explicit None check
    filtered_dict[key] = filtered_value

4. Not Preserving Special Object Types

The code might fail to handle special object types like dates, sets, or custom classes properly.

Problematic Code:

def dfs(data):
    if isinstance(data, list):
        # handle list
    elif isinstance(data, dict):
        # handle dict
    else:
        # Treats everything else as primitive
        return data if fn(data) else None

Why it fails: Objects like datetime, set, or custom class instances would be passed directly to the filter function, which might not be the intended behavior.

Solution: Add explicit handling for special types or document the expected behavior:

def dfs(data):
    # Handle special types that should be treated as primitives
    if isinstance(data, (datetime, date, set, frozenset)):
        return data if fn(data) else None
  
    if isinstance(data, list):
        # handle list
    elif isinstance(data, dict):
        # handle dict
    elif hasattr(data, '__dict__'):  # Custom objects
        # Optionally handle custom objects by filtering their attributes
        filtered_obj = dfs(data.__dict__)
        # Additional logic to reconstruct the object
    else:
        return data if fn(data) else None