Sponsored
Sponsored
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 <map>
#include <vector>
#include <variant>
using JSON = std::variant<std::nullptr_t, bool, int, std::string, std::vector<JSON>, std::map<std::string, JSON>>;
bool is_falsy(const JSON& json) {
if (std::holds_alternative<std::nullptr_t>(json) ||
(std::holds_alternative<bool>(json) && !std::get<bool>(json)) ||
(std::holds_alternative<int>(json) && std::get<int>(json) == 0) ||
(std::holds_alternative<std::string>(json) && std::get<std::string>(json).empty())) {
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.
1def compact_iterative(obj):
2 stack = [(obj, None, None)] # (current_obj, parent, key/index)
3 while stack:
4 current, parent, key = stack.pop()
5 if isinstance(current, dict):
6 for k in list(current.keys()):
7 if not current[k]:
8 del current[k]
9 else:
10 stack.append((current[k], current, k))
11 elif isinstance(current, list):
12 for idx in range(len(current) - 1, -1, -1):
13 if not current[idx]:
14 current.pop(idx)
15 else:
16 stack.append((current[idx], current, idx))
17
18 return obj
19
20# Example Usage
21example_dict = {"a": None, "b": [False, 1]}
22print(compact_iterative(example_dict))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.