Watch 6 video solutions for Compact Object, a medium level problem. This walkthrough by Learn With Chirag has 1,962 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given an object or array obj, return a compact object.
A compact object is the same as the original object, except with keys containing falsy values removed. This operation applies to the object and any nested objects. Arrays are considered objects where the indices are keys. A value is considered falsy when Boolean(value) returns false.
You may assume the obj is the output of JSON.parse. In other words, it is valid JSON.
Example 1:
Input: obj = [null, 0, false, 1] Output: [1] Explanation: All falsy values have been removed from the array.
Example 2:
Input: obj = {"a": null, "b": [false, 1]}
Output: {"b": [1]}
Explanation: obj["a"] and obj["b"][0] had falsy values and were removed.
Example 3:
Input: obj = [null, 0, 5, [0], [false, 16]] Output: [5, [], [16]] Explanation: obj[0], obj[1], obj[3][0], and obj[4][0] were falsy and removed.
Constraints:
obj is a valid JSON object2 <= JSON.stringify(obj).length <= 106Problem Overview: You receive a nested JavaScript object or array. The goal is to remove every falsy value (false, null, 0, "", undefined, NaN) while keeping the original structure of the data. Arrays should keep element order, and objects should retain keys whose values remain truthy after processing.
Approach 1: Recursive Depth-First Search (O(n) time, O(h) space)
This approach walks through the structure using recursion. For arrays, iterate through each element and recursively compact it if the element is an object or array. Only push the result into the new array if it evaluates to truthy. For objects, iterate over keys using a loop, recursively compact nested structures, and assign the value only when it remains truthy. Each value is visited exactly once, giving O(n) time complexity where n is the total number of elements and properties. The recursion stack requires O(h) space where h is the maximum nesting depth.
The key insight is that objects and arrays must be processed before checking truthiness. A nested object might contain falsy values that need removal before deciding whether its result should stay in the parent structure. Recursive traversal naturally handles arbitrarily deep nesting and keeps the implementation compact and readable.
Approach 2: Iterative Depth-First Search using a Stack (O(n) time, O(n) space)
An iterative solution replaces recursion with an explicit stack, following the same traversal pattern used in depth-first search. Push the root object or array onto the stack. While the stack is not empty, pop a node, inspect its properties or elements, and process children. For nested arrays or objects, push them onto the stack so they can be compacted later. Falsy primitive values are skipped, while truthy values are preserved.
This version is useful when recursion depth might become large. Instead of relying on the call stack, it uses a manually managed stack structure. Time complexity remains O(n) because each element or property is processed once. Space complexity can reach O(n) in the worst case if many nested objects are waiting on the stack.
Recommended for interviews: The recursive DFS approach is usually what interviewers expect. It shows you understand recursive traversal of nested data structures and can reason about base cases and structure preservation. Mentioning the iterative stack alternative demonstrates deeper understanding of DFS mechanics and how to avoid recursion limits in production systems.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Depth-First Search | O(n) | O(h) | Best general solution for nested objects or arrays when recursion depth is manageable |
| Iterative DFS using Stack | O(n) | O(n) | Useful when avoiding recursion limits or when explicit stack control is preferred |