2794. Create Object from Two Arrays


Problem Description

The task is to create an object based on two provided arrays: keysArr and valuesArr. The keysArr contains the potential keys for the object, and valuesArr contains the corresponding values. As you iterate through both arrays, you are supposed to use the elements at the same index in each array to construct a key-value pair in the new object obj. However, there are a couple of rules to follow:

  1. If there are duplicate keys, you should only keep the first occurrence of the key-value pair—any subsequent duplicate key should not be included in the object.
  2. If a key in keysArr is not a string, you need to convert it into a string. This can be done using the String() function.

The problem tests your understanding of objects in TypeScript, as well as array manipulation and the consideration of edge cases such as duplicates and type conversion.

Intuition

To approach this problem, we need to think methodically about the process of building an object from two arrays, ensuring we adhere to the stated rules. Here's an intuitive step-by-step approach:

  1. Initialize an empty object to store our key-value pairs.
  2. Iterate over the keysArr array. For each key, we should:
    • Convert the key to a string, which allows any type of values in keysArr to be used as valid object keys.
    • Check if the key is already present in our object. Since object keys in JavaScript are unique, if the key already exists, it means we have a duplicate and should not add it again.
    • If the key does not exist in our object, add the key-value pair to the object using the key from keysArr and value from valuesArr.
    • It is important to note that we don't need to check for the same index in valuesArr as the assumption is that both arrays have a one-to-one mapping.

This solution is straightforward and efficient since it performs a single traversal over the input arrays and maintains a constant lookup time for keys in the object by benefiting from the properties of the object data structure in JavaScript (or TypeScript).

Solution Approach

The solution approach for creating an object from two arrays involves the following steps, demonstrating the use of algorithms, data structures, and patterns:

  1. Initialization: We begin by initializing an empty object ans of type Record<string, any>. In TypeScript, Record is a utility type that constructs an object type with a set of known property keys (in this case, string) and corresponding value types (any in this case, which represents any value type).

    1const ans: Record<string, any> = {};
  2. Iteration: The next step is to loop through the keysArr using a standard for loop. This loop will iterate over all elements of the keysArr array and by extension, through the valuesArr since they are matched by index.

    1for (let i = 0; i < keysArr.length; ++i)
  3. String Conversion: Inside the loop, each key is converted to a string to ensure consistency of the object keys. This conversion is done using the String function.

    1const k = String(keysArr[i]);
  4. Key Uniqueness Check: We must ensure that each key included in the object is unique. If the key k is undefined in ans, it means the key is not yet added to the object, and it's safe to insert the key-value pair into it.

    1if (ans[k] === undefined)
  5. Creating Key-Value Pair: Once we confirm the key is unique, we assign the value from valuesArr at the same index to the key we've just processed.

    1ans[k] = valuesArr[i];
  6. Returning the Result: After the loop has processed all key-value pairs, the fully constructed object ans is returned.

    1return ans;

This solution uses a for loop for iteration, object data structure for key-value pairing, and string conversion. Altogether, this results in a time complexity of O(n), where n is the number of elements in keysArr. The space complexity is also O(n) to store the resulting key-value pairs in the object. The use of JavaScript object properties ensures that no duplicate keys are present in the final output.

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

Which one best describes the time complexity of the following code?

1int factorial(int n) {
2  if (n < 0) {
3    return -1;
4  } else if (n == 0) {
5    return 1;
6  } else {
7    return n * factorial(n - 1);
8  }
9}

Example Walkthrough

Let's say we are given the following two arrays:

1const keysArr = ['foo', 'bar', 'foo', 123];
2const valuesArr = [1, 2, 3, 4];

The goal is to create an object that maps each string key from keysArr to the corresponding value in valuesArr.

Following are the steps from the solution approach applied to this example:

  1. Initialization: We start by creating an empty object:

    1const ans: Record<string, any> = {};

    ans is now an empty object {}.

  2. Iteration: We iterate through each element of keysArr:

    1for (let i = 0; i < keysArr.length; ++i)

    This loops from i = 0 to i = 3 since there are 4 elements in keysArr.

  3. String Conversion: Convert each key to a string:

    1const k = String(keysArr[i]);

    This will convert the keys to 'foo', 'bar', 'foo', '123'.

  4. Key Uniqueness Check: We check if the key already exists in the ans object. For the first-time key 'foo', 'bar', and '123', the condition will be true, but it’s false for the second occurrence of 'foo'.

    1if (ans[k] === undefined)

    For the first time, we encounter 'foo', 'bar', and '123', they don't exist in ans, so we proceed to add them.

  5. Creating Key-Value Pair: Add the key-value pair to the ans object if the key is first-time seen:

    1ans[k] = valuesArr[i];

    After processing each key-value pair, ans will look like:

    1{ 'foo': 1, 'bar': 2, '123': 4 }

    Note that the second 'foo' was not added because it was already present.

  6. Returning the Result: After looping through the arrays, we return the ans object:

    1return ans;

At the end of execution, the resulting object will be:

1{
2  'foo': 1,
3  'bar': 2,
4  '123': 4
5}

This matches our rules where we avoid duplicates and convert non-string keys to strings. The returned object now correctly maps each key of keysArr to its corresponding value from valuesArr following the mentioned transformation and restrictions.

Solution Implementation

1def create_object(keys_arr, values_arr):
2    # Initialize an empty dictionary to store the key-value pairs
3    record = {}
4  
5    # Iterate over all elements in the keys array
6    for i in range(len(keys_arr)):
7        # Convert the key at index i to a string
8        key = str(keys_arr[i])
9      
10        # If the key doesn't exist in the record, add it with its matching value
11        if key not in record:
12            # Use the corresponding index in the values array for the value
13            record[key] = values_arr[i]
14        # If the key already exists, the loop continues to the next iteration without modification
15
16    # Return the constructed dictionary
17    return record
18
1import java.util.HashMap;
2import java.util.Map;
3
4public class ObjectCreator {
5  
6    /**
7     * This method takes two arrays, one for keys and one for values, and creates a map
8     * with each key mapped to its corresponding value. If there are duplicate keys, only
9     * the first occurrence is considered.
10     *
11     * @param keysArr   the array containing keys
12     * @param valuesArr the array containing values
13     * @return a map constructed with key-value pairs from the given arrays
14     */
15    public Map<String, Object> createObject(Object[] keysArr, Object[] valuesArr) {
16        // Initialize an empty HashMap to store the key-value pairs
17        Map<String, Object> record = new HashMap<>();
18
19        // Iterate over all elements in the keys array
20        for (int i = 0; i < keysArr.length; ++i) {
21            // Convert the key at index i to a string
22            String key = keysArr[i].toString();
23
24            // If the key doesn't exist in the record, add it with its matching value
25            if (!record.containsKey(key)) {
26                // Check if the key has a corresponding value before adding it
27                Object value = i < valuesArr.length ? valuesArr[i] : null;
28
29                record.put(key, value);
30            }
31            // If the key already exists, it is ignored due to the check above
32        }
33
34        // Return the constructed map
35        return record;
36    }
37}
38
1#include <unordered_map>
2#include <string>
3#include <vector>
4
5// This function takes two vectors: one for keys (keys) and one for values (values)
6// It creates an unordered_map (objectMap) with each key mapped to its corresponding value.
7// If there are duplicate keys, only the first occurrence is considered.
8
9std::unordered_map<std::string, std::string> CreateObject(const std::vector<std::string>& keys, const std::vector<std::string>& values) {
10    // Initialize an empty unordered_map to store the key-value pairs
11    std::unordered_map<std::string, std::string> objectMap;
12  
13    // Iterate over all elements in the keys vector
14    for (size_t i = 0; i < keys.size(); ++i) {
15        // Convert the key at index 'i' to a string (it's already a string, but kept for consistency)
16        std::string key = keys[i];
17      
18        // If the key doesn't exist in the objectMap, add it with its matching value
19        if (objectMap.find(key) == objectMap.end()) {
20            // Check if we have a corresponding value for the key, if not set an empty string
21            std::string value = (i < values.size()) ? values[i] : std::string();
22            objectMap[key] = value;
23        }
24        // If the key already exists, it is ignored due to the check above
25    }
26  
27    // Return the constructed objectMap
28    return objectMap;
29}
30
1// This function takes two arrays: one for keys (keysArr) and one for values (valuesArr)
2// It creates an object (record) with each key mapped to its corresponding value.
3// If there are duplicate keys, only the first occurrence is considered.
4
5function createObject(keysArr: any[], valuesArr: any[]): Record<string, any> {
6    // Initialize an empty object to store the key-value pairs
7    const record: Record<string, any> = {};
8  
9    // Iterate over all elements in the keys array
10    for (let i = 0; i < keysArr.length; ++i) {
11        // Convert the key at index i to a string
12        const key = String(keysArr[i]);
13      
14        // If the key doesn't exist in the record, add it with its matching value
15        if (record[key] === undefined) {
16            record[key] = valuesArr[i];
17        }
18        // If the key already exists, it is ignored due to the check above
19    }
20  
21    // Return the constructed record
22    return record;
23}
24

Time and Space Complexity

Time Complexity

The time complexity of the given function is primarily determined by the for loop that iterates through the keysArr array. For each iteration, it performs a constant time operation of converting the key to a string and checking/assigning it in the ans object.

The main operations within the loop are:

  • Converting the key to a string: O(1)
  • Checking if the key exists in the object: O(1) on average
  • Assigning the value to the object: O(1)

Considering the loop runs n times, where n is the length of keysArr, the overall time complexity is O(n).

Space Complexity

The space complexity is determined by the space required to store the ans object, which has as many properties as there are unique keys provided in the keysArr.

  • ans object storage: up to O(n)

The total space complexity of the function is O(n), where n is the length of keysArr.

Note: In the worst-case scenario, if the keys are all unique, the space complexity will indeed be O(n). However, if keys are repeated, the number of actual unique keys stored could be less than n, providing a best-case space complexity of O(u), where u is the number of unique keys.


Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following problems can be solved with backtracking (select multiple)


Recommended Readings


Got a question? Ask the Monster 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.


🪄