Problem Description

You are given an object or array obj that needs to be "compacted" by removing all falsy values from it.

A compact object is created by:

• Removing any keys/properties that contain falsy values
• Applying this removal process recursively to all nested objects and arrays
• Treating arrays as objects where the indices serve as keys

A value is considered falsy when Boolean(value) returns false. In JavaScript/TypeScript, falsy values include:

• false
• 0
• "" (empty string)
• null
• undefined
• NaN

The compacting process works as follows:

• For objects: Remove any key-value pairs where the value is falsy
• For arrays: Remove falsy elements (which may change indices)
• For nested structures: Apply the same rules recursively

The input obj is guaranteed to be valid JSON (as if it came from JSON.parse).

Example: If the input is {a: null, b: [false, 1], c: {d: "", e: 2}}, the output would be {b: [1], c: {e: 2}} because:

• Key a is removed (value is null)
• In array b, false is removed, keeping only 1
• In nested object c, key d is removed (value is empty string), keeping only e: 2

Intuition

The key insight is that we need to traverse the entire data structure and make decisions at each level about what to keep and what to remove. Since the structure can be nested to any depth, recursion becomes the natural choice.

Let's think about what we're dealing with:

1. Primitive values: These can't have "keys" to remove, so we return them as-is if they're truthy
2. Arrays: We need to filter out falsy elements and process remaining elements recursively
3. Objects: We need to check each key-value pair, keep only truthy values, and process those values recursively

The recursive pattern emerges from recognizing that at each level, we perform the same operation: check if values are falsy, remove them if they are, and for any remaining values that are objects or arrays, apply the same logic to their contents.

For arrays, filter(Boolean) is a clean way to remove falsy values since Boolean acts as a predicate function that returns false for falsy values. After filtering, we still need to recursively process each remaining element with map(compactObject) because those elements might themselves be objects or arrays containing falsy values.

For objects, we iterate through all entries, and only add a key-value pair to our result if the value is truthy. But before adding, we recursively process the value to ensure any nested structures are also compacted.

The base case of our recursion is when we encounter a non-object value (including null) - these are leaf nodes in our data structure tree that can't be traversed further, so we simply return them if they're truthy or exclude them if they're falsy (handled by the calling context).

Solution Approach

The implementation uses recursion to traverse and compact the data structure. Let's walk through how the solution handles each case:

Base Case - Non-objects and null:

if (!obj || typeof obj !== 'object') {
    return obj;
}

When obj is not an object or is null, we return it as-is. This handles primitive values (numbers, strings, booleans) and null. Since these values don't have nested properties, there's nothing to compact.

Array Processing:

if (Array.isArray(obj)) {
    return obj.filter(Boolean).map(compactObject);
}

For arrays, we apply a two-step process:

1. filter(Boolean) removes all falsy elements. The Boolean constructor acts as a predicate that returns false for falsy values (0, "", false, null, undefined, NaN)
2. map(compactObject) recursively processes each remaining element to ensure nested structures within the array are also compacted

Object Processing:

return Object.entries(obj).reduce((acc, [key, value]) => {
    if (value) {
        acc[key] = compactObject(value);
    }
    return acc;
}, {} as Obj);

For regular objects, we:

1. Use Object.entries(obj) to get an array of [key, value] pairs
2. Use reduce to build a new object, starting with an empty object {}
3. For each key-value pair:
   • Check if the value is truthy with if (value)
   • If truthy, recursively call compactObject(value) to process nested structures
   • Add the compacted value to the accumulator object with the same key
4. Return the accumulated object containing only keys with truthy values

The recursion ensures that the compacting process applies to all levels of nesting. Each recursive call either:

• Returns a primitive value unchanged (base case)
• Returns a compacted array with all falsy elements removed
• Returns a compacted object with all falsy-valued keys removed

This depth-first approach guarantees that by the time a value is checked for truthiness at any level, all of its nested content has already been compacted.

Example Walkthrough

Let's trace through a concrete example to see how the recursive solution works:

Input: {a: 0, b: {c: false, d: "hi"}, e: [1, "", 2]}

Step-by-step execution:

1. Initial call - compactObject({a: 0, b: {c: false, d: "hi"}, e: [1, "", 2]})

   • Input is an object (not null, not primitive), so we process it as an object
   • We iterate through entries: [["a", 0], ["b", {c: false, d: "hi"}], ["e", [1, "", 2]]]

2. Processing key "a":

   • Value is 0 (falsy)
   • Skip adding to result (fails if (value) check)

3. Processing key "b":

   • Value is {c: false, d: "hi"} (truthy - objects are truthy)
   • Recursively call compactObject({c: false, d: "hi"})
     • It's an object, so iterate through entries: [["c", false], ["d", "hi"]]
     • "c" has value false (falsy) → skip
     • "d" has value "hi" (truthy) → recursively call compactObject("hi")
       • It's a primitive string, return "hi"
     • Result: {d: "hi"}
   • Add to result: acc["b"] = {d: "hi"}

4. Processing key "e":

   • Value is [1, "", 2] (truthy - arrays are truthy)
   • Recursively call compactObject([1, "", 2])
     • It's an array, so:
     • First, filter: [1, "", 2].filter(Boolean) → [1, 2] (empty string removed)
     • Then map: [1, 2].map(compactObject)
       • compactObject(1) → returns 1 (primitive)
       • compactObject(2) → returns 2 (primitive)
     • Result: [1, 2]
   • Add to result: acc["e"] = [1, 2]

5. Final result: {b: {d: "hi"}, e: [1, 2]}

The key observations:

• Falsy primitive values at the top level of objects/arrays are removed
• The recursion ensures nested structures are cleaned at all depths
• Arrays maintain their order but with falsy elements filtered out
• Objects only keep keys whose values are truthy after recursive processing

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the total number of elements (including nested elements) in the input object structure.

The algorithm visits each element exactly once during the traversal. For objects, it iterates through all key-value pairs using Object.entries(). For arrays, it processes each element with filter() and map(). Since each element is processed once regardless of the depth of nesting, the overall time complexity remains linear relative to the total number of elements.

The space complexity is O(n) for two main reasons:

1. Recursion stack depth: In the worst case, the recursion depth equals the maximum nesting level of the object structure, which could be O(n) for a deeply nested structure (like a linked list-shaped object).
2. Output space: The function creates a new compacted object structure. In the worst case where no elements are removed (all values are truthy), the output size equals the input size, requiring O(n) space.

The intermediate operations like Object.entries(), filter(), and map() also create temporary arrays, but these don't exceed the overall O(n) space bound since they operate on one level at a time.

Common Pitfalls

Pitfall 1: Incorrect Handling of Empty Containers

The Problem: A common mistake is not recognizing that empty arrays [] and empty objects {} are truthy in JavaScript/Python, even though they might seem "empty". The current solution correctly preserves them, but developers often mistakenly try to remove them.

Incorrect Implementation:

# Wrong: Trying to remove empty containers
if isinstance(obj, list):
    result = [compactObject(item) for item in obj if item]
    return result if result else None  # DON'T do this!

# Wrong: Checking for empty dict
if value and (not isinstance(value, dict) or value):  # Confusing logic
    result[key] = compactObject(value)

Why It's Wrong:

• Boolean([]) returns true in JavaScript and bool([]) returns True in Python
• Boolean({}) returns true in JavaScript and bool({}) returns True in Python
• These empty containers should be preserved in the output

Correct Approach: The original solution handles this correctly by only checking truthiness of the values themselves, not whether containers are empty after processing.

Pitfall 2: Modifying the Original Object

The Problem: Some implementations might accidentally modify the original object instead of creating a new one.

Incorrect Implementation:

def compactObject(obj):
    if isinstance(obj, dict):
        # Wrong: Modifying original object
        for key in list(obj.keys()):
            if not obj[key]:
                del obj[key]  # Mutating original!
            else:
                obj[key] = compactObject(obj[key])
        return obj

Why It's Wrong:

• This mutates the input object, which can cause unexpected side effects
• If the same object is referenced elsewhere in the code, those references will see the changes

Correct Approach: Always create new objects/arrays during the compacting process:

# Correct: Creating new dict
result = {}
for key, value in obj.items():
    if value:
        result[key] = compactObject(value)
return result

Pitfall 3: Not Handling Special Falsy Values Correctly

The Problem: Developers might use explicit checks that miss certain falsy values or incorrectly classify truthy values as falsy.

Incorrect Implementation:

# Wrong: Using explicit checks that miss cases
if value is not None and value != "":  # Misses 0, False, etc.
    result[key] = compactObject(value)

# Wrong: Using len() which doesn't work for all types
if len(str(value)) > 0:  # Converts 0 to "0" which has length > 0
    result[key] = compactObject(value)

Why It's Wrong:

• Explicit checks often miss edge cases (like NaN, 0, False)
• Type conversions can change the truthiness evaluation

Correct Approach: Use Python's built-in truthiness evaluation:

if value:  # Correctly identifies all falsy values
    result[key] = compactObject(value)

This naturally handles all falsy values: None, False, 0, 0.0, "", [] (for filtering), etc.