We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Deep Object Filter

Number: 2912

Difficulty: Medium

Paid? Yes

Companies: N/A

Problem Description

Given a JSON object or array and a filtering function fn that returns a boolean, perform a deep filter operation. Remove any properties or elements for which fn returns false, and also remove any objects or arrays that become empty after filtering. If the entire object or array becomes empty, return undefined.

Key Insights

  • Use recursion to traverse nested objects and arrays.
  • When encountering an object or array, recursively filter each property or element.
  • Apply fn to primitive values (or non-object/array values) to decide if they should be kept.
  • After filtering substructures, if an object or array is empty, treat it as invalid and remove it from the final result.
  • The solution must handle edge cases such as deeply nested empty objects/arrays.

Space and Time Complexity

Time Complexity: O(n), where n is the total number of elements/properties in the input. Space Complexity: O(d), where d is the maximum depth of the nested structures due to recursion.

Solution

We solve the problem using a recursive depth-first search. For each node in the object or array:

  1. If the node is an object or an array, iterate over its keys or indices, recursively call the deep filter on the value, and include the value only if the recursive call returns a defined (non-empty) value.
  2. For other values (non-objects/arrays), apply the filter function fn. If fn returns true, keep the value; otherwise, drop it.
  3. After processing an object or an array, if no valid entries remain, return undefined to indicate the structure is empty.
  4. This approach ensures that by the time we have filtered higher levels, all invalid entries (including empty nested structures) have been removed.

Code Solutions

def deepFilter(obj, fn):
    # Check if the current value is a dictionary.
    if isinstance(obj, dict):
        # Create a new dictionary for filtered results.
        filtered = {}
        for key, value in obj.items():
            # Recursively filter the value.
            filtered_value = deepFilter(value, fn)
            if filtered_value is not None:
                filtered[key] = filtered_value
        # If the filtered dictionary is not empty, return it; otherwise, return None.
        return filtered if filtered else None
    
    # Check if the current value is a list.
    elif isinstance(obj, list):
        # Create a new list for filtered elements.
        filtered = []
        for value in obj:
            filtered_value = deepFilter(value, fn)
            if filtered_value is not None:
                filtered.append(filtered_value)
        # Return the list if not empty; otherwise, return None.
        return filtered if filtered else None
    
    else:
        # For primitive values, apply the filter function.
        return obj if fn(obj) else None

# Example usage:
# obj = [-5, -4, -3, -2, -1, 0, 1]
# fn = lambda x: x > 0
# print(deepFilter(obj, fn))  # Output should be [1]
← Back to All Questions