LeetCode Problem 2822

Difficulty: 🟢 Easy
Topics: —

Solution

LeetCode 2822 - Inversion of Object

Problem Understanding

This problem asks us to invert the relationship between keys and values in a JSON object or array.

The input can be either:

• A JSON object, where keys are strings and values are strings.
• A JSON array, where indices act as keys and elements are strings.

The goal is to create a new object called invertedObj where:

• Every original value becomes a key.
• Every original key becomes a value.

For example, if the original object contains:

{
    "a": "1"
}

then the inverted object becomes:

{
    "1": "a"
}

The complication comes from duplicate values. Multiple keys may map to the same value in the original object. Since object keys must be unique, a single inverted key may need to store multiple original keys.

For example:

{
    "a": "2",
    "b": "2"
}

cannot become:

{
    "2": "a",
    "2": "b"
}

because the second assignment would overwrite the first. Instead, the inverted object must store all matching keys:

{
    "2": ["a", "b"]
}

When the input is an array, the indices are treated as keys. For example:

["x", "y"]

is conceptually:

{
    "0": "x",
    "1": "y"
}

and therefore inverts to:

{
    "x": "0",
    "y": "1"
}

The constraints guarantee that every value is a string. This simplifies the problem because every value can safely be used as a key in the inverted object.

The serialized input size can be as large as 10^5 characters, which means we should aim for a linear-time solution. Any approach that repeatedly scans the entire object for duplicates would become unnecessarily expensive.

Important edge cases include duplicate values, arrays instead of objects, and situations where more than two keys share the same value. The problem guarantees that all values are strings, so we never need to handle nested objects, numbers, booleans, or other JSON types as values.

Approaches

Brute Force Approach

A straightforward solution is to process each key-value pair one at a time. For every value, we could scan the entire object again to find all keys that map to that value.

For example, when processing value "2", we would search through every key in the object and collect all matching keys.

This approach is correct because it explicitly finds every key associated with every value. However, it performs repeated full scans of the input. If there are n entries, each entry may require another scan of up to n elements.

As a result, the time complexity becomes quadratic.

Optimal Approach

The key observation is that we only need one pass through the input.

As we iterate through each key-value pair:

• If the value has never appeared before, store the key directly.
• If the value has appeared before and currently maps to a single key, convert that entry into an array containing both keys.
• If the value already maps to an array, simply append the new key.

A hash map is ideal because it allows constant-time lookup and update for each value.

This eliminates repeated scanning and produces the inverted object in linear time.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Repeatedly scans the entire input to find duplicate values
Optimal	O(n)	O(n)	Single pass using a hash map for constant-time updates

Algorithm Walkthrough

1. Create an empty hash map called inverted.
2. Iterate through every key-value pair in the input object. If the input is an array, the iteration automatically provides indices as keys.
3. For the current key and value, check whether the value already exists in inverted.
4. If the value does not exist, store the key directly:

inverted[value] = key

This is the simplest case because no duplicate has been encountered yet. 5. If the value already exists, there are two possibilities. 6. If the existing entry is a single string, this means we have encountered the first duplicate. Convert the stored string into an array containing both keys:

inverted[value] = [existingKey, key]

7. If the existing entry is already an array, append the new key to that array.
8. Continue until all entries have been processed.
9. Return the completed inverted object.

Why it works

The algorithm maintains the invariant that for every value processed so far, inverted[value] contains exactly all keys that have produced that value.

When a value appears for the first time, the invariant holds because the corresponding key is stored directly. When duplicates appear, the stored representation is expanded into an array and all future matching keys are appended. Therefore, after processing all entries, every value maps to precisely the set of original keys that produced it, which is exactly the required inversion.

Python Solution

from typing import Any

class Solution:
    def invertObject(self, obj: Any) -> dict:
        inverted = {}

        if isinstance(obj, list):
            iterable = enumerate(obj)
        else:
            iterable = obj.items()

        for key, value in iterable:
            key = str(key)

            if value not in inverted:
                inverted[value] = key
            else:
                if isinstance(inverted[value], list):
                    inverted[value].append(key)
                else:
                    inverted[value] = [inverted[value], key]

        return inverted

The implementation begins by creating the result dictionary inverted.

Because the input may be either an object or an array, the code first determines how to iterate through it. For arrays, enumerate() provides index-value pairs. For objects, items() provides key-value pairs.

Each key is converted to a string because array indices are integers in Python but must behave as string keys according to the problem specification.

For every value, the code checks whether that value already exists in the inverted dictionary.

If it does not exist, the key is stored directly. If it does exist, the implementation distinguishes between two situations. When the existing entry is already a list, the new key is appended. Otherwise, the existing string is converted into a two-element list containing both keys.

After processing all entries, the completed inverted dictionary is returned.

Go Solution

func invertObject(obj interface{}) map[string]interface{} {
	inverted := make(map[string]interface{})

	switch v := obj.(type) {
	case []interface{}:
		for i, value := range v {
			val := value.(string)
			key := strconv.Itoa(i)

			if existing, ok := inverted[val]; !ok {
				inverted[val] = key
			} else {
				switch e := existing.(type) {
				case string:
					inverted[val] = []string{e, key}
				case []string:
					inverted[val] = append(e, key)
				}
			}
		}

	case map[string]interface{}:
		for key, value := range v {
			val := value.(string)

			if existing, ok := inverted[val]; !ok {
				inverted[val] = key
			} else {
				switch e := existing.(type) {
				case string:
					inverted[val] = []string{e, key}
				case []string:
					inverted[val] = append(e, key)
				}
			}
		}
	}

	return inverted
}

The Go implementation follows the same logic as the Python version. Because Go does not have dynamic dictionary values in the same way as JavaScript, the result map is declared as map[string]interface{}. This allows each inverted entry to hold either a single string or a slice of strings.

Type assertions are used to distinguish between those two representations. Array indices are converted to strings using strconv.Itoa, ensuring consistency with the problem requirements.

Worked Examples

Example 1

Input:

{
    "a": "1",
    "b": "2",
    "c": "3",
    "d": "4"
}

Step	Key	Value	Inverted State
1	a	1	{"1":"a"}
2	b	2	{"1":"a","2":"b"}
3	c	3	{"1":"a","2":"b","3":"c"}
4	d	4	{"1":"a","2":"b","3":"c","4":"d"}

Final result:

{
    "1": "a",
    "2": "b",
    "3": "c",
    "4": "d"
}

Example 2

Input:

{
    "a": "1",
    "b": "2",
    "c": "2",
    "d": "4"
}

Step	Key	Value	Inverted State
1	a	1	{"1":"a"}
2	b	2	{"1":"a","2":"b"}
3	c	2	{"1":"a","2":["b","c"]}
4	d	4	{"1":"a","2":["b","c"],"4":"d"}

Final result:

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

Example 3

Input:

["1", "2", "3", "4"]

Iteration treats indices as keys.

Step	Index	Value	Inverted State
1	0	1	{"1":"0"}
2	1	2	{"1":"0","2":"1"}
3	2	3	{"1":"0","2":"1","3":"2"}
4	3	4	{"1":"0","2":"1","3":"2","4":"3"}

Final result:

{
    "1": "0",
    "2": "1",
    "3": "2",
    "4": "3"
}

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each key-value pair is processed exactly once
Space	O(n)	The inverted object stores information derived from all input entries

The algorithm performs a single pass through the input. Every hash map lookup, insertion, and append operation takes constant time on average. Therefore the total running time grows linearly with the number of entries. The output itself may contain all original keys, so linear auxiliary space is required.

Test Cases

solution = Solution()

# Example 1, all values unique
assert solution.invertObject(
    {"a": "1", "b": "2", "c": "3", "d": "4"}
) == {
    "1": "a",
    "2": "b",
    "3": "c",
    "4": "d",
}

# Example 2, duplicate value
assert solution.invertObject(
    {"a": "1", "b": "2", "c": "2", "d": "4"}
) == {
    "1": "a",
    "2": ["b", "c"],
    "4": "d",
}

# Example 3, array input
assert solution.invertObject(
    ["1", "2", "3", "4"]
) == {
    "1": "0",
    "2": "1",
    "3": "2",
    "4": "3",
}

# Multiple duplicates of same value
assert solution.invertObject(
    {"a": "x", "b": "x", "c": "x"}
) == {
    "x": ["a", "b", "c"]
}

# Array with duplicates
assert solution.invertObject(
    ["a", "b", "a"]
) == {
    "a": ["0", "2"],
    "b": "1",
}

# Smallest meaningful duplicate case
assert solution.invertObject(
    {"a": "z", "b": "z"}
) == {
    "z": ["a", "b"]
}

# All entries share same value
assert solution.invertObject(
    {"a": "k", "b": "k", "c": "k", "d": "k"}
) == {
    "k": ["a", "b", "c", "d"]
}

# Single duplicate appearing late
assert solution.invertObject(
    {"a": "1", "b": "2", "c": "3", "d": "2"}
) == {
    "1": "a",
    "2": ["b", "d"],
    "3": "c",
}

Test Summary

Test	Why
Unique object values	Verifies basic inversion behavior
One duplicate value	Verifies conversion from string to list
Array input	Verifies index handling
Three identical values	Verifies repeated appending to list
Duplicate values in array	Verifies arrays and duplicates together
Two-key duplicate	Smallest duplicate scenario
All values identical	Stress test for grouping logic
Duplicate appearing later	Ensures earlier mapping is preserved correctly

Edge Cases

Multiple Keys Sharing the Same Value

A common bug is correctly handling the second occurrence of a value but failing on the third or fourth occurrence. For example:

{
    "a": "x",
    "b": "x",
    "c": "x"
}

A solution that only converts a string into a two-element array may lose later keys. The implementation explicitly checks whether the stored value is already a list and appends additional keys, ensuring all duplicates are preserved.

Array Inputs

Because arrays are valid inputs, their indices must be treated as keys. A naive implementation might use integer indices directly, producing incorrect output types. The implementation converts every index to a string before storing it, matching the required behavior.

Late Duplicate Discovery

Consider:

{
    "a": "1",
    "b": "2",
    "c": "3",
    "d": "2"
}

The duplicate is not discovered until near the end of processing. A buggy implementation might overwrite "b" with "d" and lose information. The solution instead converts the existing string "b" into ["b", "d"], preserving all original keys associated with value "2".

All Values Unique

When every value is distinct, no arrays should appear in the output. Some implementations unnecessarily wrap every key inside a list. The algorithm stores a plain string for first occurrences and only creates a list when a duplicate actually appears, matching the specification exactly.