LeetCode 2823 - Deep Object Filter

This problem asks us to recursively filter a JSON-like structure that may contain nested objects and arrays. The input consists of two parts: - obj, which can be either: - a primitive value, - an array, - or an object containing nested arrays and objects - fn, a predicate…

leetcodemedium

LeetCode Problem 2823

Difficulty: 🟡 Medium
Topics: —

Solution

Problem Understanding

This problem asks us to recursively filter a JSON-like structure that may contain nested objects and arrays. The input consists of two parts:

  • obj, which can be either:

  • a primitive value,

  • an array,

  • or an object containing nested arrays and objects

  • fn, a predicate function that returns either true or false

The goal is to create a new deeply filtered version of the structure. Every primitive value in the structure is tested against fn. If the function returns true, the value remains. If it returns false, the value is removed.

The important detail is that filtering must happen recursively. This means:

  • Arrays must be traversed element by element.
  • Objects must be traversed key by key.
  • Nested arrays and objects must also be processed recursively.

After filtering child elements, we must also remove any empty containers that remain. For example:

  • An empty array [] should be discarded.
  • An empty object {} should also be discarded.

If the entire structure becomes empty after filtering, we return undefined.

The problem guarantees that the input is valid JSON data. That means we only need to deal with:

  • objects,
  • arrays,
  • numbers,
  • strings,
  • booleans,
  • and null.

The constraint JSON.stringify(obj).length <= 10^5 tells us the structure can become fairly large. A naive approach involving repeated copying or multiple full traversals could become inefficient. We need a solution that processes the structure efficiently in a single recursive traversal.

Several edge cases are especially important:

  • Arrays that become empty after filtering.
  • Objects whose nested children all disappear.
  • Primitive root values.
  • Deeply nested structures.
  • Cases where the predicate matches arrays or objects themselves.
  • Returning undefined correctly when nothing survives.

One subtle point is that arrays and objects themselves are not directly tested with fn during traversal unless they are leaf values. Instead, we recursively process their contents and decide whether the container survives based on whether anything remains inside.

Approaches

Brute Force Approach

A brute-force strategy would repeatedly traverse the structure and rebuild intermediate results multiple times.

For example, we could:

  1. Flatten the entire structure into paths and values.
  2. Evaluate every primitive against the predicate.
  3. Reconstruct the structure afterward.
  4. Perform additional cleanup passes to remove empty arrays and objects.

This approach works because every value is eventually evaluated and reconstructed correctly. However, reconstruction becomes complicated, especially for deeply nested arrays and objects. Additionally, multiple passes over the data significantly increase runtime and memory usage.

The brute-force solution is inefficient because:

  • It may traverse the structure several times.
  • It requires storing intermediate representations.
  • Reconstruction logic becomes unnecessarily complex.

Optimal Approach

The key insight is that filtering and cleanup can happen simultaneously during a single depth-first traversal.

Instead of processing the structure in separate phases, we recursively process each node and immediately decide:

  • whether the filtered result should survive,
  • or whether it should disappear entirely.

The recursive structure naturally mirrors the nested JSON structure:

  • For arrays:

  • recursively filter each element,

  • keep only surviving elements,

  • discard the array if it becomes empty.

  • For objects:

  • recursively filter each property,

  • keep only surviving properties,

  • discard the object if it becomes empty.

  • For primitive values:

  • directly evaluate them with fn.

This produces a clean and elegant recursive solution with optimal efficiency.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n) Multiple traversals and reconstruction passes
Optimal O(n) O(h) Single DFS traversal, where h is recursion depth

Algorithm Walkthrough

  1. Define a recursive helper function that processes one value at a time.

This helper will return:

  • the filtered structure if something survives,
  • or undefined if the value should be removed.
  1. Check whether the current value is an array.

If it is:

  • create a new result array,
  • recursively process each element,
  • append only elements whose recursive result is not undefined.

After processing:

  • if the result array is empty, return undefined,
  • otherwise return the filtered array.
  1. Check whether the current value is an object.

We must ensure:

  • the value is not null,
  • and it is not an array.

If it is an object:

  • create a new result object,
  • recursively process every property value,
  • keep only properties whose recursive result is not undefined.

After processing:

  • if the object has no keys remaining, return undefined,
  • otherwise return the filtered object.
  1. Handle primitive values.

For numbers, strings, booleans, or null:

  • evaluate fn(value),
  • if true, return the value,
  • otherwise return undefined.
  1. Start recursion from the root object.

The recursive helper naturally processes the entire structure depth-first.

Why it works

The algorithm maintains the invariant that every recursive call returns either:

  • a fully filtered valid subtree,
  • or undefined if no valid data remains.

Because every container only keeps surviving children, all invalid values are removed. Since empty containers are discarded immediately after processing their children, the final structure contains only meaningful filtered data. This guarantees correctness.

Python Solution

from typing import Any

class Solution:
    def deepFilter(self, obj: Any, fn) -> Any:
        def dfs(value):
            # Handle arrays
            if isinstance(value, list):
                filtered_array = []

                for item in value:
                    filtered_item = dfs(item)

                    if filtered_item is not None:
                        filtered_array.append(filtered_item)

                return filtered_array if filtered_array else None

            # Handle objects
            if isinstance(value, dict):
                filtered_object = {}

                for key, val in value.items():
                    filtered_val = dfs(val)

                    if filtered_val is not None:
                        filtered_object[key] = filtered_val

                return filtered_object if filtered_object else None

            # Handle primitive values
            return value if fn(value) else None

        result = dfs(obj)
        return result

The implementation follows the recursive DFS strategy directly.

The helper function dfs processes one node at a time. The function first checks whether the current value is a list. If so, it recursively filters each element and stores only surviving results.

For dictionaries, the logic is similar. Each property is recursively processed, and only surviving properties are copied into the new object.

Primitive values form the base case of recursion. They are directly tested using the predicate function fn.

Returning None serves as Python's equivalent of JavaScript undefined in this implementation. Any recursive result equal to None is treated as removed.

The recursion naturally handles arbitrarily deep nesting while ensuring empty arrays and objects are discarded immediately.

Go Solution

package main

type JSONValue interface{}

func deepFilter(obj JSONValue, fn func(JSONValue) bool) JSONValue {
	var dfs func(JSONValue) JSONValue

	dfs = func(value JSONValue) JSONValue {
		// Handle arrays
		if arr, ok := value.([]JSONValue); ok {
			filtered := make([]JSONValue, 0)

			for _, item := range arr {
				result := dfs(item)

				if result != nil {
					filtered = append(filtered, result)
				}
			}

			if len(filtered) == 0 {
				return nil
			}

			return filtered
		}

		// Handle objects
		if objMap, ok := value.(map[string]JSONValue); ok {
			filtered := make(map[string]JSONValue)

			for key, val := range objMap {
				result := dfs(val)

				if result != nil {
					filtered[key] = result
				}
			}

			if len(filtered) == 0 {
				return nil
			}

			return filtered
		}

		// Handle primitive values
		if fn(value) {
			return value
		}

		return nil
	}

	return dfs(obj)
}

The Go implementation mirrors the Python solution closely, but there are some language-specific differences.

Go does not have a universal JSON type like Python, so we use interface{} through the alias JSONValue.

Arrays are represented as []JSONValue, and objects are represented as map[string]JSONValue.

Go uses nil as the equivalent of JavaScript undefined. Any subtree returning nil is discarded.

Type assertions are required to determine whether a value is an array or object.

Worked Examples

Example 1

Input:

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

Processing steps:

Element fn(x) Keep? Result Array
-5 false No []
-4 false No []
-3 false No []
-2 false No []
-1 false No []
0 false No []
1 true Yes [1]

Final output:

[1]

Example 2

Input:

{
  "a": 1,
  "b": "2",
  "c": 3,
  "d": "4",
  "e": 5,
  "f": 6,
  "g": {"a": 1}
}

Predicate:

typeof x === "string"

Processing:

Key Value Predicate Result Kept?
a 1 false No
b "2" true Yes
c 3 false No
d "4" true Yes
e 5 false No
f 6 false No
g.a 1 false No

The nested object "g" becomes empty:

{}

Therefore it is removed entirely.

Final output:

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

Example 3

Input:

[-1, [-1, -1, 5, -1, 10], -1, [-1], [-5]]

Predicate:

x > 0

Recursive processing:

Substructure Filtered Result
-1 removed
[-1, -1, 5, -1, 10] [5, 10]
-1 removed
[-1] removed entirely
[-5] removed entirely

Final array:

[[5, 10]]

Example 4

Input:

[[[[5]]]]

Predicate:

Array.isArray(x)

The primitive value 5 fails the predicate.

Recursive cleanup:

Level Result
[5] [] -> removed
[[5]] [] -> removed
[[[5]]] [] -> removed
[[[[5]]]] [] -> removed

Final output:

undefined

Complexity Analysis

Measure Complexity Explanation
Time O(n) Every node in the JSON structure is visited exactly once
Space O(h) Recursive call stack depth equals nesting depth

The algorithm performs a single DFS traversal over the entire structure. Every primitive, array, and object is processed once, producing linear runtime.

The extra space comes primarily from recursion depth. In the worst case of deeply nested structures, the recursion stack can grow to height h.

Test Cases

sol = Solution()

# Example 1
assert sol.deepFilter(
    [-5, -4, -3, -2, -1, 0, 1],
    lambda x: x > 0
) == [1]  # filters positive numbers

# Example 2
assert sol.deepFilter(
    {
        "a": 1,
        "b": "2",
        "c": 3,
        "d": "4",
        "e": 5,
        "f": 6,
        "g": {"a": 1}
    },
    lambda x: isinstance(x, str)
) == {
    "b": "2",
    "d": "4"
}  # removes empty nested objects

# Example 3
assert sol.deepFilter(
    [-1, [-1, -1, 5, -1, 10], -1, [-1], [-5]],
    lambda x: x > 0
) == [[5, 10]]  # removes empty arrays recursively

# Example 4
assert sol.deepFilter(
    [[[[5]]]],
    lambda x: isinstance(x, list)
) is None  # entire structure removed

# Empty object after filtering
assert sol.deepFilter(
    {"a": -1},
    lambda x: x > 0
) is None  # empty root object

# Empty array after filtering
assert sol.deepFilter(
    [-1, -2, -3],
    lambda x: x > 0
) is None  # empty root array

# Nested mixed structures
assert sol.deepFilter(
    {
        "a": [1, 2, -1],
        "b": {"x": -5, "y": 10},
        "c": []
    },
    lambda x: x > 0
) == {
    "a": [1, 2],
    "b": {"y": 10}
}  # mixed recursive filtering

# Boolean filtering
assert sol.deepFilter(
    [True, False, True],
    lambda x: x is True
) == [True, True]  # boolean filtering

# Null handling
assert sol.deepFilter(
    {"a": None, "b": 1},
    lambda x: x is not None
) == {"b": 1}  # removes null values

# Deep nesting
assert sol.deepFilter(
    {"a": {"b": {"c": {"d": 5}}}},
    lambda x: x > 0
) == {"a": {"b": {"c": {"d": 5}}}}  # preserves deep structure
Test Why
Positive number filtering Basic array filtering
String filtering in objects Recursive object cleanup
Nested arrays Recursive array removal
Fully removed structure Correct undefined behavior
Empty object Root cleanup correctness
Empty array Array cleanup correctness
Mixed nested structures Combined object and array recursion
Boolean filtering Non-numeric primitives
Null handling Correct primitive processing
Deep nesting Recursion correctness

Edge Cases

One important edge case occurs when every value is filtered out. A naive implementation might return an empty object {} or empty array [], but the problem explicitly requires returning undefined. The recursive cleanup step ensures that empty containers are discarded immediately, eventually propagating undefined all the way to the root.

Another tricky case involves nested empty containers. Consider input like:

[[[-1]]]

If -1 fails the predicate, the innermost array becomes empty and must be removed. That removal causes the parent array to become empty as well, continuing recursively upward. The implementation handles this naturally because each recursive level checks whether its filtered result has length zero.

A third important edge case involves mixed nested structures containing both arrays and objects. For example:

{
  "a": [1, -1],
  "b": {"x": -5}
}

After filtering:

  • "a" becomes [1]
  • "b" becomes empty and must be removed

The implementation correctly treats arrays and objects independently while applying the same recursive cleanup principle to both.

Finally, primitive root values deserve attention. Although most examples use arrays or objects, the root itself could theoretically be a primitive JSON value. The recursive base case handles this correctly by directly evaluating the predicate and returning either the value or undefined.