LeetCode 2705 - Compact Object

Difficulty: 🟡 Medium
Topics: —

Solution

Problem Understanding

The problem asks us to compact a JSON-like object or array by removing all falsy values. Falsy values are those that evaluate to false in a Boolean context, such as null, 0, false, "", undefined (though JSON does not have undefined), and NaN. The input obj can be a nested structure, meaning arrays or objects may contain other arrays or objects, and the removal of falsy values should apply recursively.

The input represents a valid JSON structure, so we can assume objects only contain string keys and values that are numbers, strings, booleans, null, arrays, or objects. The output is a new structure where all falsy values are removed at every level. Arrays should retain their structure with remaining elements shifted left, and objects should only keep keys whose values are truthy after compacting.

Constraints tell us that the serialized JSON string can be up to 10^6 characters, which means the input can be large. This rules out inefficient or naive solutions that traverse elements multiple times unnecessarily. Important edge cases include empty arrays or objects, deeply nested falsy values, arrays with all falsy values, and objects where all keys are falsy. The problem guarantees the input is valid JSON, so we do not need to handle malformed input.

Approaches

The brute-force approach involves iterating over each element of the input and checking if it is falsy. For arrays, we create a new array of only truthy elements, recursively applying the same logic for nested arrays. For objects, we iterate over each key-value pair and keep only those keys whose values are truthy after recursively compacting them. This approach works but may repeatedly create new objects or arrays for every level of nesting, leading to higher space usage.

The optimal approach relies on a recursive function that directly processes the structure and returns a compacted copy. By processing elements recursively and only including truthy results, we naturally collapse nested structures without extra unnecessary traversals. This approach is efficient because each element is visited once, and memory is only allocated for the truthy elements.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * d)	O(n)	Traverses all elements, potentially multiple times at each nesting level
Optimal	O(n)	O(n)	Visits each element once recursively and constructs compacted structure directly

n is the total number of elements in the object, and d is the depth of nesting.

Algorithm Walkthrough

Define a recursive function compact(obj) that takes an object or array.
If obj is an array, initialize an empty list result.
Iterate over each element item in the array.
Recursively call compact(item) to compact nested structures.
If the result is truthy, append it to result. Ignore falsy results.
If obj is a dictionary, initialize an empty dictionary result.
Iterate over each key-value pair.
Recursively call compact(value) on the value.
If the compacted value is truthy, include the key in the result.
If obj is neither a list nor a dict, return it as-is.
Return the constructed result.

Why it works: Each recursion ensures that nested objects and arrays are compacted before inclusion in the parent structure. The invariant is that at every level, the returned object or array contains only truthy values. This guarantees correctness for arbitrarily nested inputs.

Python Solution

class Solution:
    def compactObject(self, obj: object) -> object:
        def compact(o):
            if isinstance(o, list):
                result = []
                for item in o:
                    compacted_item = compact(item)
                    if compacted_item or compacted_item == 0:  # include 0 as truthy in JSON terms
                        result.append(compacted_item)
                return result
            elif isinstance(o, dict):
                result = {}
                for key, value in o.items():
                    compacted_value = compact(value)
                    if compacted_value or compacted_value == 0:
                        result[key] = compacted_value
                return result
            else:
                return o
        return compact(obj)

This implementation defines a nested function compact that handles both arrays and objects recursively. For arrays, it iterates through elements and appends only truthy ones. For dictionaries, it iterates over key-value pairs and includes only keys with truthy values. Base types are returned as-is.

Go Solution

package main

import "reflect"

func compactObject(obj any) any {
    switch o := obj.(type) {
    case []any:
        result := []any{}
        for _, item := range o {
            compactedItem := compactObject(item)
            if !isFalsy(compactedItem) {
                result = append(result, compactedItem)
            }
        }
        return result
    case map[string]any:
        result := map[string]any{}
        for key, value := range o {
            compactedValue := compactObject(value)
            if !isFalsy(compactedValue) {
                result[key] = compactedValue
            }
        }
        return result
    default:
        return o
    }
}

func isFalsy(val any) bool {
    if val == nil {
        return true
    }
    v := reflect.ValueOf(val)
    switch v.Kind() {
    case reflect.Bool:
        return !v.Bool()
    case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64:
        return v.Int() == 0
    case reflect.Float32, reflect.Float64:
        return v.Float() == 0
    case reflect.String:
        return v.String() == ""
    }
    return false
}

In Go, we distinguish types explicitly and use reflection to check for falsy values, since Go does not have a direct concept of truthy/falsy for arbitrary any types. Slices and maps are processed recursively in the same way as Python.

Worked Examples

Example 1: [null, 0, false, 1]

Step through each element: null, 0, false are falsy, so only 1 remains. Output: [1].

Example 2: {"a": null, "b": [false, 1]}

"a" is falsy, "b" is an array [false, 1]. Compacting "b" removes false and keeps 1. Output: {"b": [1]}.

Example 3: [null, 0, 5, [0], [false, 16]]

Step through each element:

null and 0 removed.
5 kept.
[0] compacts to [].
[false, 16] compacts to [16].

Output: [5, [], [16]].

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each element is visited once recursively.
Space	O(n)	The output object may have up to n elements, plus recursion stack.

This accounts for the need to create new arrays or objects in memory for truthy values.

Test Cases

# Provided examples
assert Solution().compactObject([None, 0, False, 1]) == [1]  # basic array
assert Solution().compactObject({"a": None, "b": [False, 1]}) == {"b": [1]}  # nested array
assert Solution().compactObject([None, 0, 5, [0], [False, 16]]) == [5, [], [16]]  # nested arrays

# Boundary and edge cases
assert Solution().compactObject([]) == []  # empty array
assert Solution().compactObject({}) == {}  # empty object
assert Solution().compactObject([0, None, False, [], {}]) == [[], {}]  # array with falsy and empty objects/arrays
assert Solution().compactObject({"x": 0, "y": None, "z": False, "w": 1}) == {"w": 1}  # object with mixed falsy
assert Solution().compactObject([[[None]], [[0]], [[1]]]) == [[[]], [[]], [[1]]]  # nested arrays

Test	Why
`[None, 0, False, 1]`	Tests simple array filtering of falsy values
`{"a": None, "b": [False, 1]}`	Tests nested arrays inside an object
`[None, 0, 5, [0], [False, 16]]`	Tests multiple levels of nested arrays
`[]`	Edge case of empty array
`{}`	Edge case of empty object
`[0, None, False, [], {}]`	Tests empty objects and arrays retained while falsy values removed
`{"x":0,"y":None,"z":False,"w":1}`	Tests object filtering with mixed falsy
`[[[None]],[[0]],[[1]]]`	Tests deep nesting and preservation of structure

Edge Cases

Empty structures: An empty array or object should return itself because there are no elements to compact. This ensures the algorithm does not introduce None or nil unnecessarily.

**Arrays with only fals