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.

Examples

Example 1

1
2
3
4
5
6
7

    
    
    Input: obj = [null, 0, false, 1]
    Output: [1]
    Explanation: All falsy values have been removed from the array.
    

Example 2

1
2
3
4
5
6

    
    
    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

1
2
3
4
5
6
7

    
    
    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

  • obj is a valid JSON object
  • 2 <= JSON.stringify(obj).length <= 10^6

Solution

Method 1 – Recursive Filtering

Intuition

To compact an object or array, recursively remove all keys (or indices) with falsy values. For arrays, filter out falsy elements and recursively compact nested arrays/objects. For objects, remove keys with falsy values and recursively compact nested values.

Approach

  1. If the input is an array:
    • Recursively compact each element.
    • Filter out elements that are falsy after compaction.
  2. If the input is an object:
    • For each key, recursively compact the value.
    • Only keep keys whose compacted value is truthy.
  3. For primitive values, return as is.
  4. Return the compacted object or array.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    compactObject(obj) {
        if (Array.isArray(obj)) {
            const ans = [];
            for (const v of obj) {
                const c = this.compactObject(v);
                if (Boolean(c)) ans.push(c);
            }
            return ans;
        } else if (obj !== null && typeof obj === 'object') {
            const ans = {};
            for (const k in obj) {
                const c = this.compactObject(obj[k]);
                if (Boolean(c)) ans[k] = c;
            }
            return ans;
        } else {
            return obj;
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    compactObject(obj: any): any {
        if (Array.isArray(obj)) {
            const ans: any[] = [];
            for (const v of obj) {
                const c = this.compactObject(v);
                if (Boolean(c)) ans.push(c);
            }
            return ans;
        } else if (obj !== null && typeof obj === 'object') {
            const ans: any = {};
            for (const k in obj) {
                const c = this.compactObject(obj[k]);
                if (Boolean(c)) ans[k] = c;
            }
            return ans;
        } else {
            return obj;
        }
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the total number of keys and elements in the object/array.
  • 🧺 Space complexity: O(n), for the recursion stack and output.