2822. Inversion of Object


Problem Description

The task is to create a function that accepts either an object (often called a map or dictionary in other languages) or an array obj, and returns a new object, invertedObj. This inverted object should swap the keys and values from the original obj: each original key becomes a value, and each original value becomes a key.

For example, given an object { 'a': '1', 'b': '2' }, the invertedObj would be { '1': 'a', '2': 'b' }.

Handling arrays means considering their indices as keys. For instance, if obj is an array like ['a', 'b'], the resulting invertedObj would be { 'a': '0', 'b': '1' } (indices '0' and '1' become values in the inverted object).

A twist in this problem is how to handle duplicate values in the obj. If a value appears multiple times, then in invertedObj, this value becomes a key mapped to an array containing all the original keys that had the value. For instance, if obj is an object like { 'a': '1', 'b': '1' }, then invertedObj would be { '1': ['a', 'b'] }.

The function guarantees that obj will only have strings as values, which simplifies the possible types of values we have to handle for keys in invertedObj.

Intuition

The intuition behind the solution is fairly straightforward given the constraints and objectives of the problem: since we are looking to invert the key-value pairs, we'll iterate through all the key-value pairs of the input obj.

For each pair, we'll check if the value we're looking at is already a key in the ans (the accumulator or result object). If so, we need to handle it differently depending on whether it's already associated with multiple original keys (which would mean it's already an array) or not.

  1. If the value is not yet a key in the ans, we simply set the value as a key in ans and assign it the current key as its value.
  2. If the value already exists as a key and it's associated with an array, we append the current key to this array.
  3. If the value already exists as a key but not as an array (meaning this is the second occurrence of this value), we transform the value into an array and add the current key to it.

This three-step logic ensures that each value in the original obj is turned into a key in invertedObj and that any duplicates are handled in such a way that the result is an array of original keys for values that appear multiple times.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

How does quick sort divide the problem into subproblems?

Solution Approach

The solution uses a simple iteration approach with a conditional structure to handle the creation of the inverted object. The primary data structure used is a JavaScript object (ans), which is essentially acting like a hash table, allowing us to store key-value pairs efficiently.

  1. We define a function named invertObject that takes an object as a parameter and initializes an empty object ans which will store our inverted key-value pairs.

  2. We iterate over the obj parameter using a for...in loop. In JavaScript, a for...in loop iterates over the enumerable properties (keys) of an object.

  3. Inside the loop, for every key-value pair in obj, we check if the value (which will become a key in ans) already exists in ans using ans.hasOwnProperty(obj[key]).

    • If it does not exist already, we simply assign the value from obj as the key in ans, and set the original key as the value, like so: ans[obj[key]] = key.

    • If it does exist, we need to differentiate between two cases:

      • When the existing value is an array, which means the value has appeared before and we've already converted it into an array. Here we push the current key to that array: ans[obj[key]].push(key).
      • When it is not an array, which means this is the second occurrence of that value and it is currently stored as a single string. We transform it into an array containing the previously mapped key and the current key: ans[obj[key]] = [ans[obj[key]], key].
  4. After we have iterated over all key-value pairs in obj, the ans object is fully constructed and now contains all the inverted key-value pairs, with single values being kept as strings and duplicated values being stored as arrays.

  5. Finally, the function returns the ans object as the output, giving us the required invertedObj.

The elegance of this solution lies in its simplicity and efficiency. We use a single pass over the input obj, leveraging hash table operations for quick access and update, and we handle duplicate values seamlessly by converting them to an array only when required. This approach ensures optimal use of space since we don't prematurely create arrays for values that don't have multiple keys.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Depth first search can be used to find whether two components in a graph are connected.

Example Walkthrough

Let's walkthrough the solution approach using a small example. Suppose we have the following object:

1let obj = { 'a': '1', 'b': '2', 'c': '2', 'd': '3' };

According to our problem description, we want to invert this object's keys and values but also handle the case where a single value may correspond to multiple keys. Here is how we would apply the solution steps outlined above:

  1. We initiaize our empty object ans that will store the inverted key-value pairs:
1let ans = {};
  1. Now, we iterate over the object. Starting with the first key-value pair ('a': '1'):

    • Since '1' is not already a key in ans, we set ans[1] = 'a'.
  2. Moving to the next key-value pair ('b': '2'):

    • Since '2' is not in ans yet, we set ans[2] = 'b'.
  3. Next, we have the key-value pair ('c': '2'):

    • Now we find '2' already as a key in ans. Since it is not associated with an array yet, we convert it into an array including the current and prior keys, resulting in ans[2] = ['b', 'c'].
  4. Finally, we have the key-value pair ('d': '3'):

    • Again, '3' is not a key in ans, so we set ans[3] = 'd'.

After iterating through all key-value pairs, our ans object looks like this:

1{
2 '1': 'a',
3 '2': ['b', 'c'],
4 '3': 'd'
5}
  1. This ans object is our inverted object that we return from the function:
1return ans;

The output indicates that:

  • The value '1' corresponds to the key 'a' in the original object.
  • The value '2' corresponds to both keys 'b' and 'c'.
  • The value '3' corresponds to the key 'd'.

The solution effectively handles duplicate values by storing all keys that correspond to a single value in an array, thus maintaining the integrity of the original object in the inverted output.

Solution Implementation

1def invert_object(source_object):
2    # Initialize a dictionary to store the inverted key-value pairs
3    inverted_object = {}
4
5    # Iterate over each key-value pair in the source object
6    for key, value in source_object.items():
7        # Check if the value already exists as a key in the inverted object
8        if value in inverted_object:
9            # If the inverted key (which is the original object's value) already has a list,
10            # append the new key (original object's key) to that list
11            if isinstance(inverted_object[value], list):
12                inverted_object[value].append(key)
13            else:
14                # If there is a single value, convert it into a list containing
15                # the existing and new keys
16                inverted_object[value] = [inverted_object[value], key]
17        else:
18            # If the inverted key does not exist, add it with its new value 
19            # which is the original object's key
20            inverted_object[value] = key
21
22    # Return the inverted dictionary after all key-value pairs have been processed
23    return inverted_object
24
1import java.util.HashMap;
2import java.util.Map;
3import java.util.List;
4import java.util.ArrayList;
5
6public class ObjectInverter {
7
8    /**
9     * Inverts the keys and values of the given map. If the same value is encountered more than once,
10     * the corresponding keys are grouped in a list.
11     * @param sourceMap The map to invert.
12     * @return A map with inverted keys and values.
13     */
14    public static Map<Object, Object> invertObject(Map<Object, Object> sourceMap) {
15        // Initialize a map to store the inverted key-value pairs.
16        Map<Object, Object> invertedMap = new HashMap<>();
17
18        // Iterate over each entry in the source map.
19        for (Map.Entry<Object, Object> entry : sourceMap.entrySet()) {
20            Object key = entry.getKey();
21            Object value = entry.getValue();
22
23            // Check if the value already exists as a key in the inverted map.
24            if (invertedMap.containsKey(value)) {
25                // Retrieve the existing entry for the current value.
26                Object existingEntry = invertedMap.get(value);
27
28                // If the corresponding inverted value is already a List,
29                // we add the new key into that List.
30                if (existingEntry instanceof List) {
31                    ((List) existingEntry).add(key);
32                } else {
33                    // Otherwise, we create a List to combine the existing and new keys,
34                    // then put it as the new value for the current inverted key.
35                    List<Object> keysList = new ArrayList<>();
36                    keysList.add(existingEntry);
37                    keysList.add(key);
38                    invertedMap.put(value, keysList);
39                }
40            } else {
41                // If the inverted key does not exist, simply add it with its value (original map's key).
42                invertedMap.put(value, key);
43            }
44        }
45
46        // Return the resulting map after all keys have been inverted.
47        return invertedMap;
48    }
49
50    // Optional: main method for testing the invertObject function.
51    public static void main(String[] args) {
52        Map<Object, Object> sourceMap = new HashMap<>();
53        sourceMap.put("a", 1);
54        sourceMap.put("b", 2);
55        sourceMap.put("c", 1);
56        Map<Object, Object> invertedMap = invertObject(sourceMap);
57      
58        // This should print "{1=[a, c], 2=b}"
59        System.out.println(invertedMap);
60    }
61}
62
1#include <unordered_map>
2#include <vector>
3#include <string>
4#include <typeinfo>
5
6// This function takes a map and inverts its keys and values.
7// If the same value is encountered more than once, the corresponding keys are grouped in a vector.
8std::unordered_map<std::string, std::vector<std::string>> InvertObject(std::unordered_map<std::string, std::string>& sourceMap) {
9    // Initialize a map to store the inverted key-value pairs.
10    std::unordered_map<std::string, std::vector<std::string>> invertedMap;
11
12    // Iterate over each key-value pair in the source map.
13    for (const auto& kvp : sourceMap) {
14        const std::string& key = kvp.first;
15        const std::string& value = kvp.second;
16
17        // Check if the value already exists as a key in the inverted map.
18        auto it = invertedMap.find(value);
19        if (it != invertedMap.end()) {
20            // If the inverted key (which is the original map's value) is found,
21            // we add the new key (original map's key) to the existing vector.
22            it->second.push_back(key);
23        } else {
24            // If the inverted key does not exist, we create a new vector
25            // with the original map's key and add it to the inverted map.
26            invertedMap[value] = std::vector<std::string>{key};
27        }
28    }
29
30    // Return the result after all keys and values have been inverted.
31    return invertedMap;
32}
33
34// Note: The use of string as the type for keys and values is an assumption.
35// If, in practice, keys or values have different types, the appropriate data
36// structures and type handling would need to be used.
37
1// This function takes an object and inverts its keys and values.
2// If the same value is encountered more than once, the corresponding keys are grouped in an array.
3function invertObject(sourceObject: Record<any, any>): Record<any, any> {
4    // Initialize an object to store the inverted key-value pairs.
5    const invertedObject: Record<any, any> = {};
6
7    // Iterate over each key in the source object.
8    for (const key in sourceObject) {
9        const value = sourceObject[key];
10
11        // Check if the value already exists as a key in the inverted object.
12        if (invertedObject.hasOwnProperty(value)) {
13            // If the inverted key (which is the original object's value) already has an array,
14            // we add the new key (original object's key) into that array.
15            if (Array.isArray(invertedObject[value])) {
16                invertedObject[value].push(key);
17            } else {
18                // Otherwise, we convert it into an array containing the existing and new keys.
19                invertedObject[value] = [invertedObject[value], key];
20            }
21        } else {
22            // If the inverted key does not exist, we simply add it with its value 
23            // (original object's key).
24            invertedObject[value] = key;
25        }
26    }
27
28    // Return the result after all keys have been inverted.
29    return invertedObject;
30}
31
Not Sure What to Study? Take the 2-min Quiz:

Which of the following is a min heap?

Time and Space Complexity

The given TypeScript function inverts a key-value mapping in an object by making the values as keys and the original keys as values. If the function comes across duplicate values in the input, it stores the keys corresponding to that value in an array.

Time Complexity

The time complexity of invertObject is O(n), where n is the number of properties in the input object. This is because the function iterates through all the properties of the object exactly once.

During iteration, the function checks if the ans object has a property with the current value as its name, adds the current key to an array, or creates a new property. The hasOwnProperty check, access, and assignment of a property in an object are all O(1) operations on average, assuming the properties are sufficiently distributed in the underlying hash table. However, when multiple keys map to the same value and an array is created, the push operation on the array is also O(1) on average, assuming dynamic array resizing is infrequent compared to the number of push operations.

Hence, the loop which constitutes the main workload of the function performs a constant amount of work for each property, ensuring an overall linear time complexity.

Space Complexity

The space complexity of invertObject is O(n) because it creates a new object ans that stores all the properties from the original object, but with flipped keys and values. In the worst case, where no values are duplicated, each property from the input will be represented in ans. When values are duplicated and arrays are created, these arrays are stored within the same ans object, not increasing the order of space complexity but only the constants involved.

Furthermore, the space needed for the arrays to accommodate the duplicate keys is included in the O(n) complexity because the size of the arrays is contingent on the number of keys, which at maximum can be n (when all keys have the same value).

Thus, the space required is directly proportional to the size of the input, leading to a linear space complexity.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of these pictures shows the visit order of a depth-first search?


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫