Compact Object - Solution & Explanation
Problem Statement
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:
objis a valid JSON object2 <= JSON.stringify(obj).length <= 106
Approach Overview
Problem 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 1: Recursive Depth-First Search
This approach leverages a recursive depth-first search to traverse the object or array. We remove any keys or indices associated with falsy values during traversal. The recursion ensures nested structures are appropriately compacted.
In C, handling JSON-like objects requires defining detailed structures for objects and arrays. This fragment outlines a basic setup for type checking and falsy determination. Complete recursive traversal and compaction logic would be needed for a working solution.
Complexity
The time complexity is O(n), where n is the total number of elements (including nested) in the object. The space complexity also depends on the depth of recursion, primarily O(d) where d is the depth of nested objects.
Approach 2: Iterative Depth-First Search using a Stack
Instead of recursion, this approach uses an iterative depth-first search pattern using a stack to manage the traversal. It ensures that nested structures are compacted by maintaining traversal state without deep recursion, mitigating possible stack overflows in languages with limited recursion depth control.
This Python implementation uses an explicit stack to perform an iterative deep-first traversal on the JSON structure. By handling keys/indices dynamically, the solution effectively compacts nested constructs without recursive function calls.
Code
Python
JavaScript
Complexity
Time Complexity: O(n) as each element is processed once; Space Complexity: O(n) where n encapsulates all elements since the entire structure can potentially end up in the stack.
Approach 3: Recursion
If obj is not an object or is null, the function will return it as is, because there's no need to check for keys in non-object values.
If obj is an array, it will use obj.filter(Boolean) to filter out falsy values (like null, undefined, false, 0, ""), then use map(compactObject) to recursively call compactObject on each element. This ensures that nested arrays are also compacted.
If obj is an object, it will create a new empty object compactedObj. It will iterate over all keys of obj, and for each key, it will recursively call compactObject on the corresponding value, then store the result in the value variable. If the value is truthy (i.e., not falsy), it will assign it to the compacted object with the corresponding key.
The time complexity is O(n), and the space complexity is O(n).
Code
TypeScript
JavaScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Recursive Depth-First Search | The time complexity is O(n), where n is the total number of elements (including nested) in the object. The space complexity also depends on the depth of recursion, primarily O(d) where d is the depth of nested objects. |
| Iterative Depth-First Search using a Stack | Time Complexity: O(n) as each element is processed once; Space Complexity: O(n) where n encapsulates all elements since the entire structure can potentially end up in the stack. |
| Recursion | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Compact Object | Leetcode 2705 | JSON | 30 Days of JavaScript #javascript #leetcode • Learn With Chirag • 2,033 views views
Watch 4 more video solutions →Frequently Asked Questions
Is Compact Object easy or hard?
How to solve Compact Object in O(n)?
What is the best approach for Compact Object?
What data structure is used in Compact Object?
What is the time complexity of Compact Object?
Compact Object Python or Java solution approach
Is Compact Object asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Compact Object with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor