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 <= 106The key idea behind solving #2705 Compact Object is to recursively traverse the given structure and remove all falsy values such as false, 0, null, "", undefined, and NaN. Since the input can be either an array or an object, your approach must handle both structures dynamically.
If the current value is an array, iterate through each element, recursively compact nested arrays or objects, and keep only elements that evaluate to truthy. If the value is an object, iterate through its keys and recursively process nested values before deciding whether to keep them.
This problem is best solved using recursion combined with conditional checks on value types. By visiting each element once and rebuilding the structure without falsy entries, you achieve an efficient traversal. The overall complexity depends on the number of elements processed in the object tree.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Recursive traversal of arrays and objects | O(n) | O(n) |
NeetCode
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.
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.
1#include <iostream>
2#include <map>
3#include <vector>
4#include <variant>
5
6using JSON = std::variant<std::nullptr_t, bool, int, std::string, std::vector<JSON>, std::map<std::string, JSON>>;
7
8bool is_falsy(const JSON& json) {
9 if (std::holds_alternative<std::nullptr_t>(json) ||
10 (std::holds_alternative<bool>(json) && !std::get<bool>(json)) ||
11 (std::holds_alternative<int>(json) && std::get<int>(json) == 0) ||
12 (std::holds_alternative<std::string>(json) && std::get<std::string>(json).empty())) {
13 return true;
}
return false;
}
JSON compact(JSON json) {
if (std::holds_alternative<std::vector<JSON>>(json)) {
std::vector<JSON> result;
for (auto& item : std::get<std::vector<JSON>>(json)) {
if (!is_falsy(item)) {
result.push_back(compact(item));
}
}
return result;
}
else if (std::holds_alternative<std::map<std::string, JSON>>(json)) {
std::map<std::string, JSON> result;
for (auto& pair : std::get<std::map<std::string, JSON>>(json)) {
if (!is_falsy(pair.second)) {
result[pair.first] = compact(pair.second);
}
}
return result;
}
return json;
}
int main() {
JSON json = std::map<std::string, JSON>{ {"a", nullptr}, {"b", std::vector<JSON>{false, 1}} };
JSON compacted = compact(json);
// Display compacted result using some output function
return 0;
}This C++ solution employs a variant-based JSON structure allowing multi-type storage. The solution recursively traverses the data structure, removing any elements or entries corresponding to falsy values. By leveraging variants, C++ can handle complex JSON objects more effectively.
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.
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.
1function compactIterative(obj) {
2
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
The optimal approach uses recursion to traverse arrays and objects while removing falsy values. Each element is processed once, and nested structures are compacted recursively to rebuild the final object or array.
Recursion allows you to process nested arrays and objects in a natural way. Each recursive call handles a smaller part of the structure, making it easier to compact deeply nested values without complex iterative logic.
Problems like Compact Object appear in JavaScript-focused interviews because they test recursion, object manipulation, and understanding of falsy values. Variations of deep traversal problems are common in frontend and full‑stack roles.
Understanding arrays, objects (hash maps), and recursion is key. You must also be comfortable checking value truthiness and reconstructing nested data structures while traversing them.
This JavaScript code uses an iterative approach with a stack to track objects or arrays needing traversal. It efficiently removes keys or elements with falsy values, addressing deeply nested structures without recursion.