Compact Object - Practice Coding Problems

Compact Object - Problem

JavaScript Medium

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.

Input & Output

Example 1 — Object with Falsy Values

$ Input: obj = {"a": null, "b": [false, 1]}

› Output: {"b": [1]}

💡 Note: The key 'a' is removed because null is falsy. In the array [false, 1], false is removed but 1 remains as it's truthy.

Example 2 — Array with Mixed Values

$ Input: obj = [null, 0, 5, [0], {}]

› Output: [5, []]

💡 Note: null and 0 are falsy and removed. 5 remains. [0] becomes [] after removing 0. {} remains as an empty object.

Example 3 — Nested Objects

$ Input: obj = {"a": {"b": {"c": 0}}}

› Output: {}

💡 Note: The value 0 is falsy, so it's removed. This makes object {"c": 0} become {}, then the parent objects cascade to become empty, resulting in {}.

Constraints

obj is a valid JSON object
obj only contains JSON data types: null, boolean, number, string, object, array
2 ≤ JSON.stringify(obj).length ≤ 10⁶
Nested depth ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input

Original object/array with falsy values mixed in

Process

Recursively filter out falsy values (null, false, 0, "")

Output

Compacted structure with only truthy values

Key Takeaway

🎯 Key Insight: Recursively traverse nested structures and filter out values that evaluate to false in Boolean context

Asked in

F Facebook 35 G Google 28 A Amazon 22 M Microsoft 18

The key insight is to recursively traverse the object/array structure and filter out falsy values using JavaScript's Boolean() conversion rules. The optimal approach recursively processes nested structures, removing falsy values (null, false, 0, "", undefined) while preserving the overall structure. Time: O(n), Space: O(n) where n is the total number of elements.

Common Approaches

Approach	Time	Space	Notes
✓ Optimized Recursive Compacting	O(n)	O(n)	Improved version with better falsy detection and empty container handling
Recursive Deep Traversal	O(n)	O(n)	Recursively traverse the object/array and rebuild without falsy values

Optimized Recursive Compacting — Algorithm Steps

Step 1: Use Boolean() conversion to detect falsy values
Step 2: For containers, recursively compact then check if result is empty
Step 3: Only include non-empty compacted containers in result

Visualization

Tap to expand

Step-by-Step Walkthrough

Input Analysis

Identify all falsy values using Boolean() rules

Recursive Processing

Recursively compact nested structures

Empty Container Check

Remove containers that become empty after compacting

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <cjson/cJSON.h>

int isTruthy(cJSON* item) {
    if (cJSON_IsNull(item)) return 0;
    if (cJSON_IsBool(item)) return cJSON_IsTrue(item);
    if (cJSON_IsNumber(item)) return cJSON_GetNumberValue(item) != 0.0;
    if (cJSON_IsString(item)) return strlen(cJSON_GetStringValue(item)) > 0;
    return 1;
}

int isEmpty(cJSON* item) {
    if (cJSON_IsArray(item)) return cJSON_GetArraySize(item) == 0;
    if (cJSON_IsObject(item)) return cJSON_GetArraySize(item) == 0;
    return 0;
}

cJSON* compact(cJSON* item) {
    if (cJSON_IsArray(item)) {
        cJSON* result = cJSON_CreateArray();
        cJSON* element = NULL;
        cJSON_ArrayForEach(element, item) {
            if (isTruthy(element)) {
                if (cJSON_IsObject(element) || cJSON_IsArray(element)) {
                    cJSON* compacted = compact(element);
                    if (!isEmpty(compacted)) {
                        cJSON_AddItemToArray(result, compacted);
                    } else {
                        cJSON_Delete(compacted);
                    }
                } else {
                    cJSON_AddItemToArray(result, cJSON_Duplicate(element, 1));
                }
            }
        }
        return result;
    } else if (cJSON_IsObject(item)) {
        cJSON* result = cJSON_CreateObject();
        cJSON* element = NULL;
        cJSON_ArrayForEach(element, item) {
            if (isTruthy(element)) {
                if (cJSON_IsObject(element) || cJSON_IsArray(element)) {
                    cJSON* compacted = compact(element);
                    if (!isEmpty(compacted)) {
                        cJSON_AddItemToObject(result, element->string, compacted);
                    } else {
                        cJSON_Delete(compacted);
                    }
                } else {
                    cJSON_AddItemToObject(result, element->string, cJSON_Duplicate(element, 1));
                }
            }
        }
        return result;
    }
    return cJSON_Duplicate(item, 1);
}

cJSON* solution(cJSON* obj) {
    return compact(obj);
}

int main() {
    char input[10000];
    fgets(input, sizeof(input), stdin);
    input[strcspn(input, "\n")] = 0;
    
    cJSON* obj = cJSON_Parse(input);
    cJSON* result = solution(obj);
    
    char* output = cJSON_PrintUnformatted(result);
    printf("%s\n", output);
    
    cJSON_Delete(obj);
    cJSON_Delete(result);
    free(output);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through all elements in nested structure

✓ Linear Growth

Space Complexity

O(n)

New compacted structure plus recursion call stack

⚡ Linearithmic Space

27.6K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized Recursive Compacting — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler