Problem Description

This problem asks you to create a function that inverts the key-value relationship of an object or array.

Given an input object obj, you need to return a new object invertedObj where:

• The values from the original object become the keys in the inverted object
• The keys from the original object become the values in the inverted object
• For arrays, treat the array indices as keys

The main challenge is handling duplicate values. When multiple keys in the original object have the same value, the inverted object should map that value to an array containing all the corresponding keys.

For example:

• If obj = {a: "1", b: "2"}, then invertedObj = {"1": "a", "2": "b"}
• If obj = {a: "1", b: "1"}, then invertedObj = {"1": ["a", "b"]} (duplicate handling)
• If obj = ["x", "y"], then invertedObj = {"x": "0", "y": "1"} (indices as keys)

The solution iterates through each key-value pair in the input object. For each value:

1. If it doesn't exist as a key in the result object, create it with the current key as its value
2. If it already exists with a single value, convert that value to an array containing both the existing and new keys
3. If it already exists with an array value, push the new key to that array

This approach ensures all original keys are preserved when values are duplicated, maintaining a complete inverse mapping.

Intuition

The key insight is recognizing that we're essentially creating a reverse mapping. In a normal object, each key maps to exactly one value, but when we invert it, multiple keys might map to the same value - which means in the inverted object, that value needs to map back to multiple keys.

Think of it like a phone book. Originally, we have names (keys) mapping to phone numbers (values). When we invert it, we want phone numbers to map back to names. But what if two people share the same phone number? We need to keep track of both names.

This leads us to three distinct cases we need to handle:

1. First occurrence: When we encounter a value for the first time, we simply map it to its corresponding key. This is straightforward - invertedObj[value] = key.

2. Second occurrence: When we see the same value again, we now have two keys that need to be associated with it. We transform the single key into an array containing both the original key and the new one: [originalKey, newKey].

3. Subsequent occurrences: Once we already have an array, we just keep adding new keys to it.

The natural approach is to iterate through the object once, checking for each value whether it already exists in our result. Using hasOwnProperty() ensures we correctly handle edge cases where values might be falsy (like empty strings or "0").

For arrays, the solution elegantly handles them by treating indices as keys - JavaScript's for...in loop naturally iterates over array indices as strings, so arrays are processed just like objects without needing special handling.

This single-pass approach with conditional logic for handling duplicates gives us an efficient O(n) solution where n is the number of key-value pairs in the input.

Solution Approach

The implementation uses a hash table (JavaScript object) to build the inverted mapping. Here's a step-by-step walkthrough of the algorithm:

Initialize the result object:

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

We create an empty object that will store our inverted key-value pairs.

Iterate through all keys:

for (const key in obj) {

The for...in loop iterates over all enumerable properties of the object. For arrays, this includes the indices as strings ("0", "1", "2", etc.).

Check if the value already exists as a key in the result:

if (ans.hasOwnProperty(obj[key])) {

This checks whether we've already encountered this value before. Using hasOwnProperty() is important to avoid issues with inherited properties and to correctly handle falsy values.

Handle duplicate values:

When the value already exists in our result object, we have two sub-cases:

1. If the existing value is already an array:

   if (Array.isArray(ans[obj[key]])) {
       ans[obj[key]].push(key);
   }

   Simply append the new key to the existing array.

2. If the existing value is a single key:

   else {
       ans[obj[key]] = [ans[obj[key]], key];
   }

   Convert it to an array containing both the existing key and the new key.

Handle first occurrence:

else {
    ans[obj[key]] = key;
}

When encountering a value for the first time, directly map it to its corresponding key.

The algorithm maintains the following invariants:

• Each unique value from the original object becomes a key in the result
• Single mappings are stored as simple values
• Multiple mappings are stored as arrays
• The order of keys in the arrays follows the iteration order of the original object

Time Complexity: O(n) where n is the number of properties in the input object Space Complexity: O(n) for storing the inverted object

Example Walkthrough

Let's walk through the solution with a concrete example to see how the algorithm handles different cases:

Input: obj = {a: "1", b: "2", c: "1", d: "1"}

Step-by-step execution:

1. Initialize: ans = {}

2. Process key "a" with value "1":

   • Check: Does ans have property "1"? No
   • Action: Set ans["1"] = "a"
   • Result: ans = {"1": "a"}

3. Process key "b" with value "2":

   • Check: Does ans have property "2"? No
   • Action: Set ans["2"] = "b"
   • Result: ans = {"1": "a", "2": "b"}

4. Process key "c" with value "1":

   • Check: Does ans have property "1"? Yes
   • Check: Is ans["1"] an array? No (it's "a")
   • Action: Convert to array: ans["1"] = ["a", "c"]
   • Result: ans = {"1": ["a", "c"], "2": "b"}

5. Process key "d" with value "1":

   • Check: Does ans have property "1"? Yes
   • Check: Is ans["1"] an array? Yes
   • Action: Push "d" to array: ans["1"].push("d")
   • Result: ans = {"1": ["a", "c", "d"], "2": "b"}

Final Output: {"1": ["a", "c", "d"], "2": "b"}

This example demonstrates all three cases:

• First occurrence (steps 2 & 3): Direct assignment
• Second occurrence (step 4): Convert single value to array
• Subsequent occurrences (step 5): Append to existing array

For an array input like ["x", "y", "x"], the same logic applies but with indices as keys:

• Process index "0" with value "x" → {"x": "0"}
• Process index "1" with value "y" → {"x": "0", "y": "1"}
• Process index "2" with value "x" → {"x": ["0", "2"], "y": "1"}

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the number of key-value pairs in the input object.

• The code iterates through each key in the input object exactly once using a for...in loop
• For each iteration, the operations performed are:
  • Checking if a property exists using hasOwnProperty(): O(1)
  • Checking if a value is an array using Array.isArray(): O(1)
  • Array push operation (when applicable): O(1) amortized
  • Property assignment: O(1)
• Since we perform constant time operations for each of the n keys, the overall time complexity is O(n)

Space Complexity: O(n) where n is the number of key-value pairs in the input object.

• The algorithm creates a new object ans to store the inverted mapping
• In the worst case (when all values in the original object are unique), the new object will have exactly n key-value pairs
• In cases where multiple keys map to the same value, arrays are created to store these keys, but the total number of stored elements (keys from the original object) remains n
• The space used for the output object and its contents is proportional to the size of the input, resulting in O(n) space complexity

Common Pitfalls

1. Type Coercion Issues with Object Keys

One significant pitfall occurs when values in the original object are not valid object key types. In JavaScript/TypeScript, object keys are always strings (or Symbols), so non-string values get automatically converted to strings. This can lead to unexpected collisions.

Problem Example:

const obj = {a: 1, b: "1", c: true, d: "true"};
const inverted = invertObject(obj);
// Result: {"1": ["a", "b"], "true": ["c", "d"]}
// The number 1 and string "1" both become the string key "1"
// The boolean true and string "true" both become the string key "true"

Solution: To handle this properly, you could:

1. Use a Map instead of a plain object, which preserves type distinctions:

function invertObjectWithMap(obj) {
    const result = new Map();
    for (const key in obj) {
        const value = obj[key];
        if (result.has(value)) {
            const existing = result.get(value);
            result.set(value, Array.isArray(existing) ? [...existing, key] : [existing, key]);
        } else {
            result.set(value, key);
        }
    }
    return result;
}

2. Or maintain type information by wrapping values:

function invertObjectPreserveTypes(obj) {
    const result = {};
    for (const key in obj) {
        const value = obj[key];
        const valueKey = JSON.stringify({type: typeof value, val: value});
        if (result.hasOwnProperty(valueKey)) {
            if (Array.isArray(result[valueKey])) {
                result[valueKey].push(key);
            } else {
                result[valueKey] = [result[valueKey], key];
            }
        } else {
            result[valueKey] = key;
        }
    }
    return result;
}

2. Handling Null and Undefined Values

Another pitfall is dealing with null or undefined values, which can cause runtime errors or unexpected behavior.

Problem Example:

const obj = {a: null, b: undefined, c: null};
const inverted = invertObject(obj);
// Could result in {"null": ["a", "c"], "undefined": "b"}
// But accessing properties on null/undefined in certain contexts might throw errors

Solution: Add validation to skip or handle these special cases:

function invertObjectSafe(obj) {
    const result = {};
    for (const key in obj) {
        const value = obj[key];
        // Skip null or undefined values
        if (value == null) continue;

        // Or convert them to a special string representation
        const safeValue = value ?? `__${value}__`;

        if (result.hasOwnProperty(safeValue)) {
            if (Array.isArray(result[safeValue])) {
                result[safeValue].push(key);
            } else {
                result[safeValue] = [result[safeValue], key];
            }
        } else {
            result[safeValue] = key;
        }
    }
    return result;
}

3. Array Index Type Inconsistency

When inverting arrays, indices are strings in the result, which might not match expectations when comparing with numbers.

Problem Example:

const arr = ["a", "b", "c"];
const inverted = invertObject(arr);
// Result: {"a": "0", "b": "1", "c": "2"}
// Note: values are strings, not numbers
console.log(inverted["a"] === 0); // false
console.log(inverted["a"] === "0"); // true

Solution: Convert indices to numbers if numeric indices are expected:

function invertArray(arr) {
    const result = {};
    for (let i = 0; i < arr.length; i++) {
        const value = arr[i];
        if (result.hasOwnProperty(value)) {
            if (Array.isArray(result[value])) {
                result[value].push(i); // Use numeric index
            } else {
                result[value] = [result[value], i];
            }
        } else {
            result[value] = i; // Store as number
        }
    }
    return result;
}