Hash map lookup

When to use it

Use it when yes or no is not enough: you need something kept beside each item, such as its position or its partner.

It belongs to the foundations group: Remember what you have seen, in a shape that makes the next question take one step.

Watch it work

A teacher wrote down who answered each question in class, in order. Return the shortest wait between two answers by the same pupil, counted in questions. At least one pupil answers twice.

Input
names = ["Ana", "Ben", "Caro", "Ana", "Ben", "Ana"]

Output
2

The method

1. Start with an empty map from each pupil to their last position
2. A pupil found in the map answered before: measure the wait
3. Store this position beside the pupil, over any older one
4. Return the shortest wait

The run, one moment at a time

1. Step 1. No name has been looked at, so the map is empty. The best wait starts at 6, which is longer than any real wait.

   names: Ana Ben Caro Ana Ben Ana
   pupil: empty
   last at: empty
   best: 6
   

2. Step 3. "Ana" is not in the map, so this is the first answer by Ana. Store position 0 beside the name.

   names: Ana Ben Caro Ana Ben Ana
   pupil: Ana
   last at: 0
   best: 6
   

3. Step 3. "Ben" is not in the map, so this is the first answer by Ben. Store position 1 beside the name.

   names: Ana Ben Caro Ana Ben Ana
   pupil: Ana Ben
   last at: 0 1
   best: 6
   

4. Step 3. "Caro" is not in the map, so this is the first answer by Caro. Store position 2 beside the name.

   names: Ana Ben Caro Ana Ben Ana
   pupil: Ana Ben Caro
   last at: 0 1 2
   best: 6
   

5. Step 2. "Ana" is in the map with position 0. This is position 3, so the wait is 3 - 0 = 3. The best wait goes from 6 down to 3.

   names: Ana Ben Caro Ana Ben Ana
   pupil: Ana Ben Caro
   last at: 0 1 2
   best: 3
   

6. Step 3. Store position 3 beside "Ana", over the 0. A later answer by Ana is measured from here.

   names: Ana Ben Caro Ana Ben Ana
   pupil: Ana Ben Caro
   last at: 3 1 2
   best: 3
   

7. Step 2. "Ben" is in the map with position 1. This is position 4, so the wait is 4 - 1 = 3. The best wait stays 3.

   names: Ana Ben Caro Ana Ben Ana
   pupil: Ana Ben Caro
   last at: 3 1 2
   best: 3
   

8. Step 3. Store position 4 beside "Ben", over the 1. A later answer by Ben is measured from here.

   names: Ana Ben Caro Ana Ben Ana
   pupil: Ana Ben Caro
   last at: 3 4 2
   best: 3
   

9. Step 2. "Ana" is in the map with position 3. This is position 5, so the wait is 5 - 3 = 2. The best wait goes from 3 down to 2.

   names: Ana Ben Caro Ana Ben Ana
   pupil: Ana Ben Caro
   last at: 3 4 2
   best: 2
   

10. Step 3. Store position 5 beside "Ana", over the 3. A later answer by Ana is measured from here.

    names: Ana Ben Caro Ana Ben Ana
    pupil: Ana Ben Caro
    last at: 5 4 2
    best: 2
    

11. Step 4. 6 names, 6 lookups. The shortest wait is 2: Ana answered at positions 3 and 5.

    names: Ana Ben Caro Ana Ben Ana
    pupil: Ana Ben Caro
    last at: 5 4 2
    best: 2
    

The code

The numbered comments are the steps of the method.

function solve(names) {
  // 1. Start with an empty map from each pupil to their last position
  const last = new Map();
  let best = names.length; // longer than any real wait
  for (let i = 0; i < names.length; i++) {
    // 2. A pupil found in the map answered before: measure the wait
    if (last.has(names[i])) {
      best = Math.min(best, i - last.get(names[i]));
    }
    // 3. Store this position beside the pupil, over any older one
    last.set(names[i], i);
  }
  // 4. Return the shortest wait
  return best;
}

def solve(names):
    # 1. Start with an empty map from each pupil to their last position
    last = {}
    best = len(names)  # longer than any real wait
    for i in range(len(names)):
        # 2. A pupil found in the map answered before: measure the wait
        if names[i] in last:
            best = min(best, i - last[names[i]])
        # 3. Store this position beside the pupil, over any older one
        last[names[i]] = i
    # 4. Return the shortest wait
    return best

How to spot it

Asked: Return the positions of the two items that match

A position must be remembered beside each item. A map from item to position gives it back in one step.

Given: A rule gives the exact partner of each item

When you know exactly which value you need, you do not search for it. You look it up as a key.

Asked: Put the items that share a label into one group

The label is the key, and the list of its items is kept beside it. Each item finds its group in one step.

Limits: Up to 100,000 items, and each needs its exact partner among the earlier ones

Searching back from every item is about 5 billion steps. One lookup by key for each item is 100,000.

Looks like it, but is not

• You only need to know whether a value came before, and nothing else about it. Use Hash set membership. A map would work, but the part beside the key would never be read. A set keeps the keys alone.
• The question is how often each value appears, not where. Use Frequency counting. That is a map too, but what it keeps is a number that goes up by 1. Nothing is looked up to find a partner or a place.
• The list is sorted and you need a pair of values that meet a condition. Use Opposing two pointers. Sorted order lets two positions walk in from both ends and find the pair with no extra memory.

Cost and mistakes

Time grows with the number of items, about n steps, written O(n), because each lookup and each store is one step on average. Extra space is one map entry for each different key, at most n.

Watch out

• Look up before you store. If the item goes into the map first, it finds itself and looks like its own partner.
• Decide what happens when a key comes again. Storing over the old entry keeps only the newest one. To keep them all, store a list beside the key.

In the 150

3 problems of the 150 use it. Naming them gives their method away, so the list is folded.