2705. Compact Object
Problem Description
In this problem, we are given an input that could be either an object or an array, referred to as obj
. Our task is to produce a "compact" version of this object. By "compact", what is meant is that we need to remove any key-value pairs from the object where the value is falsy. A falsy value is one that, when converted to a boolean, equals false
. Examples of falsy values in JavaScript include 0
, null
, undefined
, false
, NaN
, and ""
(an empty string).
To clarify further, this process must apply recursively to all nested objects within obj
. If obj
is an array, we should treat it similarly to an object, wherein the indices are keys; hence, any element with a falsy value should be removed. We can assume that obj
contains only valid JSON data types since it is stated that obj
could be the result of JSON.parse
.
Intuition
To tackle this challenge, we need a recursive approach because objects can be nested within objects, and we need to ensure that we're removing falsy values at all levels.
For arrays, the solution entails iterating over all elements, keeping only the truthy values, and if an element is itself an object or array, calling the compactObject
function recursively to compact that element before adding it back to the array.
For objects, we iterate over each key-value pair. When we encounter a falsy value, we remove the key from the object. If the value is an object (nested object or array), we make a recursive call to compactObject
to deal with nested structures before assigning the compacted object back to the key.
Here is the intuitive step-by-step manner in which the solution works:
- Check if the input
obj
is an array usingArray.isArray()
. - If it is an array:
- Create a temporary array to store the non-falsy values.
- Loop through each element in the original array.
- For each element, check if it is truthy.
- If the truthy element is an object, call
compactObject
on it, then push the compacted object to the temp array. - If the element is truthy and not an object, directly push it to the temp array.
- After the loop, return the temp array, which contains only non-falsy values or compacted objects.
- If
obj
is an object (and not an array):- Loop through each key-value pair using
Object.entries()
to access both key and value. - Check if the value is falsy. If so, delete the key from the object.
- If the value is an object, make a recursive call to
compactObject(value)
and assign the result back toobj[key]
. - Once all the keys have been processed, return the object.
- Loop through each key-value pair using
At the end of this process, we are left with a "compact" version of the original object or array, devoid of any falsy values.
Solution Approach
The implementation follows a recursive strategy, which is commonly used for problems involving nested data structures like objects or arrays. The solution exploits the ability in JavaScript to differentiate between arrays and objects and handle them appropriately.
Here's how the implementation unfolds:
-
We define a TypeScript type
Obj
which represents a record with keys of any type and values of any type. In JavaScript, objects serve as associative arrays or hash maps, allowing for the storage and retrieval of data through key-value pairs. -
The
compactObject
function takes in an object of typeObj
and returns an object of the same type. The initial check determines whether the input is an array or not. -
If it's an array, a temporary array
temp
is created. We iterate over each element of the original array, and we have two cases to handle:- If the current item is truthy, and...
- It is an object (which includes arrays in JavaScript since arrays are a special kind of object), then we recursively call
compactObject(item)
to compact the object, and we push the result into ourtemp
array. - It is not an object (e.g., a number, string that's not empty, etc.), then we directly push this item into our
temp
array.
- It is an object (which includes arrays in JavaScript since arrays are a special kind of object), then we recursively call
- If the current item is truthy, and...
-
If the input
obj
is not an array, it must be an object. We then useObject.entries(obj)
to iterate over the key-value pairs in the object. For each pair, we have two cases:- If the value is falsy (
!value
returnstrue
), we remove the key from the object usingdelete obj[key]
. - If the value is truthy and an object (or an array), we recursively call our
compactObject
function on this value. The compacted object (or array) is then assigned back to the current key in our original object withobj[key] = compactObject(value)
.
- If the value is falsy (
-
Finally, for both the array and the object case, the function returns the newly created
temp
array or the modified original objectobj
, respectively, both of which are now compacted versions of the input, free of falsy values.
The chosen algorithm is depth-first in nature because it calls itself recursively to deal with any nested objects before it moves on to the next sibling at the same level. This depth-first approach ensures that all levels of nested data structures are adequately compacted before finalizing any one level.
This approach works well with JSON objects/array structure, ensuring that no matter how deeply nested an object or array might be, all keys associated with falsy values are pruned.
Here is part of the TypeScript code, which is essentially JavaScript with type annotations for better developer readability and error checking, explaining the key parts of the recursive function:
1function compactObject(obj: Obj): Obj {
2 // Checks if the object is an array
3 if (Array.isArray(obj)) {
4 const temp = [];
5 // Process each element if it's an array
6 // ...
7 return temp;
8 }
9 // Not an array, so an object; process each key-value pair
10 for (const [key, value] of Object.entries(obj)) {
11 if (!value) delete obj[key]; // Delete falsy value
12 else if (typeof value === 'object') obj[key] = compactObject(value); // Recursive call
13 }
14 return obj;
15}
This code snippet demonstrates the conditional paths for arrays versus objects and includes the key operations of filtering out falsy values and the recursive calls necessary for nested structures.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a simple example to illustrate the solution approach. Suppose we have the following obj
, a mixed array that contains various elements, including falsy values and nested objects:
1let obj = [0, 1, false, { a: null, b: "string", c: { d: undefined, e: 2 } }, "", [], [3, null]];
We want to compact this array, removing any elements with falsy values and ensuring that any nested arrays or objects are also compacted.
-
The
compactObject
function is called withobj
. It discovers thatobj
is an array. -
It creates a temporary array
temp
to store non-falsy values. -
It starts iterating over
obj
. It encounters the following:0
(falsy) — Skipped and not added totemp
.1
(truthy) — Added totemp
.false
(falsy) — Skipped.- The next element is an object
{ a: null, b: "string", c: { d: undefined, e: 2 }}
.- It makes a recursive call to
compactObject
for this nested object.- In this recursive call:
a: null
(falsy) — This key-value pair is removed.b: "string"
(truthy) — Kept.c: { d: undefined, e: 2 }
— Another recursive call is made.d: undefined
(falsy) — Removed.e: 2
(truthy) — Kept.
- The object
{ b: "string", c: { e: 2 }}
is returned and added totemp
.
- In this recursive call:
- It makes a recursive call to
""
(falsy) — Skipped.[]
(truthy, but empty array) — Added totemp
as is.[3, null]
— A recursive call compacts it to[3]
, and this array is added totemp
.
-
After the iteration,
temp
holds[1, { b: "string", c: { e: 2 }}, [], [3]]
. -
The function returns the compacted
temp
array.
Our original obj
has been transformed into its compact version [1, { b: "string", c: { e: 2 }}, [], [3]]
. Thus, the implementation correctly removes all falsy values, including those nested in objects and arrays, resulting in a cleaner and more concise data structure.
Solution Implementation
1def compact_object(obj):
2 """
3 Removes falsy values from a dictionary or a list.
4 Recursive for nested dictionaries and lists.
5
6 :param obj: The dictionary or list to compact.
7 :return: The dictionary or list with falsy values removed.
8 """
9 # If the input is a list, compact the list.
10 if isinstance(obj, list):
11 compacted_list = []
12 for item in obj:
13 # Check if the item is truthy.
14 if item:
15 # If the item itself is an object (list or dict), recurse.
16 # Otherwise, add the item to the compacted list.
17 compacted_list.append(compact_object(item) if isinstance(item, (dict, list)) else item)
18 return compacted_list
19
20 # If the input is a dictionary, compact the dictionary.
21 elif isinstance(obj, dict):
22 # Create a copy to avoid modifying the input dictionary while iterating.
23 keys_to_delete = []
24 for key, value in obj.items():
25 # Check if the value is falsy.
26 if not value:
27 # Mark the key for removal if the value is falsy.
28 keys_to_delete.append(key)
29 elif isinstance(value, (dict, list)):
30 # If the value itself is an object (list or dict), apply recursion.
31 obj[key] = compact_object(value)
32
33 # Delete the marked keys from the dictionary.
34 for key in keys_to_delete:
35 del obj[key]
36
37 return obj
38
39 else:
40 # If the obj is neither a list nor a dictionary, just return it.
41 return obj
42
1import java.util.HashMap;
2import java.util.Map;
3import java.util.List;
4import java.util.ArrayList;
5
6public class ObjectCompactor {
7
8 /**
9 * Removes falsy values from an object or a list.
10 * Recursive for nested objects and lists.
11 *
12 * @param object - The object or list to compact.
13 * @return - The object or list with falsy values removed.
14 */
15 public static Object compactObject(Object object) {
16 // If the input is a list, compact the list.
17 if (object instanceof List) {
18 List<?> originalList = (List<?>) object;
19 List<Object> compactedList = new ArrayList<>();
20
21 for (Object item : originalList) {
22 if (isTruthy(item)) {
23 // If the item is a Map or List, recurse.
24 // Otherwise, add the item to the compactedList.
25 compactedList.add((item instanceof Map || item instanceof List) ? compactObject(item) : item);
26 }
27 }
28 return compactedList;
29 } else if (object instanceof Map) { // If the input is a Map, compact the Map.
30 Map<?, ?> originalMap = (Map<?, ?>) object;
31 Map<Object, Object> compactedMap = new HashMap<>();
32
33 for (Map.Entry<?, ?> entry : originalMap.entrySet()) {
34 if (isTruthy(entry.getValue())) {
35 // If the value is a Map or List, apply recursion.
36 compactedMap.put(entry.getKey(), (entry.getValue() instanceof Map || entry.getValue() instanceof List) ? compactObject(entry.getValue()) : entry.getValue());
37 }
38 }
39 return compactedMap;
40 } else {
41 // If the input is neither a List nor a Map, simply return the object
42 return object;
43 }
44 }
45
46 /**
47 * Helper method to determine if an object is "truthy" (not null and not false).
48 *
49 * @param obj - The object to check.
50 * @return true if the object is "truthy", false otherwise.
51 */
52 private static boolean isTruthy(Object obj) {
53 return obj != null && !Boolean.FALSE.equals(obj);
54 }
55}
56
1#include <vector>
2#include <map>
3#include <string>
4#include <any>
5#include <type_traits>
6
7// Compact the given std::map or std::vector by removing falsy values.
8// This function is overloaded to handle both containers.
9std::map<std::string, std::any> compactObject(const std::map<std::string, std::any>& object);
10std::vector<std::any> compactObject(const std::vector<std::any>& array);
11
12// Helper function to check if an std::any object is falsy.
13bool isFalsy(const std::any& value) {
14 try {
15 if (value.type() == typeid(bool)) {
16 return !std::any_cast<bool>(value);
17 } else if (value.type() == typeid(int)) {
18 return std::any_cast<int>(value) == 0;
19 } else if (value.type() == typeid(double)) {
20 return std::any_cast<double>(value) == 0.0;
21 } else if (value.type() == typeid(std::string)) {
22 return std::any_cast<std::string>(value).empty();
23 } else {
24 // Consider any other type as not falsy.
25 return false;
26 }
27 } catch (const std::bad_any_cast&) {
28 // If any_cast throws, the type is not falsy.
29 return false;
30 }
31}
32
33// Compacts the given std::vector by removing falsy values, and
34// applies recursion if an element is another container.
35std::vector<std::any> compactObject(const std::vector<std::any>& array) {
36 std::vector<std::any> compactedArray;
37 for (const auto& item : array) {
38 if (!isFalsy(item)) {
39 if (item.type() == typeid(std::map<std::string, std::any>)) {
40 compactedArray.push_back(compactObject(std::any_cast<std::map<std::string, std::any>>(item)));
41 } else if (item.type() == typeid(std::vector<std::any>)) {
42 compactedArray.push_back(compactObject(std::any_cast<std::vector<std::any>>(item)));
43 } else {
44 compactedArray.push_back(item);
45 }
46 }
47 }
48 return compactedArray;
49}
50
51// Compacts the given std::map by removing falsy values, and
52// applies recursion if a value is another container.
53std::map<std::string, std::any> compactObject(const std::map<std::string, std::any>& object) {
54 std::map<std::string, std::any> compactedObject;
55 for (const auto& [key, value] : object) {
56 if (!isFalsy(value)) {
57 if (value.type() == typeid(std::map<std::string, std::any>)) {
58 compactedObject[key] = compactObject(std::any_cast<std::map<std::string, std::any>>(value));
59 } else if (value.type() == typeid(std::vector<std::any>)) {
60 compactedObject[key] = compactObject(std::any_cast<std::vector<std::any>>(value));
61 } else {
62 compactedObject[key] = value;
63 }
64 }
65 }
66 return compactedObject;
67}
68
1// Type definition for a generic object with any key type and any value type.
2type GenericObject = Record<string, unknown>;
3
4/**
5 * Removes falsy values from an object or an array.
6 * Recursive for nested objects and arrays.
7 *
8 * @param {GenericObject | unknown[]} object - The object or array to compact.
9 * @return {GenericObject | unknown[]} - The object or array with falsy values removed.
10 */
11function compactObject(object: GenericObject | unknown[]): GenericObject | unknown[] {
12 // If the input is an array, compact the array.
13 if (Array.isArray(object)) {
14 const compactedArray = [];
15 for (const item of object) {
16 if (item) {
17 // If the item is an object, recurse.
18 // Otherwise, add the item to the compacted array.
19 compactedArray.push(typeof item === 'object' ? compactObject(item as GenericObject) : item);
20 }
21 }
22 return compactedArray;
23 } else { // If the input is an object, compact the object.
24 for (const [key, value] of Object.entries(object)) {
25 if (!value) {
26 // Remove the key if the value is falsy.
27 delete object[key];
28 } else if (typeof value === 'object') {
29 // If the value is an object, apply recursion
30 object[key] = compactObject(value as GenericObject);
31 }
32 }
33 return object;
34 }
35}
36
Time and Space Complexity
Time Complexity:
The function compactObject
operates by checking each element of the input obj
. If obj
is an array, it iterates through every element, and if an element is truthy and an object, it calls itself recursively; otherwise, it pushes the item into a new array. When obj
is a regular object, it iterates through all key-value pairs, deleting falsy values or recursively calling itself on sub-objects.
Let n
be the combined number of elements and properties in all nested structures within the input object (including arrays and sub-objects). The worst-case time complexity is O(n)
because each element or property is visited at most once. Even though there is recursion, each call processes a different part of the object without revisiting any elements or properties.
However, note that JavaScript objects have some overhead for property access and deletion, which does not significantly affect the big O notation but may impact real-world performance.
Space Complexity:
The space complexity is also O(n)
in the worst case. This is due to several factors:
- Each recursive call to
compactObject
occupies additional space on the call stack. - New arrays and objects are created to store the compacted versions of the input.
- Temporary arrays are created to store non-falsy items when input is an array.
The actual space used depends on the depth of the nested structures and the number of non-falsy elements kept after compaction. The space is linearly proportional to the number of items and nested objects in the input due to the recursion stack and new structures created.
Note that in JavaScript, objects and arrays are reference types. Hence the size of pointers is considered rather than the size of the actual values when calculating space complexity.
Which of the following is a good use case for backtracking?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time