Value-to-Index Mapping

You remember seeing her, but can you say where?

Imagine searching a large dataset. It's often not enough to know that an item exists; you need to know where you saw it first. How can we build a temporary, instant "index" of our data to answer the question, "I need value X, have I seen it before and what was its position?" without having to search for it all over again?

This problem is one of the most famous interview questions of all time. Its optimal solution is a perfect demonstration of the pattern. If you haven't already solved this, please take 15-20 minutes to solve it before moving on.

Problem: Two Sum LeetCode Link : Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

The brute-force solution would give you an $O(N^2)$ time complexity. To optimize it, as you scan through the array, you can maintain a map (or dictionary) that tells you, for every value you’ve seen so far, where you saw it. This "value → index" mapping lets you answer in $O(1)$ time the question, "Have I seen the complement of my current number before, and if so, where?"

value_to_index = {}
for i, num in enumerate(array):
    value_to_index[num] = i
# To find the index of a value
index = value_to_index.get(target_value)

Map<Integer, Integer> valueToIndex = new HashMap<>();
for (int i = 0; i < array.length; i++) {
    valueToIndex.put(array[i], i);
}
// To find the index of a value
Integer index = valueToIndex.get(targetValue);

std::unordered_map<int, int> valueToIndex;
for (int i = 0; i < array.size(); ++i) {
    valueToIndex[array[i]] = i;
}
// To find the index of a value
auto it = valueToIndex.find(targetValue);
int index = (it != valueToIndex.end()) ? it->second : -1;

An extension of this idea is to use a hash map to group items by a computed key, where you categorize items based on a shared property. You generate a "key" for each item (e.g., a sorted string for anagrams) and store a list of items under that key.

grouped_data = defaultdict(list)
for s in strings:
    key = "".join(sorted(s)) # Example: sorted string as key for anagrams
    grouped_data[key].append(s)

Map<String, List<String>> groupedData = new HashMap<>();
for (String s : strings) {
    char[] charArray = s.toCharArray();
    Arrays.sort(charArray);
    String key = new String(charArray); // Example: sorted string as key
    groupedData.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
}

std::unordered_map<std::string, std::vector<std::string>> groupedData;
for (const std::string& s : strings) {
    std::string key = s;
    std::sort(key.begin(), key.end()); // Example: sorted string as key
    groupedData[key].push_back(s);
}

This pattern helps you efficiently answer questions like:

1. "Where did I see this value before?" (Value-to-Index Mapping)
2. "Which items share this specific characteristic?" (Data Grouping)

Walkthrough : Solving "Two Sum"

1. Initialize an empty hash map valueToIndex.
2. We will loop through the nums array once. Let's say nums = {11, 5, 2, 7} and target = 7.
3. Iteration 1 (num = 11, index = 0):
   • Calculate complement = target - num = 7 - 11 = -4.
   • Check if -4 exists in valueToIndex. It does not.
   • Add 11 to valueToIndex with its index: {11: 0}.
4. Iteration 2 (num = 5, index = 1):
   • Calculate complement = 7 - 5 = 2.
   • Check if 2 exists in valueToIndex. It does not.
   • Add 5 to valueToIndex with its index: {11: 0, 5: 1}.
5. Iteration 3 (num = 2, index = 2):
   • Calculate complement = 7 - 2 = 5.
   • Check if 5 exists in valueToIndex. It does! Its index is 1.
   • We have found our solution: return (1, 2).

Complexity Analysis

• Time Complexity: $O(N)$ - We traverse the array once, and each hash map operation (insert, lookup) is $O(1)$ on average.
• Space Complexity: $O(N)$ - In the worst case, we store all elements in the hash map.

Bonus: An Inverted Index which is at the heart of search engines is a perfect example of this pattern. It maps words to their locations in documents for fast lookups. See how foundational this pattern is to many real-world applications!

More Problems & Variations

1. Group Anagrams: LeetCode Link 💡 HintHow can you create a unique "key" for each group of anagrams? The key could be a sorted string or a string representation of the character frequency map.
2. Longest Consecutive Sequence: LeetCode Link 💡 HintFirst, put all numbers into a hash set for $O(1)$ lookups. Then, iterate through the numbers. If a number x is the start of a sequence (i.e., x-1 is not in the set), then see how long a streak you can build by checking for x+1, x+2, etc.
3. Contains Duplicate II: LeetCode Link 💡 HintUse a hash map to track the last index of each number. If you find a number again, check if the difference between the current index and the last index is less than or equal to k.