Problem

Given an object or an array obj and a function fn, return a filtered object or array filteredObject.

Function deepFilter should perform a deep filter operation on the obj. The deep filter operation should remove properties for which the output of the filter function fn is false, as well as any empty objects or arrays that remain after the keys have been removed.

If the deep filter operation results in an empty object or array, with no remaining properties, deepFilter should return undefined to indicate that there is no valid data left in the filteredObject.

Examples

Example 1:

1
2
3
4
5

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:

1
2
3
4
5

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:

1
2
3
4
5

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:

1
2
3
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 <= 10^5

Solution

Method 1 – Recursive Deep Filter

Intuition

To deeply filter an object or array, we recursively apply the filter function to all values. If a value is an object or array, we filter its children. If a value passes the filter, we keep it. If a container (object/array) becomes empty after filtering, we remove it (return undefined).

Approach

  1. If the value is an array:
    • Recursively filter each element.
    • Remove elements that become undefined.
    • If the result is empty, return undefined.
    • Otherwise, return the filtered array.
  2. If the value is an object (but not an array):
    • Recursively filter each property value.
    • Remove properties that become undefined.
    • If the result is empty, return undefined.
    • Otherwise, return the filtered object.
  3. For primitives, return the value if it passes the filter, else return undefined.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
    deepFilter(obj, fn) {
        if (Array.isArray(obj)) {
            const ans = [];
            for (const v of obj) {
                const res = this.deepFilter(v, fn);
                if (res !== undefined) ans.push(res);
            }
            return ans.length ? ans : undefined;
        }
        if (this.isObject(obj)) {
            const ans = {};
            for (const k in obj) {
                if (Object.prototype.hasOwnProperty.call(obj, k)) {
                    const res = this.deepFilter(obj[k], fn);
                    if (res !== undefined) ans[k] = res;
                }
            }
            return Object.keys(ans).length ? ans : undefined;
        }
        return fn(obj) ? obj : undefined;
    }
    isObject(x) {
        return typeof x === 'object' && x !== null && !Array.isArray(x);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
    deepFilter(obj: any, fn: (x: any) => boolean): any {
        if (Array.isArray(obj)) {
            const ans: any[] = [];
            for (const v of obj) {
                const res = this.deepFilter(v, fn);
                if (res !== undefined) ans.push(res);
            }
            return ans.length ? ans : undefined;
        }
        if (this.isObject(obj)) {
            const ans: Record<string, any> = {};
            for (const k in obj) {
                if (Object.prototype.hasOwnProperty.call(obj, k)) {
                    const res = this.deepFilter(obj[k], fn);
                    if (res !== undefined) ans[k] = res;
                }
            }
            return Object.keys(ans).length ? ans : undefined;
        }
        return fn(obj) ? obj : undefined;
    }
    isObject(x: any): boolean {
        return typeof x === 'object' && x !== null && !Array.isArray(x);
    }
}

Complexity

  • ⏰ Time complexity: O(N), where N is the total number of values in the nested structure, since each value is visited once.
  • 🧺 Space complexity: O(D), where D is the maximum depth of the nested structure, due to recursion stack.