Deep Object Filter

Problem Statement

In this task, you are given an object or an array obj and a function fn. Your goal is to return a filtered version of obj, referred to as filteredObject. The deepFilter function should deeply traverse obj, applying fn to each value. It should remove any properties or entries where fn returns false. Additionally, after performing these removals, any resulting empty objects or arrays should also be removed. If the final filteredObject is completely empty, indicating that there is no valid data left after the filtering, then deepFilter should return undefined.

Examples

Example 1

Input:

obj = [-5, -4, -3, -2, -1, 0, 1],
fn = (x) => x > 0

Output:

[1]

Explanation:

All values that were not greater than 0 were removed.

Example 2

Input:

obj = {"a": 1, "b": "2", "c": 3, "d": "4", "e": 5, "f": 6, "g": {"a": 1}},
fn = (x) => typeof x === "string"

Output:

{"b":"2","d":"4"}

Explanation:

All keys with values that were not a string were removed. When the object keys were removed during the filtering process, any resulting empty objects were also removed.

Example 3

Input:

obj = [-1, [-1, -1, 5, -1, 10], -1, [-1], [-5]],
fn = (x) => x > 0

Output:

[[5,10]]

Explanation:

All values that were not greater than 0 were removed. When the values were removed during the filtering process, any resulting empty arrays were also removed.

Example 4

Input:

obj = [[[[5]]]],
fn = (x) => Array.isArray(x)

Output:

undefined

Constraints

• fn is a function that returns a boolean value
• obj is a valid JSON object or array
• 2 <= JSON.stringify(obj).length <= 105

Approach and Intuition

The essential aspect of the deepFilter function is its ability to recursively process both arrays and objects, which requires a thorough and effective traversal method:

1. Initialize the filteredObject. If obj is an array, start with an empty array; if it's an object, start with an empty object.
2. Traverse each entry in obj. If it's a nested object or array, recursively apply deepFilter. If it's a primitive value, apply the function fn:
   • If fn returns true, retain the value in the filteredObject.
   • If fn returns false, skip adding this value to filteredObject.
3. After processing all entries:
   • If dealing with an object, remove any properties that lead to empty objects.
   • If dealing with an array, remove any elements that are empty arrays or have been reduced to nothing.
4. Finally, check if filteredObject is empty after all cleanup. If it is, return undefined; otherwise, return the filteredObject.

Example Walkthroughs:

Example 1: Filtering Positive Numbers in Array

• Start with an array.
• Apply fn to each number in the array. Here, fn = (x) => x > 0.
• Only the positive number 1 satisfies fn, so the output array is [1].

Example 2: Filtering String Values in Object

• Start with an object.
• Apply fn to each value. Here, fn = (x) => typeof x === "string".
• Only the properties with string values ('2' and '4') remain. Therefore, {"b":"2", "d":"4"} is returned.

Example 3: Nested Arrays Filter

• Begin with a nested array.
• Apply fn to each element recursively. Here, fn = (x) => x > 0.
• Deep filtering results in removing all non-positive numbers and arrays that result empty after filtering. The final filtered array is [[5, 10]].

Example 4: Undefined Return Scenario

• Begin with a deeply nested array: [[[[5]]]].
• None of the elements, except for the external arrays, satisfy fn. Here, fn = (x) => Array.isArray(x) is specifically designed to return undefined.
• All levels ultimately filter out, leading to undefined since no direct numeric value exists to satisfy the condition on its own.

This approach to deep filtering emphasizes the importance of recursive function design and effectively handling nested data structures, ensuring that all elements are correctly assessed and any residual empty structures are pruned accordingly.

Solutions

var filteredDeepCopy = function(inputObj, filterFunc) {
  function recursiveSearch(currentElement) {
    if(currentElement === null) {
      if(filterFunc(currentElement)) return currentElement;
      return undefined;
    }
    if(typeof currentElement !== 'object') {
      if(filterFunc(currentElement)) return currentElement;
      return undefined;
    }

    if(Array.isArray(currentElement)) {
      const resultArray = [];

      for(let index = 0; index < currentElement.length; index++) {
        const element = currentElement[index];
        const filteredResult = recursiveSearch(element);

        if(filteredResult !== undefined) {
          resultArray.push(filteredResult);
        }
      }

      if(resultArray.length === 0) {
        return undefined;
      }

      return resultArray;
    }

    const resultObject = {};
    let hasValidProperty = false;

    for(const property in currentElement) {
      const filteredResult = recursiveSearch(currentElement[property]);
      if(filteredResult !== undefined) {
        resultObject[property] = filteredResult;
        hasValidProperty = true;
      }
    }

    if(!hasValidProperty) return undefined;

    return resultObject;
  }

  return recursiveSearch(inputObj);
}