Compact Object solution and explanation
4 more videos on this problem
Compact Object | Leetcode 2705 | JSON | 30 Days of JavaScript #javascript #leetcodeLearn With Chirag · 12:15 · 2K views
#day27 | 2705 Compact Object | 30 Days of JavaScript| Leetcode-2705 | 30 Days Challenge| Array in JSCoding with Ankita · 16:53 · 891 views
Can I solve LeetCode #2705 (Compact Object)?Larry · 5:29 · 212 views
#2705 Compact Object | Day27 | 30 Days of JavaScript | #javascript #leetcodesolution #array #objectProgrammers choice · 7:13 · 97 views
2705. Compact Object | Remove Empty Values from Object in JavaScriptCodeCrafting with Vishnu · 14:59 · 62 views
The problem
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.
def compact(obj):
if isinstance(obj, list):
return [compact(item) for item in obj if item]
elif isinstance(obj, dict):
return {k: compact(v) for k, v in obj.items() if v}
return obj
# Example Usage
example_dict = {"a": None, "b": [False, 1]}
print(compact(example_dict))import java.util.*;
class CompactObject {
public static Object compact(Object obj) {
if (obj instanceof List) {
List<Object> result = new ArrayList<>();
for (Object item : (List<?>) obj) {
if (Boolean.TRUE.equals(item) || (item != null && !Boolean.FALSE.equals(item))) {
Object compactedItem = compact(item);
if (!(compactedItem instanceof Collection && ((Collection<?>) compactedItem).isEmpty())) {
result.add(compactedItem);
}
}
}
return result;
} else if (obj instanceof Map) {
Map<String, Object> result = new HashMap<>();
for (Map.Entry<?, ?> entry : ((Map<?, ?>) obj).entrySet()) {
if (entry.getValue() != null && Boolean.TRUE.equals(entry.getValue())) {
result.put((String) entry.getKey(), compact(entry.getValue()));
}
}
return result;
}
return obj;
}
public static void main(String[] args) {
Map<String, Object> obj = new HashMap<>() {{
put("a", null);
put("b", Arrays.asList(false, 1));
}};
System.out.println(compact(obj));
}
}#include <iostream>
#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;
}function compact(obj) {
if (Array.isArray(obj)) {
return obj.map(compact).filter(Boolean);
}
if (obj !== null && typeof obj === 'object') {
return Object.entries(obj)
.filter(([key, value]) => Boolean(value))
.reduce((acc, [key, value]) => ({ ...acc, [key]: compact(value) }), {});
}
return obj;
}
// Example usage
console.log(compact({ a: null, b: [false, 1] }));#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
bool is_falsy(void *value, char type) {
switch (type) {
case 'n': return value == NULL;
case 'b': return (*(bool*)value) == false;
case 'i': return (*(int*)value) == 0;
case 's': return strcmp((char*)value, "") == 0;
default: return false;
}
}
void compact_object(void *obj, char type) {
// Fill with logic to handle recursively compacting the object or array in 'C'.
// This demo focuses on conceptual pseudocode, and actual implementation will
// require detailed type-checking and parsing logic.
}
int main() {
// Example usage and testing with pseudo objects here - actual implementation required.
return 0;
}using System;
using System.Collections;
using System.Collections.Generic;
public class CompactObject
{
public static object Compact(object obj)
{
if (obj is IList list)
{
var result = new List<object>();
foreach (var item in list)
{
if (item != null && !Equals(item, false))
{
var compactedItem = Compact(item);
if (compactedItem != null)
{
result.Add(compactedItem);
}
}
}
return result;
}
if (obj is IDictionary dictionary)
{
var result = new Dictionary<string, object>();
foreach (DictionaryEntry entry in dictionary)
{
if (entry.Value != null && !Equals(entry.Value, false))
{
var compactedValue = Compact(entry.Value);
if (compactedValue != null)
{
result.Add((string)entry.Key, compactedValue);
}
}
}
return result;
}
return obj;
}
public static void Main(string[] args)
{
var obj = new Dictionary<string, object>
{
{ "a", null },
{ "b", new List<object>{ false, 1 } }
};
Console.WriteLine(Compact(obj));
}
}Python makes handling this problem quite intuitive with its dynamic typing and list/dict comprehensions. The code above recursively filters out elements or keys/values that evaluate to 'False', effectively compacting the structure.
The time complexity is O(n) because each element is processed once, and the space complexity is O(d) due to recursion stack usage, where d represents the depth of nesting.
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.
def compact_iterative(obj):
stack = [(obj, None, None)] # (current_obj, parent, key/index)
while stack:
current, parent, key = stack.pop()
if isinstance(current, dict):
for k in list(current.keys()):
if not current[k]:
del current[k]
else:
stack.append((current[k], current, k))
elif isinstance(current, list):
for idx in range(len(current) - 1, -1, -1):
if not current[idx]:
current.pop(idx)
else:
stack.append((current[idx], current, idx))
return obj
# Example Usage
example_dict = {"a": None, "b": [False, 1]}
print(compact_iterative(example_dict))function compactIterative(obj) {
const stack = [{ obj, parent: null, key: null }];
while (stack.length) {
const { obj: current, parent, key } = stack.pop();
if (Array.isArray(current)) {
for (let i = current.length - 1; i >= 0; i--) {
if (!current[i]) current.splice(i, 1);
else stack.push({ obj: current[i], parent: current, key: i });
}
} else if (current !== null && typeof current === 'object') {
Object.keys(current).forEach(k => {
if (!current[k]) delete current[k];
else stack.push({ obj: current[k], parent: current, key: k });
});
}
}
return obj;
}
// Example usage
console.log(compactIterative({ a: null, b: [false, 1] }));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.
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).
type Obj = Record<any, any>;
function compactObject(obj: Obj): Obj {
if (!obj || typeof obj !== 'object') {
return obj;
}
if (Array.isArray(obj)) {
return obj.filter(Boolean).map(compactObject);
}
return Object.entries(obj).reduce((acc, [key, value]) => {
if (value) {
acc[key] = compactObject(value);
}
return acc;
}, {} as Obj);
}Complexity comparison
| Approach | Complexity |
|---|---|
| Recursive Depth-First Search | The time complexity is O(n) because each element is processed once, and the space complexity is O(d) due to recursion stack usage, where d represents the depth of nesting. |
| 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 | – |
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 |
Frequently asked questions
Is Compact Object easy or hard?
Compact Object is generally considered a medium difficulty problem. The main challenge is correctly handling nested arrays and objects while filtering falsy values without breaking the original structure.
How to solve Compact Object in O(n)?
Traverse the object or array using depth-first search. For each element, recursively compact nested objects or arrays before checking truthiness. Skip falsy values and include only truthy results in the final structure. Because each node is processed once, the algorithm runs in O(n) time.
What is the best approach for Compact Object?
Recursive Depth-First Search is the most common approach. Traverse the object or array, recursively compact nested structures, and keep only truthy results. This processes every element once for O(n) time complexity and uses O(h) recursion stack space where h is the nesting depth.
What data structure is used in Compact Object?
The solution relies on depth-first traversal of objects and arrays. Recursive implementations use the call stack implicitly, while iterative implementations use an explicit stack data structure to track nested structures during traversal.
What is the time complexity of Compact Object?
The time complexity is O(n), where n is the total number of values and properties in the nested structure. Each element or key-value pair is visited exactly once during traversal. Space complexity is O(h) for recursion or O(n) when using an explicit stack.
Compact Object Python or Java solution approach
The same DFS idea applies across languages. Check if the current value is a list/array or dictionary/object, recursively process children, and keep only truthy results. The logic remains O(n) regardless of whether it is implemented in Python, Java, or JavaScript.
Is Compact Object asked at Google, Amazon, or Meta?
Problems involving recursive traversal of nested JSON-like structures appear frequently in frontend and full‑stack interviews at companies like Meta and Amazon. Variants test understanding of recursion, DFS traversal, and data cleanup in hierarchical objects.