Skip to main content
Talentd

Deep Object Filter - Solution & Explanation

MediumPremiumFree on FleetCode4 min read
Practice this problem

Problem Statement

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.

 

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 Overview

Problem Overview: Deep Object Filter asks you to recursively process a nested structure (objects and arrays) and remove values that do not satisfy a predicate function fn. Primitive values are checked directly with the predicate, while arrays and objects must be traversed deeply so that only valid elements remain in the final structure.

Approach 1: Recursive DFS Traversal (O(n) time, O(h) space)

The most natural solution treats the input as a tree of values and performs a depth‑first traversal. If the current value is an array, iterate through each element, recursively filter it, and keep only the results that are still valid. If the value is an object, iterate through its keys and recursively filter each property, deleting keys whose filtered result is invalid. For primitives, simply evaluate fn(value) and return the value only when the predicate passes. This approach processes each node exactly once, giving O(n) time complexity where n is the number of values in the structure, and O(h) recursion stack space where h is the maximum nesting depth. This pattern is common in problems involving recursion and nested data traversal.

Approach 2: Iterative Stack Traversal (O(n) time, O(n) space)

You can replace recursion with an explicit stack to simulate depth‑first traversal. Push the root node onto a stack along with a reference to its parent container. While the stack is not empty, pop a node, inspect its type, and process arrays or objects by pushing their children back onto the stack. After evaluating children, remove entries that fail the predicate or become empty after filtering. This avoids recursion depth limits and can be easier to control in environments where stack overflow is a concern. The algorithm still visits every element once, resulting in O(n) time complexity and up to O(n) auxiliary space for the stack and intermediate references. The traversal pattern is similar to iterative depth-first search used for tree structures.

Recommended for interviews: The recursive DFS approach is what most interviewers expect. It shows you understand how to traverse nested data structures and apply transformations during recursion. Mentioning the iterative stack variant demonstrates deeper understanding of traversal mechanics and recursion limits. If the discussion touches JavaScript behavior, highlighting how arrays and objects are processed differently in JavaScript can also strengthen your explanation.

Solution

Code

TypeScript

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Recursive DFS TraversalO(n)O(h)Best general solution for nested arrays/objects when recursion depth is manageable
Iterative Stack TraversalO(n)O(n)When avoiding recursion limits or when explicit traversal control is needed

Video Solution

LeetCode was HARD until I Learned these 15 Patterns • Ashish Pratap Singh • 1,002,273 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Deep Object Filter easy or hard?
Deep Object Filter is generally considered a medium-level problem. The challenge comes from correctly handling both arrays and objects while recursively removing invalid values and empty containers. Strong understanding of recursion and nested data structures makes it straightforward.
Deep Object Filter Python/Java solution
The same algorithm works in Python or Java by recursively traversing dictionaries/maps and lists. Evaluate primitives with the predicate and rebuild containers with only valid children. Regardless of language, the complexity remains O(n) time with O(h) recursion depth.
How to solve Deep Object Filter in O(n)?
Traverse the structure using depth-first search. For arrays, iterate through elements and recursively filter them; for objects, iterate through keys and recursively process values. Primitive values are kept only if the predicate function returns true. Since each node is visited once, the total runtime is O(n).
What is the best approach for Deep Object Filter?
Recursive depth-first traversal is the most effective approach. You recursively inspect arrays and objects, apply the predicate to primitive values, and remove elements that fail the condition. Each node is processed once, giving O(n) time complexity and O(h) space for recursion depth.
Is Deep Object Filter asked at Google/Amazon/Meta?
Problems involving recursive filtering of nested objects appear in frontend and JavaScript-heavy interviews at large tech companies. Variants of this question test recursion, DFS traversal, and understanding of object vs array handling in JavaScript-style data structures.
What data structure is used in Deep Object Filter?
The input structure behaves like a tree composed of objects and arrays. The solution typically uses recursion or a stack to perform depth-first traversal. During traversal, arrays and hash-map style objects are reconstructed with only valid elements.
What is the time complexity of Deep Object Filter?
The optimal solution runs in O(n) time where n is the total number of values across the entire nested structure. Every array element, object property, and primitive value is visited exactly once during traversal. Space complexity is O(h) for recursion depth or O(n) when using an explicit stack.

Ready to solve this problem?

Practice Deep Object Filter with our built-in code editor and test cases.

Practice on FleetCode