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 <= 106This 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.
C++
Java
Python
C#
JavaScript
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.
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.
JavaScript
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 | 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. |
Design Min Stack - Amazon Interview Question - Leetcode 155 - Python • NeetCode • 255,380 views views
Watch 9 more video solutions →Practice Compact Object with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor